diffcore-rename performance mode

[this is a resend of some comments I made deep in another thread on rename limiting; I wanted to get your comments, Junio, but I was afraid you didn't see it buried in the mess. If you have already read it and have nothing to say, just tell me to shut up.

I was able to get 1000% speedup on a (perhaps pathological) diff, and I suspect there may be more speedups possible in the spanhash lookups. So I think it's worth pursuing.]

Hmm. Actually, doing some profiling, it looks like about 75% of the time is spent not in the O(n^2) comparison, but in generating the hash fingerprints of each file.

There seems to be a serious performance problem in diffcore-rename. There is infrastructure to cache the "cnt_data" member of each filespec, but it never gets used because we immediately free the filespec data after use. Oops.

With this patch:

Jeff King <peff@peff.net> writes:

Yes, these early freeing of filespec_data() were introducd later specifically to address the memory usage issue.

That would be an interesting and relatively low-hanging optimization.

I think it was just a hash table with linear overflow (if your spot is occupied by somebody else, you look for the next available vacant spot -- works only if you do not ever delete items from the table) but sorry, I do not recall the rationale for picking that data structure. I vaguely recall I did some measurement between that and the usual "an array that is indexed with a hash value that holds heads of linked lists" and pointer chasing appeared quite cache-unfriendly to the point that it actually degraded performance, but did not try very hard to optimize it.

On Tue, Sep 18, 2007 at 01:49:50AM -0700, Junio C Hamano wrote:

OK, I will work up a patch. Is it worth making it configurable? Since it is a space-time tradeoff, if you are tight on memory, it might actually hurt performance. However, I have only looked at the numbers for my massive data set...I can produce memory usage numbers for the kernel, too.

I thought we were holding counts of hashes, in which case there _is_ no overflow. We only care if you hit the hash fingerprint or not. But perhaps I am mistaken...I will have to look more closely at the code.

-Peff

Jeff King <peff@peff.net> writes:

The raw hashval (the fingerprint recorded in struct spanhash) is further reduced and used as an index into spahash_top.data[]. So more than one hashval can try to sit in the same slot in spanhash_top.data[] array.

On Tue, Sep 18, 2007 at 01:58:17AM -0700, Junio C Hamano wrote:

Right, that's sort of what I was hinting at in the original message. Can we just make the hash table big enough to use the fingerprint hashes directly? It's going to use a bit more memory, but lookups should be very fast. I'll try to experiment and get some numbers.

-Peff

Jeff King <peff@peff.net> writes:

Thanks -- I vaguely recall large hash was disastrous for me (trashed cache), but that was on a different hardware, different time.

Hi,

On Tue, 18 Sep 2007, Jeff King wrote:

Yes, I think it would be worth making it configurable... For example, one of the machines I work on has only 128M.

Thanks, Dscho

On Tue, Sep 18, 2007 at 04:54:13AM -0400, Jeff King wrote:

And here are some kernel numbers. I measured performance of this script in the linux-2.6 repository:

#!/bin/sh

last=
git-tag | grep -v -- - | while read tag; do
  if test -n "$last"; then
    echo Diffing $last..$tag
    git-diff --raw -M -l0 $last $tag >/dev/null
  fi
  last=$tag
done

under the assumption that diffing between major revisions would give a good medium of diffs that would be large enough to show the n^2 rename behavior, but still small enough to be close to "everyday" usage.

I measured three different approaches:
  1. stock 'next' (stock)
  2. removing entirely the calls to diff_free_filespec_data (nofree)
  3. changing those free calls to free everything except cnt_data (somefree)

And I measured two things:
  1. user CPU time to complete
  2. peak memory usage

All numbers are warm-cache, and typical cases after multiple runs.

                 | stock | nofree | somefree
-----------------|---------------------------
user time (s)    | 76.78 | 16.96  | 46.26
peak memory (Kb) | 52300 | 66796  | 59156

The raw 'time' output is below:

stock: 76.78user 3.35system 1:20.72elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+166733minor)pagefaults 0swaps

nofree: 16.96user 1.46system 0:18.47elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+185353minor)pagefaults 0swaps

somefree: 46.26user 1.54system 0:47.94elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+178819minor)pagefaults 0swaps

So this is definitely worth pursuing, as it yields massive speedups even for regular repositories. And even the 'nofree' case only costs us 14M of extra memory (although it is a 27% increase, this just isn't that memory-hungry an endeavour for the sizes of changes we're talking about). And as Linus noted, now that we have a default rename limit, you're not likely to hit an explosion of memory usage.

What is most confusing is why the 'somefree' case performs so badly, since we should just be using the cnt_data. I'll see if gprof can shed any light on that. It would be nice to use it instead, since it will have much better memory usage in the face of large blobs (e.g., my pathological case that started this whole thread).

-Peff

On Tue, Sep 25, 2007 at 12:38:43PM -0400, Jeff King wrote:

OK, I found the problem. estimate_similarity calls diff_populate_filespec each time, even if we already have the cnt_data, which leads to recomputing the blob contents from deltas. Oops.

Fixing this, the correct numbers are:

                 | stock | nofree | old somefree | fixed somefree
-----------------|-----------------------------------------------
user time (s)    | 76.78 | 16.96  | 46.26        | 16.99
peak memory (Kb) | 52300 | 66796  | 59156        | 57328

So now we're at a 4.5x speedup for about 10% extra memory usage. Patch will follow.

-Peff

Jeff King wrote:

Nice work :)

Jeff King <peff@peff.net> writes:

Sounds good except when we happen to just hit the "memory working set exceeds physical memory" sweet spot. But the odds are much better than for "nofree".

On Tue, Sep 25, 2007 at 09:32:31PM +0200, David Kastrup wrote:

Of course, there is the possibility that it is the 10% that pushes you
into swap (or kills your ability to cache the entire pack in RAM).
However, this is probably not a big deal for two reasons:
  1. this is a 50M process handling the linux-2.6 repository. Other
     operations such as repacking already consume significantly more
     memory (git-repack -a allocates 290M on the same repo).
  2. I specifically turned off rename limiting (-l0) to do rename
     detection on these large-ish diffs.  If you have a machine which is
     on the cusp of swapping, then don't do that. Jumping from -l100
     (the default) to -l0 in my tests is _already_ moving you from 28M
     to 52M, a much larger jump.

-Peff

On Tue, 18 Sep 2007, Jeff King wrote:

I think this is a reasonable patch, but only now *after* we limit the rename matrix.

The whole reason for freeing the filespec data was to avoid exploding the memory usage, but now that we aggressively limit the number of renames in flight anyway, I think we can probably remove the code that frees the file data in between all the rename similarity analysis.

			Linus