{"thread":{"id":"26375","subject":"Porting JGit HistogramDiff","startedAt":"2011-02-01T05:02:50Z","lastAt":"2011-02-01T05:02:50Z","messageCount":1,"participants":["Shawn Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"160156","messageId":"AANLkTimisConBkVqCxYjd-HKL0=grFtVT5=fbqakA59O@mail.gmail.com","threadId":"26375","inReplyTo":null,"subject":"Porting JGit HistogramDiff","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-02-01T05:02:50Z","receivedAt":"2011-02-01T05:02:50Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Jan 31, 2011 at 09:05, Junio C Hamano <gitster@pobox.com> wrote:\n>\n>  * Shawn Pearce says that the diff implementation JGit uses (histogram\n>   diff) performs way better than the xdiff implementation we use by\n>   default. It would be great if somebody can spend time taking a look at\n>   it and possibly port it back to C-git.\n\nThe idea that JGit's HistogramDiff is faster came from Robin Rosenburg in [1]:\n\n> $ time jgit log -M -p >jgit.txt\n>\n> real\t0m3.880s\n> user\t0m7.137s\n> sys\t0m0.807s\n>\n> $ time git log -M -p >cgit.txt\n>\n> real\t0m16.420s\n> user\t0m14.936s\n> sys\t0m0.899s\n>\n> Seems JGit beats the pants off C Git. A quick scans implies both version\n> produce correct diffs, but don't post this to the Git ML list just yet :)\n\n\nHistogramDiff is a variation of Patience Difference[2].  Within JGit\nit is implemented as two classes:\n\n  HistogramDiff[3] - the top level driver\n\n  HistogramDiffIndex[4] - the hash table used to count and match occurrences\n\n\nBecause its based on a hash table, the hash function for lines matters\na lot.  xdiff's hash is crap, it generates too many collisions on the\nlinux-2.6 repository's source files.  We use djb's hash function,\nwhich you can find in our RawTextComparator class[5].  We actually\ntested a number of hash functions using a test program [6].\n\nI may try to port this myself, but it would be great if someone else\nbeat me to it.  :-)\n\n\n[1]  http://dev.eclipse.org/mhonarc/lists/jgit-dev/msg00897.html\n[2]  http://bramcohen.livejournal.com/73318.html\n[3]  http://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiff.java;hb=HEAD\n[4]  http://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiffIndex.java;hb=HEAD\n[5]  http://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit/src/org/eclipse/jgit/diff/RawTextComparator.java;hb=HEAD\n[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\n\n-- \nShawn.\n"}]}