From: Junio C Hamano <hidden> Date: 2016-06-15 22:43:35
Jeff King [off-list ref] writes:
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:
...
My 20-minute diff becomes a 2-minute diff. The downside is that the
memory usage is much increased (for obvious reasons, it should increase
by the dataset size, since we are keeping pointers to the data around --
in my case, around 1G extra).
Yes, these early freeing of filespec_data() were introducd later
specifically to address the memory usage issue.
However, keeping around _just_ the
cnt_data caused only about 100M of extra memory consumption (and gave
the same performance boost).
That would be an interesting and relatively low-hanging optimization.
The spanhash data structure is a bit confusing. At first, it looked like
we were doing a linear search for a matching hash, but it's not quite,
since we seem to start at some magic spot based on the hashval we're
looking up.
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.
From: Jeff King <hidden> Date: 2016-06-15 22:43:35
On Tue, Sep 18, 2007 at 01:49:50AM -0700, Junio C Hamano wrote:
quoted
However, keeping around _just_ the
cnt_data caused only about 100M of extra memory consumption (and gave
the same performance boost).
That would be an interesting and relatively low-hanging optimization.
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 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.
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
From: Jeff King <hidden> Date: 2016-06-15 22:43:36
On Tue, Sep 18, 2007 at 04:54:13AM -0400, Jeff King wrote:
quoted
quoted
However, keeping around _just_ the
cnt_data caused only about 100M of extra memory consumption (and gave
the same performance boost).
That would be an interesting and relatively low-hanging optimization.
I can produce memory usage numbers for the kernel, too.
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
From: Jeff King <hidden> Date: 2016-06-15 22:43:36
On Tue, Sep 25, 2007 at 12:38:43PM -0400, Jeff King wrote:
[...]
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
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
From: Andreas Ericsson <hidden> Date: 2016-06-15 22:43:36
Jeff King wrote:
On Tue, Sep 25, 2007 at 12:38:43PM -0400, Jeff King wrote:
quoted
[...]
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
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.
Nice work :)
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: David Kastrup <hidden> Date: 2016-06-15 22:43:36
Jeff King [off-list ref] writes:
On Tue, Sep 25, 2007 at 12:38:43PM -0400, Jeff King wrote:
quoted
[...]
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
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.
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".
--
David Kastrup
From: Jeff King <hidden> Date: 2016-06-15 22:43:36
On Tue, Sep 25, 2007 at 09:32:31PM +0200, David Kastrup wrote:
quoted
| 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.
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".
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