Re: [PATCH 1/2] blame: large-scale performance rewrite

From: David Kastrup <dak@gnu.org>
Date: Apr 26, 2014, 17:02 UTC
Message-ID: <87d2g481nb.fsf@fencepost.gnu.org>
In-Reply-To: <CAJo=hJs=ap=Ct_PzOsO=vHmDVMvUF+nvbB7b67bgnmug+Yrohg@mail.gmail.com>

Shawn Pearce <spearce@spearce.org> writes:

> Thanks for doing this. Unfortunately I can't read the patch itself as
> I am also trying to improve JGit's blame code for $DAY_JOB, and JGit
> is BSD licensed.

Actually, I'd have suggested asking $EMPLOYER to buy the rights for looking at the code, but as I wrote previously, I'd seriously doubt that he'd get his money's worth for use in a _Java_ implementation.

The C code I proposed is good for files with many small changes: I'd suggest benchmarking your JGit code with some of them. If the JGit is still dominated by unpacking, your implementation should be fine. The current C version instead thrashes around digging through its own all-purpose single linear list.

Here are two real-world test cases:

git://git.savannah.gnu.org/emacs.git git blame [-M / -C] src/xdisp.c

http://repo.or.cz/r/wortliste.git git blame [-M / -C] wortliste

The latter one is _really_ taking a severe hit from the O(n^2) algorithms. If your benchmarks for that one still point mostly to the unpacking, your jgit blame should be fine regarding the stuff I reimplemented.

-- 
David Kastrup