Porting JGit HistogramDiff

From: Shawn Pearce <spearce@spearce.org>
Date: Feb 1, 2011, 05:02 UTC
Message-ID: <AANLkTimisConBkVqCxYjd-HKL0=grFtVT5=fbqakA59O@mail.gmail.com>

On Mon, Jan 31, 2011 at 09:05, Junio C Hamano <gitster@pobox.com> wrote:

Show 5 quoted lines

>
>  * Shawn Pearce says that the diff implementation JGit uses (histogram
>   diff) performs way better than the xdiff implementation we use by
>   default. It would be great if somebody can spend time taking a look at
>   it and possibly port it back to C-git.

The idea that JGit's HistogramDiff is faster came from Robin Rosenburg in [1]:

Show 14 quoted lines

> $ time jgit log -M -p >jgit.txt
>
> real	0m3.880s
> user	0m7.137s
> sys	0m0.807s
>
> $ time git log -M -p >cgit.txt
>
> real	0m16.420s
> user	0m14.936s
> sys	0m0.899s
>
> Seems JGit beats the pants off C Git. A quick scans implies both version
> produce correct diffs, but don't post this to the Git ML list just yet :)

HistogramDiff is a variation of Patience Difference[2]. Within JGit it is implemented as two classes:

  HistogramDiff[3] - the top level driver

  HistogramDiffIndex[4] - the hash table used to count and match occurrences

Because its based on a hash table, the hash function for lines matters a lot. xdiff's hash is crap, it generates too many collisions on the linux-2.6 repository's source files. We use djb's hash function, which you can find in our RawTextComparator class[5]. We actually tested a number of hash functions using a test program [6].

I may try to port this myself, but it would be great if someone else beat me to it. :-)

[1] http://dev.eclipse.org/mhonarc/lists/jgit-dev/msg00897.html [2] http://bramcohen.livejournal.com/73318.html [3] http://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiff.java;hb=HEAD [4] http://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiffIndex.java;hb=HEAD [5] http://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextComparator.java;hb=HEAD [6] http://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit.pgm/src/org/eclipse/jgit/pgm/debug/TextHashFunctions.java;hb=HEAD

-- 
Shawn.