{"thread":{"id":"9912","subject":"diffcore-rename performance mode","startedAt":"2007-09-18T08:23:22Z","lastAt":"2007-09-25T19:52:20Z","messageCount":13,"participants":["Jeff King","Junio C Hamano","Johannes Schindelin","Linus Torvalds","Andreas Ericsson","David Kastrup"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"53414","messageId":"20070918082321.GA9883@coredump.intra.peff.net","threadId":"9912","inReplyTo":null,"subject":"diffcore-rename performance mode","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-09-18T08:23:22Z","receivedAt":"2007-09-18T08:23:22Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"[this is a resend of some comments I made deep in another thread on\nrename limiting; I wanted to get your comments, Junio, but I was afraid\nyou didn't see it buried in the mess. If you have already read it and\nhave nothing to say, just tell me to shut up.\n\nI was able to get 1000% speedup on a (perhaps pathological) diff, and I\nsuspect there may be more speedups possible in the spanhash lookups. So\nI think it's worth pursuing.]\n\n\nHmm. Actually, doing some profiling, it looks like about 75% of the time\nis spent not in the O(n^2) comparison, but in generating the hash\nfingerprints of each file.\n\nThere seems to be a serious performance problem in diffcore-rename.\nThere is infrastructure to cache the \"cnt_data\" member of each filespec,\nbut it never gets used because we immediately free the filespec data\nafter use. Oops.\n\nWith this patch:\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 6bde439..531a844 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -362,10 +362,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tm->score = estimate_similarity(one, two,\n \t\t\t\t\t\t       minimum_score);\n \t\t\tm->name_score = basename_same(one, two);\n-\t\t\tdiff_free_filespec_data(one);\n \t\t}\n-\t\t/* We do not need the text anymore */\n-\t\tdiff_free_filespec_data(two);\n \t\tdst_cnt++;\n \t}\n \t/* cost matrix sorted by most to least similar pair */\n\nMy 20-minute diff becomes a 2-minute diff. The downside is that the\nmemory usage is much increased (for obvious reasons, it should increase\nby the dataset size, since we are keeping pointers to the data around --\nin my case, around 1G extra).  However, keeping around _just_ the\ncnt_data caused only about 100M of extra memory consumption (and gave\nthe same performance boost).\n\nOf course, 2 minutes for a git-status is still way too slow, so there we\nmight still need a limiter. It also looks like 57% of my time is spent\nin spanhash_find, and another 29% in diffcore_count_changes.\n\nThe spanhash data structure is a bit confusing. At first, it looked like\nwe were doing a linear search for a matching hash, but it's not quite,\nsince we seem to start at some magic spot based on the hashval we're\nlooking up.\n\nBut it seems to be an array of (hash, count) pairs for each file. Is\nthere a reason not to use a hash table mapping hash -> count? That would\nmake insertion and lookup O(1), presumably at the cost of a bit more\nmemory (since each filespec would have the full table).\n\nJunio, can you shed some light on that decision?\n\n-Peff\n"},{"id":"53415","messageId":"7vsl5cwe6p.fsf@gitster.siamese.dyndns.org","threadId":"9912","inReplyTo":"20070918082321.GA9883@coredump.intra.peff.net","subject":"Re: diffcore-rename performance mode","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-18T08:49:50Z","receivedAt":"2007-09-18T08:49:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> There seems to be a serious performance problem in diffcore-rename.\n> There is infrastructure to cache the \"cnt_data\" member of each filespec,\n> but it never gets used because we immediately free the filespec data\n> after use. Oops.\n>\n> With this patch:\n> ...\n> My 20-minute diff becomes a 2-minute diff. The downside is that the\n> memory usage is much increased (for obvious reasons, it should increase\n> by the dataset size, since we are keeping pointers to the data around --\n> in my case, around 1G extra).\n\nYes, these early freeing of filespec_data() were introducd later\nspecifically to address the memory usage issue.\n\n> However, keeping around _just_ the\n> cnt_data caused only about 100M of extra memory consumption (and gave\n> the same performance boost).\n\nThat would be an interesting and relatively low-hanging optimization.\n\n> The spanhash data structure is a bit confusing. At first, it looked like\n> we were doing a linear search for a matching hash, but it's not quite,\n> since we seem to start at some magic spot based on the hashval we're\n> looking up.\n\nI think it was just a hash table with linear overflow (if your\nspot is occupied by somebody else, you look for the next\navailable vacant spot -- works only if you do not ever delete\nitems from the table) but sorry, I do not recall the rationale\nfor picking that data structure.  I vaguely recall I did some\nmeasurement between that and the usual \"an array that is indexed\nwith a hash value that holds heads of linked lists\" and pointer\nchasing appeared quite cache-unfriendly to the point that it\nactually degraded performance, but did not try very hard to\noptimize it.\n"},{"id":"53417","messageId":"20070918085413.GA11751@coredump.intra.peff.net","threadId":"9912","inReplyTo":"7vsl5cwe6p.fsf@gitster.siamese.dyndns.org","subject":"Re: diffcore-rename performance mode","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-09-18T08:54:13Z","receivedAt":"2007-09-18T08:54:13Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 18, 2007 at 01:49:50AM -0700, Junio C Hamano wrote:\n\n> > However, keeping around _just_ the\n> > cnt_data caused only about 100M of extra memory consumption (and gave\n> > the same performance boost).\n> \n> That would be an interesting and relatively low-hanging optimization.\n\nOK, I will work up a patch. Is it worth making it configurable? Since it\nis a space-time tradeoff, if you are tight on memory, it might actually\nhurt performance. However, I have only looked at the numbers for my\nmassive data set...I can produce memory usage numbers for the kernel,\ntoo.\n\n> I think it was just a hash table with linear overflow (if your\n> spot is occupied by somebody else, you look for the next\n> available vacant spot -- works only if you do not ever delete\n> items from the table) but sorry, I do not recall the rationale\n> for picking that data structure.  I vaguely recall I did some\n> measurement between that and the usual \"an array that is indexed\n> with a hash value that holds heads of linked lists\" and pointer\n> chasing appeared quite cache-unfriendly to the point that it\n> actually degraded performance, but did not try very hard to\n> optimize it.\n\nI thought we were holding counts of hashes, in which case there _is_ no\noverflow. We only care if you hit the hash fingerprint or not. But\nperhaps I am mistaken...I will have to look more closely at the code.\n\n-Peff\n"},{"id":"53425","messageId":"7vhclswdsm.fsf@gitster.siamese.dyndns.org","threadId":"9912","inReplyTo":"20070918085413.GA11751@coredump.intra.peff.net","subject":"Re: diffcore-rename performance mode","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-18T08:58:17Z","receivedAt":"2007-09-18T08:58:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> I thought we were holding counts of hashes, in which case there _is_ no\n> overflow.\n\nThe raw hashval (the fingerprint recorded in struct spanhash) is\nfurther reduced and used as an index into spahash_top.data[].\nSo more than one hashval can try to sit in the same slot in\nspanhash_top.data[] array.\n"},{"id":"53426","messageId":"20070918090105.GA11854@coredump.intra.peff.net","threadId":"9912","inReplyTo":"7vhclswdsm.fsf@gitster.siamese.dyndns.org","subject":"Re: diffcore-rename performance mode","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-09-18T09:01:05Z","receivedAt":"2007-09-18T09:01:05Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 18, 2007 at 01:58:17AM -0700, Junio C Hamano wrote:\n\n> > I thought we were holding counts of hashes, in which case there _is_ no\n> > overflow.\n> \n> The raw hashval (the fingerprint recorded in struct spanhash) is\n> further reduced and used as an index into spahash_top.data[].\n> So more than one hashval can try to sit in the same slot in\n> spanhash_top.data[] array.\n\nRight, that's sort of what I was hinting at in the original message. Can\nwe just make the hash table big enough to use the fingerprint hashes\ndirectly? It's going to use a bit more memory, but lookups should be\nvery fast. I'll try to experiment and get some numbers.\n\n-Peff\n"},{"id":"53431","messageId":"7v8x74wcxe.fsf@gitster.siamese.dyndns.org","threadId":"9912","inReplyTo":"20070918090105.GA11854@coredump.intra.peff.net","subject":"Re: diffcore-rename performance mode","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-18T09:17:01Z","receivedAt":"2007-09-18T09:17:01Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Tue, Sep 18, 2007 at 01:58:17AM -0700, Junio C Hamano wrote:\n>\n>> > I thought we were holding counts of hashes, in which case there _is_ no\n>> > overflow.\n>> \n>> The raw hashval (the fingerprint recorded in struct spanhash) is\n>> further reduced and used as an index into spahash_top.data[].\n>> So more than one hashval can try to sit in the same slot in\n>> spanhash_top.data[] array.\n>\n> Right, that's sort of what I was hinting at in the original message. Can\n> we just make the hash table big enough to use the fingerprint hashes\n> directly? It's going to use a bit more memory, but lookups should be\n> very fast. I'll try to experiment and get some numbers.\n\nThanks -- I vaguely recall large hash was disastrous for me\n(trashed cache), but that was on a different hardware, different\ntime.\n"},{"id":"53451","messageId":"Pine.LNX.4.64.0709181220130.28586@racer.site","threadId":"9912","inReplyTo":"20070918085413.GA11751@coredump.intra.peff.net","subject":"Re: diffcore-rename performance mode","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-09-18T11:20:52Z","receivedAt":"2007-09-18T11:20:52Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 18 Sep 2007, Jeff King wrote:\n\n> On Tue, Sep 18, 2007 at 01:49:50AM -0700, Junio C Hamano wrote:\n> \n> > > However, keeping around _just_ the cnt_data caused only about 100M \n> > > of extra memory consumption (and gave the same performance boost).\n> > \n> > That would be an interesting and relatively low-hanging optimization.\n> \n> OK, I will work up a patch. Is it worth making it configurable?\n\nYes, I think it would be worth making it configurable... For example, one \nof the machines I work on has only 128M.\n\nThanks,\nDscho\n"},{"id":"53507","messageId":"alpine.LFD.0.999.0709181510460.16478@woody.linux-foundation.org","threadId":"9912","inReplyTo":"20070918082321.GA9883@coredump.intra.peff.net","subject":"Re: diffcore-rename performance mode","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-09-18T22:12:48Z","receivedAt":"2007-09-18T22:12:48Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 18 Sep 2007, Jeff King wrote:\n> \n> With this patch:\n> \n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 6bde439..531a844 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -362,10 +362,7 @@ void diffcore_rename(struct diff_options *options)\n>  \t\t\tm->score = estimate_similarity(one, two,\n>  \t\t\t\t\t\t       minimum_score);\n>  \t\t\tm->name_score = basename_same(one, two);\n> -\t\t\tdiff_free_filespec_data(one);\n>  \t\t}\n> -\t\t/* We do not need the text anymore */\n> -\t\tdiff_free_filespec_data(two);\n>  \t\tdst_cnt++;\n>  \t}\n>  \t/* cost matrix sorted by most to least similar pair */\n> \n> My 20-minute diff becomes a 2-minute diff.\n\nI think this is a reasonable patch, but only now *after* we limit the \nrename matrix.\n\nThe whole reason for freeing the filespec data was to avoid exploding the \nmemory usage, but now that we aggressively limit the number of renames in \nflight anyway, I think we can probably remove the code that frees the file \ndata in between all the rename similarity analysis.\n\n\t\t\tLinus\n"},{"id":"54016","messageId":"20070925163843.GA22987@coredump.intra.peff.net","threadId":"9912","inReplyTo":"20070918085413.GA11751@coredump.intra.peff.net","subject":"Re: diffcore-rename performance mode","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-09-25T16:38:43Z","receivedAt":"2007-09-25T16:38:43Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 18, 2007 at 04:54:13AM -0400, Jeff King wrote:\n\n> > > However, keeping around _just_ the\n> > > cnt_data caused only about 100M of extra memory consumption (and gave\n> > > the same performance boost).\n> > \n> > That would be an interesting and relatively low-hanging optimization.\n> \n> I can produce memory usage numbers for the kernel, too.\n\nAnd here are some kernel numbers. I measured performance of this script\nin the linux-2.6 repository:\n\n#!/bin/sh\n\nlast=\ngit-tag | grep -v -- - | while read tag; do\n  if test -n \"$last\"; then\n    echo Diffing $last..$tag\n    git-diff --raw -M -l0 $last $tag >/dev/null\n  fi\n  last=$tag\ndone\n\nunder the assumption that diffing between major revisions would give a\ngood medium of diffs that would be large enough to show the n^2 rename\nbehavior, but still small enough to be close to \"everyday\" usage.\n\nI measured three different approaches:\n  1. stock 'next' (stock)\n  2. removing entirely the calls to diff_free_filespec_data (nofree)\n  3. changing those free calls to free everything except cnt_data (somefree)\n\nAnd I measured two things:\n  1. user CPU time to complete\n  2. peak memory usage\n\nAll numbers are warm-cache, and typical cases after multiple runs.\n\n                 | stock | nofree | somefree\n-----------------|---------------------------\nuser time (s)    | 76.78 | 16.96  | 46.26\npeak memory (Kb) | 52300 | 66796  | 59156\n\nThe raw 'time' output is below:\n\nstock:\n76.78user 3.35system 1:20.72elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+166733minor)pagefaults 0swaps\n\nnofree:\n16.96user 1.46system 0:18.47elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+185353minor)pagefaults 0swaps\n\nsomefree:\n46.26user 1.54system 0:47.94elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+178819minor)pagefaults 0swaps\n\nSo this is definitely worth pursuing, as it yields massive speedups even\nfor regular repositories. And even the 'nofree' case only costs us 14M\nof extra memory (although it is a 27% increase, this just isn't that\nmemory-hungry an endeavour for the sizes of changes we're talking\nabout). And as Linus noted, now that we have a default rename limit,\nyou're not likely to hit an explosion of memory usage.\n\nWhat is most confusing is why the 'somefree' case performs so badly,\nsince we should just be using the cnt_data. I'll see if gprof can shed\nany light on that. It would be nice to use it instead, since it will\nhave much better memory usage in the face of large blobs (e.g., my\npathological case that started this whole thread).\n\n-Peff\n"},{"id":"54021","messageId":"20070925190640.GA4613@coredump.intra.peff.net","threadId":"9912","inReplyTo":"20070925163843.GA22987@coredump.intra.peff.net","subject":"Re: diffcore-rename performance mode","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-09-25T19:06:40Z","receivedAt":"2007-09-25T19:06:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 25, 2007 at 12:38:43PM -0400, Jeff King wrote:\n\n>[...]\n>\n> What is most confusing is why the 'somefree' case performs so badly,\n> since we should just be using the cnt_data. I'll see if gprof can shed\n\nOK, I found the problem. estimate_similarity calls\ndiff_populate_filespec each time, even if we already have the cnt_data,\nwhich leads to recomputing the blob contents from deltas. Oops.\n\nFixing this, the correct numbers are:\n\n                 | stock | nofree | old somefree | fixed somefree\n-----------------|-----------------------------------------------\nuser time (s)    | 76.78 | 16.96  | 46.26        | 16.99\npeak memory (Kb) | 52300 | 66796  | 59156        | 57328\n\nSo now we're at a 4.5x speedup for about 10% extra memory usage. Patch\nwill follow.\n\n-Peff\n"},{"id":"54023","messageId":"46F95D0E.5090000@op5.se","threadId":"9912","inReplyTo":"20070925190640.GA4613@coredump.intra.peff.net","subject":"Re: diffcore-rename performance mode","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-25T19:10:06Z","receivedAt":"2007-09-25T19:10:06Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jeff King wrote:\n> On Tue, Sep 25, 2007 at 12:38:43PM -0400, Jeff King wrote:\n> \n>> [...]\n>>\n>> What is most confusing is why the 'somefree' case performs so badly,\n>> since we should just be using the cnt_data. I'll see if gprof can shed\n> \n> OK, I found the problem. estimate_similarity calls\n> diff_populate_filespec each time, even if we already have the cnt_data,\n> which leads to recomputing the blob contents from deltas. Oops.\n> \n> Fixing this, the correct numbers are:\n> \n>                  | stock | nofree | old somefree | fixed somefree\n> -----------------|-----------------------------------------------\n> user time (s)    | 76.78 | 16.96  | 46.26        | 16.99\n> peak memory (Kb) | 52300 | 66796  | 59156        | 57328\n> \n> So now we're at a 4.5x speedup for about 10% extra memory usage. Patch\n> will follow.\n> \n\nNice work :)\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n"},{"id":"54029","messageId":"86641y4k34.fsf@lola.quinscape.zz","threadId":"9912","inReplyTo":"20070925190640.GA4613@coredump.intra.peff.net","subject":"Re: diffcore-rename performance mode","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-09-25T19:32:31Z","receivedAt":"2007-09-25T19:32:31Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Tue, Sep 25, 2007 at 12:38:43PM -0400, Jeff King wrote:\n>\n>>[...]\n>>\n>> What is most confusing is why the 'somefree' case performs so badly,\n>> since we should just be using the cnt_data. I'll see if gprof can shed\n>\n> OK, I found the problem. estimate_similarity calls\n> diff_populate_filespec each time, even if we already have the cnt_data,\n> which leads to recomputing the blob contents from deltas. Oops.\n>\n> Fixing this, the correct numbers are:\n>\n>                  | stock | nofree | old somefree | fixed somefree\n> -----------------|-----------------------------------------------\n> user time (s)    | 76.78 | 16.96  | 46.26        | 16.99\n> peak memory (Kb) | 52300 | 66796  | 59156        | 57328\n>\n> So now we're at a 4.5x speedup for about 10% extra memory usage. Patch\n> will follow.\n\nSounds good except when we happen to just hit the \"memory working set\nexceeds physical memory\" sweet spot.  But the odds are much better\nthan for \"nofree\".\n\n-- \nDavid Kastrup\n"},{"id":"54034","messageId":"20070925195220.GA19549@segfault.peff.net","threadId":"9912","inReplyTo":"86641y4k34.fsf@lola.quinscape.zz","subject":"Re: diffcore-rename performance mode","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-09-25T19:52:20Z","receivedAt":"2007-09-25T19:52:20Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 25, 2007 at 09:32:31PM +0200, David Kastrup wrote:\n\n> >                  | stock | nofree | old somefree | fixed somefree\n> > -----------------|-----------------------------------------------\n> > user time (s)    | 76.78 | 16.96  | 46.26        | 16.99\n> > peak memory (Kb) | 52300 | 66796  | 59156        | 57328\n> >\n> > So now we're at a 4.5x speedup for about 10% extra memory usage. Patch\n> > will follow.\n> \n> Sounds good except when we happen to just hit the \"memory working set\n> exceeds physical memory\" sweet spot.  But the odds are much better\n> than for \"nofree\".\n\nOf course, there is the possibility that it is the 10% that pushes you\ninto swap (or kills your ability to cache the entire pack in RAM).\nHowever, this is probably not a big deal for two reasons:\n  1. this is a 50M process handling the linux-2.6 repository. Other\n     operations such as repacking already consume significantly more\n     memory (git-repack -a allocates 290M on the same repo).\n  2. I specifically turned off rename limiting (-l0) to do rename\n     detection on these large-ish diffs.  If you have a machine which is\n     on the cusp of swapping, then don't do that. Jumping from -l100\n     (the default) to -l0 in my tests is _already_ moving you from 28M\n     to 52M, a much larger jump.\n\n-Peff\n"}]}