notes/diff-optimizations.txt

Introduction
------------

This file documents some potential optimizations for "svn diff" (or more
specifically for the diff algorithm in libsvn_diff, which is used in the
"diff", "blame", "merge" and "update" subcommands on the client side).

There are two broad approaches:

  - Speed up the existing algorithm, while maintaining a "minimal diff" 
    (i.e. without heuristics).
    
  - Introduce a "non-minimal diff" mode, either by adding heuristics in the
    existing algorithm, or by implementing another algorithm which doesn't
    guarantee that it will produce the "minimal diff" in all cases.


I. Speeding up "minimal" diff (no heuristics)
---------------------------------------------

1) More low-level optimization of prefix/suffix scanning.

  - Further optimization of the N-ary prefix/suffix scanning.
  - Add special-case code for N==2 (i.e. "svn diff").

2) Optimize line hashing.

  - Merge hash calculation with EOL scanning.
  - Reduce function calling overhead, including loop setup & finalization.

3) Reduce overhead of line/hash container.

  - Use a low collision rate / low overhead hash container.

4) Avoid some hashing by exploiting the fact that matching lines often come
   in series.

  - If the previous line had a match with the other file, first try to
    directly compare (memcmp) the next line with the successor of the
    matched line. Only if it doesn't match, calculate the hash to insert
    it into the container.
  - This approach probably conflicts with the "Merge hash calculation with 
    EOL scanning" suggestion.

5) Discarding non-matching lines before running the LCS (Longest Common
   Subsequence) algorithm.

  - Can make a *huge* impact on files which have a lot of different/unique
    lines.
    (for instance, an example script from the users list [1], which
    generates two files with random lines, 3/4th of which are
    non-matching: diff goes from several hours to a couple of seconds;
    another example is a big file of which indentation style was changed
    from tabs to spaces, and diffing without an ignore-whitespace option).

  - GNU diff does this as well, but strangely, it does it only as part
    of a heuristic (which also discards other "confusing lines"). If run
    with --minimal, these lines are not discarded (though, AFAICS, there
    should be no problem discarding the non-matching lines even when going
    for a minimal diff).

  - From mailthread [2]:
    The core algorithm for calculating a (minimal) diff is to first find
    the Longest Common Subsequence (the longest sequence of lines which
    appear both in A and in B (not necessarily as contiguous lines, there
    can be gaps)). The actual diff can be derived from this very quickly.

    But lines which only appear in A, or only in B, can never be part of
    the LCS, because they are not common lines to begin with.

    So we can just as well calculate the LCS of A' and B' (A and B
    without their "definitely non-matching" lines). This will also be an
    LCS of A and B, because there are no common lines added which can make
    it even longer.

    The only thing I'm not 100% sure of is if it would yield the same LCS
    (there can be many LCS's, all equally long, hence the different
    possible diff-representations which are sometimes not nice for human
    readers). However, gut feeling tells me it will be the same. I can't
    prove this though, so feel free to come up with a counter example :-).
    (although having a different LCS would not be a disaster: it would
    still be a minimal diff, but a different one).

    The practical difficulty is to map line numbers from lines in A and B
    to their corresponding lines in A' and B', and back again.


II. Going for a non-minimal diff (i.e. heuristics)
--------------------------------------------------

In some cases, heuristics can make a big difference (while not guaranteeing
that you'll get a minimal diff).
See also issue #1966 (libsvn_diff needs 'non-minimal-diff' mode) [3].

1) Make prefix/suffix scanning able to skip 1 or a couple of 
   non-matching lines, if it is able to find strictly more matching lines
   after that, to keep the prefix/suffix scanning going.

   This will usually work well, but can sometimes lead to missynchronization
   (see [4]):

     bxxaxxbxx
      || ||
     axxbxx

   instead of (longest common subsequence):
	
     bxxaxxbxx
       //////
      axxbxx 

2) Add some heuristics-based shortcuts in the LCS algorithm.
      
3) Implement another diff algorithm, such as "Patience Diff" [5], which is
   already implemented in several other (D)VCS's. It has the potential to
   be much faster (reducing the problem to calculating several, much
   smaller LCS's), and has the added advantage of often producing "nicer"
   diff output. It is however slightly "heuristical", it doesn't guarantee
   minimality of the diff.


References
----------

[1] http://svn.haxx.se/users/archive-2011-01/0319.shtml
[2] http://svn.haxx.se/dev/archive-2011-02/0772.shtml
[3] http://subversion.tigris.org/issues/show_bug.cgi?id=1966 (libsvn_diff
needs 'non-minimal-diff' mode)
[4] Miller, W., and Myers, E.W. "A File Comparison Program.", Software -
    Practice & Experience 15 (1985), pp. 1025-1040.
[5] http://bramcohen.livejournal.com/73318.html
[6] Mailthread with an earlier version of these notes, and some additional
    discussion: http://svn.haxx.se/dev/archive-2011-02/0490.shtml