notes/diff-optimizations.txt - trunk - niceSOFT/subversion

notes/diff-optimizations.txt
87 строк3 KB
Julian Foad
Update issue tracker links in notes, from Tigris (issuezilla) to Apache (Jira).
16 апр 2018, 16:57
16 апр 2018, 16:5743e846c
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.


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) [1].

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 [2]):

     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" [3], 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] https://issues.apache.org/jira/browse/SVN-1966 (libsvn_diff
needs 'non-minimal-diff' mode)
[2] Miller, W., and Myers, E.W. "A File Comparison Program.", Software -
    Practice & Experience 15 (1985), pp. 1025-1040.
[3] http://bramcohen.livejournal.com/73318.html