Re: My take on the diff-optimizations-bytes branch

On Sat, Jan 1, 2011 at 11:25 PM, Stefan Fuhrmann
<stefanfuhrmann_at_alice-dsl.de> wrote:
> Hi Johan,
>
> Thursday night I did something stupid and had a look at  how
> svn blame could be made faster based on the HEAD code in
> your branch.
>
> One night and most of the following day later, I think I made it
> a few percent faster now. Some of the code I committed directly
> to /trunk and you need to pull these changes into your branch
> to compile the attached patch.
>
> Feel free to test it, take it apart and morph it any way you like --
> I know the patch isn't very pretty in the first place. I tested the
> patch on x64 LINUX and would like to hear whether it at least
> somewhat improved performance on your system for your
> svn blame config.xml use-case.
>
> -- Stefan^2.
>
> [[[
> Speed-up of datasource_open() and its sub-routines
> by a series of optimizations:
>
> * allocate the file[] array on stack instead of heap
>  (all members become directly addressible through
>  the stack pointer because all static sub-functions
>  will actually be in-lined)
> * minor re-arragements in arithmetic expressions to
>  maximize reuse of results (e.g. in INCREMENT_POINTERS)
> * move hot spots to seperate functions and provide a
>  specialized version for file_len == 2
>  (many loops collapse to a single execution, other
>  values can be hard-coded, etc.)
> * use seperate loops to process data within a chunk
>  so we don't need to call INCREMENT_POINTERS & friends
>  that frequently
> * scan / compare strings in machine-word granularity
>  instead of bytes
> ]]]

Hi Stefan,

Thanks for taking a look. I really appreciate it.

When I saw your first couple of commits, to the adler32 stuff, I
already thought: hmmm, he's up to something :-). And after I saw your
change to eol.c#svn_eol__find_eol_start, reading per machine-word, I
was thinking: hey, I could really use something like that in the
prefix/suffix scanning. Nice ... :-)

(I had some trouble applying your patch. It doesn't apply cleanly
anymore to HEAD of the branch (but most hunks were applied correctly,
and I could manually change the rest, so no problem)).

However, first tests are not so great. In fact, it's about 25% slower
(when blaming my settings.xml file with 2200 revisions, it's spending
about 90 seconds in diff, vs. around 72 with HEAD of
diff-optimizations-bytes).

Analyzing further, I can see it's spending significantly less time in
prefix/suffix scanning, but more time in token.c#svn_diff__get_tokens
(which is where the original algorithm gets the tokens/lines and
inserts them into the "token tree"). This tells me it's not working
correctly: either prefix/suffix scanning fails too soon, so there's
much more left for the regular algorithm. Or it's just not functioning
correctly.

Looking at the result of the blame operation, it seems it's the
latter. The final result of the blame is not correct anymore.

I'll try to look some more into it, to see what's going wrong. Maybe
you can also see it with a simple diff of a large file ... (for a good
example in svn's own codebase, you could try
subversion/tests/cmdline/merge-tests.py (pretty large, and almost 700
revisions)).

Cheers,

-- 
Johan