{"thread":{"id":"11760","subject":"git-revert is a memory hog","startedAt":"2008-01-27T17:27:48Z","lastAt":"2008-02-14T03:00:07Z","messageCount":24,"participants":["Adrian Bunk","Shawn O. Pearce","Jeff King","Linus Torvalds","Junio C Hamano","Luke Lu","David Kastrup"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"66679","messageId":"20080127172748.GD2558@does.not.exist","threadId":"11760","inReplyTo":null,"subject":"git-revert is a memory hog","fromName":"Adrian Bunk","fromEmail":"bunk@kernel.org","sentAt":"2008-01-27T17:27:48Z","receivedAt":"2008-01-27T17:27:48Z","isPatch":false,"sender":{"key":"bunk@kernel.org","avatar":null},"body":"I'm not sure whether this is already known, but when recently working \nfor some time from a computer with \"only\" 512 MB RAM I ran into the huge \nmemory usage of git-revert when it tries to revert old commits.\n\nExample (in Linus' kernel tree with git 1.5.3.8):\n\n<--  snip  -->\n\n$ git-revert d19fbe8a7\nAuto-merged drivers/input/input.c\nCONFLICT (content): Merge conflict in drivers/input/input.c\nAuto-merged include/linux/input.h\nCONFLICT (content): Merge conflict in include/linux/input.h\nAutomatic revert failed.  After resolving the conflicts,\nmark the corrected paths with 'git add <paths>' and commit the result.\n$ \n\n<--  snip  -->\n\nIn top you can see that this took > 800 MB of RAM !\n\nI don't know how easy it would be to implement, but shouldn't git-revert \nbe able to be as fast and less memory consuming as\n  git-show d19fbe8a7 | patch -p1 -R\n?\n\ncu\nAdrian\n\n-- \n\n       \"Is there not promise of rain?\" Ling Tan asked suddenly out\n        of the darkness. There had been need of rain for many days.\n       \"Only a promise,\" Lao Er said.\n                                       Pearl S. Buck - Dragon Seed\n"},{"id":"66681","messageId":"20080127173808.GX24004@spearce.org","threadId":"11760","inReplyTo":"20080127172748.GD2558@does.not.exist","subject":"Re: git-revert is a memory hog","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-01-27T17:38:08Z","receivedAt":"2008-01-27T17:38:08Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Adrian Bunk <bunk@kernel.org> wrote:\n> I'm not sure whether this is already known, but when recently working \n> for some time from a computer with \"only\" 512 MB RAM I ran into the huge \n> memory usage of git-revert when it tries to revert old commits.\n> \n> Example (in Linus' kernel tree with git 1.5.3.8):\n> \n> $ git-revert d19fbe8a7\n...\n> In top you can see that this took > 800 MB of RAM !\n> \n> I don't know how easy it would be to implement, but shouldn't git-revert \n> be able to be as fast and less memory consuming as\n>   git-show d19fbe8a7 | patch -p1 -R\n\nIts more like:\n\n\tgit-diff-tree -M d19fbe8a7^ d19fbe8a7 | git-apply -R --index\n\nIn other words its doing rename detection.  Its possible that the\nrename detector fired for added/removed paths and it took some\nsignificant amount of memory to figure out what was renamed.\nMaybe we hung onto stuff for too long, but it has to do rename\ndetection and that takes memory to store the matrix and file\ncontents.  Once memory is allocated by git we don't give it back\nto the kernel, even if we free'd it internally.\n\nIf you really are tight on memory and have to do a revert you can\nuse the above, but minus the -M, to setup the change, but you may\nrun into trouble if renames were involved.\n\n-- \nShawn.\n"},{"id":"66708","messageId":"20080128055933.GA13521@coredump.intra.peff.net","threadId":"11760","inReplyTo":"20080127172748.GD2558@does.not.exist","subject":"Re: git-revert is a memory hog","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-01-28T05:59:33Z","receivedAt":"2008-01-28T05:59:33Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jan 27, 2008 at 07:27:48PM +0200, Adrian Bunk wrote:\n\n> <--  snip  -->\n> \n> $ git-revert d19fbe8a7\n> Auto-merged drivers/input/input.c\n> CONFLICT (content): Merge conflict in drivers/input/input.c\n> Auto-merged include/linux/input.h\n> CONFLICT (content): Merge conflict in include/linux/input.h\n> Automatic revert failed.  After resolving the conflicts,\n> mark the corrected paths with 'git add <paths>' and commit the result.\n> $ \n> \n> <--  snip  -->\n> \n> In top you can see that this took > 800 MB of RAM !\n\nI tried to reproduce this, but my peak heap allocation was only around\n20MB. Is your repository fully packed? Not packed at all? Can you use\nvalgrind/massif to figure out where the memory is going?\n\n> I don't know how easy it would be to implement, but shouldn't git-revert \n> be able to be as fast and less memory consuming as\n>   git-show d19fbe8a7 | patch -p1 -R\n\nIn your case, the patch doesn't apply cleanly, so we end up doing a\n3-way merge (in my tests, it is git-merge-recursive which ends up taking\nup the memory).\n\n-Peff\n"},{"id":"66709","messageId":"20080128060149.GB13521@coredump.intra.peff.net","threadId":"11760","inReplyTo":"20080127173808.GX24004@spearce.org","subject":"Re: git-revert is a memory hog","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-01-28T06:01:49Z","receivedAt":"2008-01-28T06:01:49Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jan 27, 2008 at 12:38:08PM -0500, Shawn O. Pearce wrote:\n\n> >   git-show d19fbe8a7 | patch -p1 -R\n> \n> Its more like:\n> \n> \tgit-diff-tree -M d19fbe8a7^ d19fbe8a7 | git-apply -R --index\n> \n> In other words its doing rename detection.  Its possible that the\n> rename detector fired for added/removed paths and it took some\n> significant amount of memory to figure out what was renamed.\n\nIt's doubtful. There are only two files in that diff, and neither is a\ncandidate for rename detection.\n\n-Peff\n"},{"id":"66859","messageId":"alpine.LFD.1.00.0801300844170.28476@www.l.google.com","threadId":"11760","inReplyTo":"20080128055933.GA13521@coredump.intra.peff.net","subject":"Re: git-revert is a memory hog","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-29T21:51:09Z","receivedAt":"2008-01-29T21:51:09Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 28 Jan 2008, Jeff King wrote:\n> \n> I tried to reproduce this, but my peak heap allocation was only around\n> 20MB. Is your repository fully packed? Not packed at all? Can you use\n> valgrind/massif to figure out where the memory is going?\n\nI definitely can reproduce it, it's horrid.\n\nThis is from \"top\" fairly late in the game, but with the thing not even \ndone yet. Current git, pretty much fully (and fairly aggressively) packed \ncurrent kernel repo, and using \"diff.renamelmit=0\".\n\n\t4751 torvalds  20   0  852m 446m  47m R   72 22.4   2:46.58 git-merge-recur\n\nIt finally finished with time reporting:\n\n\t208.15user 3.50system 4:01.50elapsed 87%CPU (0avgtext+0avgdata 0maxresident)k\n\t238736inputs+4544outputs (8261major+280971minor)pagefaults 0swaps\n\nwhere those 280971 minor page faults are what largely indicates how much \nmemory it used (the technical term for that number is \"metric buttload of \nmemory\").\n\nBut I'm in Melbourne right now on my laptop,and probably won't be able to \ndebug this much. \n\n> In your case, the patch doesn't apply cleanly, so we end up doing a\n> 3-way merge (in my tests, it is git-merge-recursive which ends up taking\n> up the memory).\n\nIt is indeed git-merge-recursive. It just shouldn't take that much memory.\n\n\t\tLinus\n"},{"id":"66861","messageId":"7vk5lsmg6i.fsf@gitster.siamese.dyndns.org","threadId":"11760","inReplyTo":"alpine.LFD.1.00.0801300844170.28476@www.l.google.com","subject":"Re: git-revert is a memory hog","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-29T22:15:49Z","receivedAt":"2008-01-29T22:15:49Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Mon, 28 Jan 2008, Jeff King wrote:\n>> \n>> I tried to reproduce this, but my peak heap allocation was only around\n>> 20MB. Is your repository fully packed? Not packed at all? Can you use\n>> valgrind/massif to figure out where the memory is going?\n>\n> I definitely can reproduce it, it's horrid.\n>\n> This is from \"top\" fairly late in the game, but with the thing not even \n> done yet. Current git, pretty much fully (and fairly aggressively) packed \n> current kernel repo, and using \"diff.renamelmit=0\".\n>\n> \t4751 torvalds  20   0  852m 446m  47m R   72 22.4   2:46.58 git-merge-recur\n>\n> It finally finished with time reporting:\n>\n> \t208.15user 3.50system 4:01.50elapsed 87%CPU (0avgtext+0avgdata 0maxresident)k\n> \t238736inputs+4544outputs (8261major+280971minor)pagefaults 0swaps\n>\n> where those 280971 minor page faults are what largely indicates how much \n> memory it used (the technical term for that number is \"metric buttload of \n> memory\").\n>\n> But I'm in Melbourne right now on my laptop,and probably won't be able to \n> debug this much. \n>\n>> In your case, the patch doesn't apply cleanly, so we end up doing a\n>> 3-way merge (in my tests, it is git-merge-recursive which ends up taking\n>> up the memory).\n>\n> It is indeed git-merge-recursive. It just shouldn't take that much memory.\n\nHmmmmm.  Obviously this depends on where you start your revert\nfrom, but that is not what I am getting.\n\n: gitster linux-2.6/test; git reset --hard\nHEAD is now at 0ba6c33... Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-2.6.25\n: gitster linux-2.6/test; /usr/bin/time git-revert d19fbe8a7\nAuto-merged drivers/input/input.c\nCONFLICT (content): Merge conflict in drivers/input/input.c\nAuto-merged include/linux/input.h\nCONFLICT (content): Merge conflict in include/linux/input.h\nAutomatic revert failed.  After resolving the conflicts,\nmark the corrected paths with 'git add <paths>' or 'git rm <paths>' and commit the result.\nCommand exited with non-zero status 1\n1.08user 0.06system 0:01.14elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+19867minor)pagefaults 0swaps\n\nNow, a possible alternative (that produces an identical result)\nis not much better, because it ends up using merge-recursive as\nits core.\n\n: gitster linux-2.6/test; git reset --hard                                      HEAD is now at 0ba6c33... Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-2.6.25\n: gitster linux-2.6/test; rm -fr .dotest\n: gitster linux-2.6/test; /usr/bin/time sh -c 'git format-patch -R --binary --stdout -1 d19fbe8a7 | git am -3'\nApplying Input: prepare to sysfs integration\nerror: patch failed: drivers/input/input.c:27\nerror: drivers/input/input.c: patch does not apply\nerror: patch failed: include/linux/input.h:12\nerror: include/linux/input.h: patch does not apply\nUsing index info to reconstruct a base tree...\nFalling back to patching base and 3-way merge...\nAuto-merged drivers/input/input.c\nCONFLICT (content): Merge conflict in drivers/input/input.c\nAuto-merged include/linux/input.h\nCONFLICT (content): Merge conflict in include/linux/input.h\nFailed to merge in the changes.\nPatch failed at 0001.\nWhen you have resolved this problem run \"git-am -3 --resolved\".\nIf you would prefer to skip this patch, instead run \"git-am -3 --skip\".\nCommand exited with non-zero status 1\n0.52user 0.25system 0:00.75elapsed 103%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+41208minor)pagefaults 0swaps\n"},{"id":"66862","messageId":"20080129222007.GA3985@coredump.intra.peff.net","threadId":"11760","inReplyTo":"alpine.LFD.1.00.0801300844170.28476@www.l.google.com","subject":"Re: git-revert is a memory hog","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-01-29T22:20:07Z","receivedAt":"2008-01-29T22:20:07Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 30, 2008 at 08:51:09AM +1100, Linus Torvalds wrote:\n\n> I definitely can reproduce it, it's horrid.\n> \n> This is from \"top\" fairly late in the game, but with the thing not even \n> done yet. Current git, pretty much fully (and fairly aggressively) packed \n> current kernel repo, and using \"diff.renamelmit=0\".\n\nHrm, setting diff.renamelimit to 0 lets me reproduce (I thought I tried\nit before, but clearly not...).\n\nThe culprit seems to be diffcore-rename.c:476:\n\n  mx = xmalloc(sizeof(*mx) * num_create * num_src);\n\nWhere that ends up allocating about 450M. I think this is exactly the\nsort of case that renamelimit was introduced to address.\n\n-Peff\n"},{"id":"66864","messageId":"20080129223010.GA4314@coredump.intra.peff.net","threadId":"11760","inReplyTo":"20080129222007.GA3985@coredump.intra.peff.net","subject":"Re: git-revert is a memory hog","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-01-29T22:30:10Z","receivedAt":"2008-01-29T22:30:10Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 29, 2008 at 05:20:07PM -0500, Jeff King wrote:\n\n> The culprit seems to be diffcore-rename.c:476:\n> \n>   mx = xmalloc(sizeof(*mx) * num_create * num_src);\n> \n> Where that ends up allocating about 450M. I think this is exactly the\n> sort of case that renamelimit was introduced to address.\n\nBTW, a much easier way to see the problem is with:\n\n  git diff -M -l0 d19fbe8a76\n\nIt's just a _really_ old commit, and the rename detection has to work on\na large number of files.\n\n-Peff\n"},{"id":"66865","messageId":"7vfxwgmf87.fsf@gitster.siamese.dyndns.org","threadId":"11760","inReplyTo":"20080129222007.GA3985@coredump.intra.peff.net","subject":"Re: git-revert is a memory hog","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-29T22:36:24Z","receivedAt":"2008-01-29T22:36:24Z","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 Wed, Jan 30, 2008 at 08:51:09AM +1100, Linus Torvalds wrote:\n>\n>> I definitely can reproduce it, it's horrid.\n>> \n>> This is from \"top\" fairly late in the game, but with the thing not even \n>> done yet. Current git, pretty much fully (and fairly aggressively) packed \n>> current kernel repo, and using \"diff.renamelmit=0\".\n>\n> Hrm, setting diff.renamelimit to 0 lets me reproduce (I thought I tried\n> it before, but clearly not...).\n\nHmph.  But I wonder why this part does not trigger, even when\nyou have renamelimit set to 0.\n\n\t/*\n\t * This basically does a test for the rename matrix not\n\t * growing larger than a \"rename_limit\" square matrix, ie:\n\t *\n\t *    rename_dst_nr * rename_src_nr > rename_limit * rename_limit\n\t *\n\t * but handles the potential overflow case specially (and we\n\t * assume at least 32-bit integers)\n\t */\n\tif (rename_limit <= 0 || rename_limit > 32767)\n\t\trename_limit = 32767;\n\tif (rename_dst_nr > rename_limit && rename_src_nr > rename_limit)\n\t\tgoto cleanup;\n\tif (rename_dst_nr * rename_src_nr > rename_limit * rename_limit)\n\t\tgoto cleanup;\n\nI wonder if the second one for the overflow avoidance should be\nusing || instead of &&, though.\n"},{"id":"66867","messageId":"20080129224558.GA4586@coredump.intra.peff.net","threadId":"11760","inReplyTo":"7vfxwgmf87.fsf@gitster.siamese.dyndns.org","subject":"Re: git-revert is a memory hog","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-01-29T22:45:58Z","receivedAt":"2008-01-29T22:45:58Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 29, 2008 at 02:36:24PM -0800, Junio C Hamano wrote:\n\n> Hmph.  But I wonder why this part does not trigger, even when\n> you have renamelimit set to 0.\n> [...]\n> \tif (rename_limit <= 0 || rename_limit > 32767)\n> \t\trename_limit = 32767;\n\nIt does trigger; we set the limit to the obscenely high 32767. My matrix\nwas something like 8000x3500.\n\n> \tif (rename_dst_nr > rename_limit && rename_src_nr > rename_limit)\n> \t\tgoto cleanup;\n> \tif (rename_dst_nr * rename_src_nr > rename_limit * rename_limit)\n> \t\tgoto cleanup;\n> \n> I wonder if the second one for the overflow avoidance should be\n> using || instead of &&, though.\n\nHrm, yes, I think it can still overflow. (e.g., a 2 by 2^32-1\nsituation). But changing it to || isn't right, either; you would\ndisallow 1 by 101, which is quite do-able (and the normal case for -C\n-C, I would think).\n\n-Peff\n"},{"id":"66868","messageId":"alpine.LFD.1.00.0801300945310.3378@www.l.google.com","threadId":"11760","inReplyTo":"7vfxwgmf87.fsf@gitster.siamese.dyndns.org","subject":"Re: git-revert is a memory hog","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-29T22:49:44Z","receivedAt":"2008-01-29T22:49:44Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 29 Jan 2008, Junio C Hamano wrote:\n> \n> I wonder if the second one for the overflow avoidance should be\n> using || instead of &&, though.\n\nNo, we want to be able to handle the case where there is (for example) \njust one removed file, but lots of new ones. That's not expensive at all. \nSo we don't want to require that *both* the counts for removed and new \nfiles are low, we really want to check that we don't have too many \ncombinations together.\n\nBut  the\n\n        if (rename_limit <= 0 || rename_limit > 32767)\n                rename_limit = 32767;\n\nwhich is there purely to avoid overflow in 32-bit multiplication should \nprobably be changed to be more reasonable. We'll never want to try to do a \nmatrix that is really 32k * 32k in size, even if we can calculate its size \n;)\n\nSo maybe we should just make that hard limit more reasonable. 100x100 was \ntoo small, but a 1000x1000 matrix might be acceptable.\n\nOr, better yet (which was what I was hoping for originally), we'd just \nmake the inexact rename detection be linear-size/time rather than O(m*n). \nBut those patches never really came together, so we do need to limit it \nmore aggressively.\n\n\t\tLinus\n"},{"id":"66869","messageId":"20080129225123.GB4586@coredump.intra.peff.net","threadId":"11760","inReplyTo":"20080129224558.GA4586@coredump.intra.peff.net","subject":"Re: git-revert is a memory hog","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-01-29T22:51:23Z","receivedAt":"2008-01-29T22:51:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 29, 2008 at 05:45:58PM -0500, Jeff King wrote:\n\n> > \tif (rename_dst_nr > rename_limit && rename_src_nr > rename_limit)\n> > \t\tgoto cleanup;\n> \n> Hrm, yes, I think it can still overflow. (e.g., a 2 by 2^32-1\n> situation). But changing it to || isn't right, either; you would\n\nI think the correct solution is just:\n\n  /* check for overflow of square */\n  if (rename_dst_nr > ULONG_MAX / rename_src_nr)\n          goto cleanup;\n\n-Peff\n"},{"id":"66870","messageId":"7v7ihsmeg7.fsf@gitster.siamese.dyndns.org","threadId":"11760","inReplyTo":"7vfxwgmf87.fsf@gitster.siamese.dyndns.org","subject":"Re: git-revert is a memory hog","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-29T22:53:12Z","receivedAt":"2008-01-29T22:53:12Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Jeff King <peff@peff.net> writes:\n>\n>> Hrm, setting diff.renamelimit to 0 lets me reproduce (I thought I tried\n>> it before, but clearly not...).\n>\n> Hmph.  But I wonder why this part does not trigger, even when\n> you have renamelimit set to 0.\n>\n> \t/*\n> \t * This basically does a test for the rename matrix not\n> \t * growing larger than a \"rename_limit\" square matrix, ie:\n> \t *\n> \t *    rename_dst_nr * rename_src_nr > rename_limit * rename_limit\n> \t *\n> \t * but handles the potential overflow case specially (and we\n> \t * assume at least 32-bit integers)\n> \t */\n> \tif (rename_limit <= 0 || rename_limit > 32767)\n> \t\trename_limit = 32767;\n> \tif (rename_dst_nr > rename_limit && rename_src_nr > rename_limit)\n> \t\tgoto cleanup;\n> \tif (rename_dst_nr * rename_src_nr > rename_limit * rename_limit)\n> \t\tgoto cleanup;\n>\n> I wonder if the second one for the overflow avoidance should be\n> using || instead of &&, though.\n\nReverting d19fbe8a7 means coming up with a 3-way merge between\nd19fbe8a7^ and master as if d19fbe8a7 is their common ancestor.\n\n\"git diff --name-status d19fbe8a7 d19fbe8a7^\" shows only two\npaths changed.\n\n\"git diff --name-status d19fbe8a7 master\" shows 8558 new paths\nand 3756 deleted paths, which makes 32m paths pairs, that is\nstill lower than 32767 squared.\n\nIf your int is 64-bit, struct diff_score which is 4-int is\n16-byte long.  32m * 16 = 501,801,600.  That seems to match your\n450MB observation well.\n"},{"id":"66871","messageId":"20080129225428.GC4586@coredump.intra.peff.net","threadId":"11760","inReplyTo":"alpine.LFD.1.00.0801300945310.3378@www.l.google.com","subject":"Re: git-revert is a memory hog","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-01-29T22:54:28Z","receivedAt":"2008-01-29T22:54:28Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 30, 2008 at 09:49:44AM +1100, Linus Torvalds wrote:\n\n> But  the\n> \n>         if (rename_limit <= 0 || rename_limit > 32767)\n>                 rename_limit = 32767;\n> \n> which is there purely to avoid overflow in 32-bit multiplication should \n\nAh, right, that first conditional handles the overflow. Then what is the\nsecond one doing? If they are both larger than the rename limit, then\nwon't there square by definition be larger than the square of the rename\nlimit? I.e., can't we just get rid of the second conditional?\n\n> Or, better yet (which was what I was hoping for originally), we'd just \n> make the inexact rename detection be linear-size/time rather than O(m*n). \n> But those patches never really came together, so we do need to limit it \n> more aggressively.\n\nI had trouble getting the memory usage to a reasonable level. The hash\ntables were just getting enormous.\n\n-Peff\n"},{"id":"66872","messageId":"20080129225748.GD4586@coredump.intra.peff.net","threadId":"11760","inReplyTo":"7v7ihsmeg7.fsf@gitster.siamese.dyndns.org","subject":"Re: git-revert is a memory hog","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-01-29T22:57:49Z","receivedAt":"2008-01-29T22:57:49Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 29, 2008 at 02:53:12PM -0800, Junio C Hamano wrote:\n\n> If your int is 64-bit, struct diff_score which is 4-int is\n> 16-byte long.  32m * 16 = 501,801,600.  That seems to match your\n> 450MB observation well.\n\nYes, except for s/64-bit/32-bit/.\n\n-Peff\n"},{"id":"66873","messageId":"7vwspskynz.fsf@gitster.siamese.dyndns.org","threadId":"11760","inReplyTo":"7vfxwgmf87.fsf@gitster.siamese.dyndns.org","subject":"Re: git-revert is a memory hog","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-29T23:19:28Z","receivedAt":"2008-01-29T23:19:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Jeff King <peff@peff.net> writes:\n>\n>> On Wed, Jan 30, 2008 at 08:51:09AM +1100, Linus Torvalds wrote:\n>>\n>>> I definitely can reproduce it, it's horrid.\n>>> \n>>> This is from \"top\" fairly late in the game, but with the thing not even \n>>> done yet. Current git, pretty much fully (and fairly aggressively) packed \n>>> current kernel repo, and using \"diff.renamelmit=0\".\n>>\n>> Hrm, setting diff.renamelimit to 0 lets me reproduce (I thought I tried\n>> it before, but clearly not...).\n\nHow about this fairly obvious patch?\n\nWe used to record, for N=src deleted paths and M=dst created\npaths, (N x M) \"struct diff_score\" that records how similar each\nof the pair is, and picked the <src,dst> pairs that gives the\nbest match first, and then went on to worse matches.  This\nsorting is so that two destinations are both found to be similar\nto a single source, we can process the more similar one first,\nand when processing the second one, it can notice \"Ah, the\nsource I was planning to say I am a copy of is already taken by\nsomebody else\" and continue on to match himself with another\nsource with a lessor match (this matters to a change introduced\nbetween 1.5.3.X series and 1.5.4-rc, that lets the code to favor\nunused matches first and then falls back to using already used\nmatches).\n\nThis instead allocates and keeps only M records in core.  For\neach dst, we compute similarlity with all sources (so the number\nof similarity estimate computations we do is still N x M), but\nwe keep the best src for each dst.  This is essentially to save\nmemory drastically by giving up to come up with better pairing.\n\nI guess we could keep a handful best candidates per dst, instead\nof just one, to further improve on this approach, and such a\nchange should be fairly straightforward.\n\n---\n diffcore-rename.c |   46 +++++++++++++++++++++++-----------------------\n 1 files changed, 23 insertions(+), 23 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 3d37725..7e8fdcd 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -473,42 +473,42 @@ void diffcore_rename(struct diff_options *options)\n \tif (num_create * num_src > rename_limit * rename_limit)\n \t\tgoto cleanup;\n \n-\tmx = xmalloc(sizeof(*mx) * num_create * num_src);\n+\n+\tmx = xmalloc(sizeof(*mx) * num_create);\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n-\t\tint base = dst_cnt * num_src;\n \t\tstruct diff_filespec *two = rename_dst[i].two;\n+\t\tstruct diff_score *m;\n+\n \t\tif (rename_dst[i].pair)\n \t\t\tcontinue; /* dealt with exact match already. */\n+\n+\t\tm = &mx[dst_cnt];\n+\t\tm->dst = -1;\n \t\tfor (j = 0; j < rename_src_nr; j++) {\n \t\t\tstruct diff_filespec *one = rename_src[j].one;\n-\t\t\tstruct diff_score *m = &mx[base+j];\n-\t\t\tm->src = j;\n-\t\t\tm->dst = i;\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\tint score, name_score;\n+\t\t\tscore = estimate_similarity(one, two,\n+\t\t\t\t\t\t    minimum_score);\n+\t\t\tname_score = basename_same(one, two);\n+\t\t\tif (m->dst < 0 ||\n+\t\t\t    score > m->score ||\n+\t\t\t    (score == m->score &&\n+\t\t\t     name_score > m->name_score)) {\n+\t\t\t\tm->score = score;\n+\t\t\t\tm->name_score = name_score;\n+\t\t\t\tm->src = j;\n+\t\t\t\tm->dst = i;\n+\t\t\t}\n \t\t\tdiff_free_filespec_blob(one);\n \t\t}\n \t\t/* We do not need the text anymore */\n \t\tdiff_free_filespec_blob(two);\n \t\tdst_cnt++;\n \t}\n+\n \t/* cost matrix sorted by most to least similar pair */\n-\tqsort(mx, num_create * num_src, sizeof(*mx), score_compare);\n-\tfor (i = 0; i < num_create * num_src; i++) {\n-\t\tstruct diff_rename_dst *dst = &rename_dst[mx[i].dst];\n-\t\tstruct diff_filespec *src;\n-\t\tif (dst->pair)\n-\t\t\tcontinue; /* already done, either exact or fuzzy. */\n-\t\tif (mx[i].score < minimum_score)\n-\t\t\tbreak; /* there is no more usable pair. */\n-\t\tsrc = rename_src[mx[i].src].one;\n-\t\tif (src->rename_used)\n-\t\t\tcontinue;\n-\t\trecord_rename_pair(mx[i].dst, mx[i].src, mx[i].score);\n-\t\trename_count++;\n-\t}\n-\tfor (i = 0; i < num_create * num_src; i++) {\n+\tqsort(mx, num_create, sizeof(*mx), score_compare);\n+\tfor (i = 0; i < num_create; i++) {\n \t\tstruct diff_rename_dst *dst = &rename_dst[mx[i].dst];\n \t\tif (dst->pair)\n \t\t\tcontinue; /* already done, either exact or fuzzy. */\n"},{"id":"66874","messageId":"7vsl0gkx7w.fsf@gitster.siamese.dyndns.org","threadId":"11760","inReplyTo":"7vwspskynz.fsf@gitster.siamese.dyndns.org","subject":"Re: git-revert is a memory hog","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-29T23:50:43Z","receivedAt":"2008-01-29T23:50:43Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> This instead allocates and keeps only M records in core.  For\n> each dst, we compute similarlity with all sources (so the number\n> of similarity estimate computations we do is still N x M), but\n> we keep the best src for each dst.  This is essentially to save\n> memory drastically by giving up to come up with better pairing.\n>\n> I guess we could keep a handful best candidates per dst, instead\n> of just one, to further improve on this approach, and such a\n> change should be fairly straightforward.\n\nAn obvious side note to this patch is that if we are going to\nlimit us to only 1 source candidate per destination, we do not\neven have to allocate.  We can just do similarity one-by-one for\neach destination, and pair up with the best source as we go.\n\nI did not code it that way, primarily because that would\npermanently close the door to extend it back to keep multiple\ncandidates per dst, so that later ones that gets processed can\nnotice what happened to earlier ones.\n"},{"id":"66879","messageId":"7vprvkj58q.fsf_-_@gitster.siamese.dyndns.org","threadId":"11760","inReplyTo":"7vwspskynz.fsf@gitster.siamese.dyndns.org","subject":"[PATCH] Optimize rename detection for a huge diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-30T04:40:21Z","receivedAt":"2008-01-30T04:40:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When there are N deleted paths and M created paths, we used to\nallocate (N x M) \"struct diff_score\" that record how similar\neach of the pair is, and picked the <src,dst> pair that gives\nthe best match first, and then went on to process worse matches.\n\nThis sorting is done so that when two new files in the postimage\nthat are similar to the same file deleted from the preimage, we\ncan process the more similar one first, and when processing the\nsecond one, it can notice \"Ah, the source I was planning to say\nI am a copy of is already taken by somebody else\" and continue\non to match itself with another file in the preimage with a\nlessor match.  This matters to a change introduced between\n1.5.3.X series and 1.5.4-rc, that lets the code to favor unused\nmatches first and then falls back to using already used\nmatches.\n\nThis instead allocates and keeps only a handful rename source\ncandidates per new files in the postimage.  I.e. it makes the\nmemory requirement from O(N x M) to O(M).\n\nFor each dst, we compute similarlity with all sources (i.e. the\nnumber of similarity estimate computations is still O(N x M)),\nbut we keep handful best src candidates for each dst.\n\nI've run\n\n    git diff -l0 -M --name-status v2.6.$i v2.6.$(($i+1))\n\nwith and without patch for i=15..23.  There is one pair between\nv2.6.20 and v2.6.21 that gets different matching from this\nversion.\n\n    R093\tinclude/asm-arm/apm.h\tinclude/linux/apm-emulation.h\n    R093\tinclude/asm-mips/apm.h\tinclude/linux/apm-emulation.h\n\nWithout the patch, apm-emulation.h is found to be from asm-arm/arm.h;\nwith the patch, it is found to be from asm-mips/apm.h.  \n\nBut the difference between the ARM and MIPS versions is quite\nsmall, so I do not think we need to even call this an regression:\n\n    diff --git a/v2.6.20:include/asm-arm/apm.h b/v2.6.20:include/asm-mips/apm.h\n    index d09113b..4b99ffc 100644\n    --- a/v2.6.20:include/asm-arm/apm.h\n    +++ b/v2.6.20:include/asm-mips/apm.h\n    @@ -10,8 +10,8 @@\n      *\n      *\n      */\n    -#ifndef ARM_ASM_SA1100_APM_H\n    -#define ARM_ASM_SA1100_APM_H\n    +#ifndef MIPS_ASM_SA1100_APM_H\n    +#define MIPS_ASM_SA1100_APM_H\n\n     #include <linux/apm_bios.h>\n\nAnd the renamed diff is like this.\n\n    diff --git a/v2.6.20:include/asm-arm/apm.h b/v2.6.21:include/linux/apm-emulation.h\n    index d09113b..e6d8003 100644\n    --- a/v2.6.20:include/asm-arm/apm.h\n    +++ b/v2.6.21:include/linux/apm-emulation.h\n    @@ -7,11 +7,9 @@\n      * based on arch/arm/kernel/apm.c\n      * factor out the information needed by architectures to provide\n      * apm status\n    - *\n    - *\n      */\n    -#ifndef ARM_ASM_SA1100_APM_H\n    -#define ARM_ASM_SA1100_APM_H\n    +#ifndef __LINUX_APM_EMULATION_H\n    +#define __LINUX_APM_EMULATION_H\n\n     #include <linux/apm_bios.h>\n\n    @@ -61,4 +59,4 @@ extern void (*apm_get_power_status)(struct apm_power_info *);\n      */\n     void apm_queue_event(apm_event_t event);\n\n    -#endif\n    +#endif /* __LINUX_APM_EMULATION_H */\n\nBy looking at the above two diffs, I would say picking between\nARM and MIPS is equally good and the behaviour difference should\nnot matter in practice.\n\nRename-detecting diff without limit between v2.6.20 and v2.6.24\nproduces 991 renames and 57 copies, with or without the patch\n(the resulting pairs are somewhat deferent, but I've looked at a\nfew and the differences looked fairly small, like the above\nheader files).  The output from /usr/bin/time are:\n\n  (without patch)\n  28.84user 0.33system 0:29.35elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n  0inputs+0outputs (19major+90874minor)pagefaults 0swaps\n\n  (with patch)\n  24.81user 0.12system 0:24.93elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n  0inputs+0outputs (0major+36553minor)pagefaults 0swaps\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n\n---\n\n Junio C Hamano <gitster@pobox.com> writes:\n\n > How about this fairly obvious patch?\n\n This replaces the previous one by implementing \"keep the best N\n candidates per each destination\" as I hinted in my earlier\n message.  I suspect that we may want to optimize the O(N x M)\n part by stopping after finding enough number of good enough\n candidates for a given destination.\n\n diffcore-rename.c |   77 +++++++++++++++++++++++++++++++++++++++--------------\n 1 files changed, 57 insertions(+), 20 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 3d37725..90d06f0 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -223,6 +223,12 @@ static int score_compare(const void *a_, const void *b_)\n {\n \tconst struct diff_score *a = a_, *b = b_;\n \n+\t/* sink the unused ones to the bottom */\n+\tif (a->dst < 0)\n+\t\treturn (0 <= b->dst);\n+\telse if (b->dst < 0)\n+\t\treturn -1;\n+\n \tif (a->score == b->score)\n \t\treturn b->name_score - a->name_score;\n \n@@ -387,6 +393,22 @@ static int find_exact_renames(void)\n \treturn i;\n }\n \n+#define NUM_CANDIDATE_PER_DST 8\n+static void record_if_better(struct diff_score m[], struct diff_score *o)\n+{\n+\tint i, worst;\n+\n+\t/* find the worst one */\n+\tworst = 0;\n+\tfor (i = 1; i < NUM_CANDIDATE_PER_DST; i++)\n+\t\tif (score_compare(&m[i], &m[worst]) > 0)\n+\t\t\tworst = i;\n+\n+\t/* is it better than the worst one? */\n+\tif (score_compare(&m[worst], o) > 0)\n+\t\tm[worst] = *o;\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -473,50 +495,65 @@ void diffcore_rename(struct diff_options *options)\n \tif (num_create * num_src > rename_limit * rename_limit)\n \t\tgoto cleanup;\n \n-\tmx = xmalloc(sizeof(*mx) * num_create * num_src);\n+\tmx = xcalloc(num_create * NUM_CANDIDATE_PER_DST, sizeof(*mx));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n-\t\tint base = dst_cnt * num_src;\n \t\tstruct diff_filespec *two = rename_dst[i].two;\n+\t\tstruct diff_score *m;\n+\n \t\tif (rename_dst[i].pair)\n \t\t\tcontinue; /* dealt with exact match already. */\n+\n+\t\tm = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];\n+\t\tfor (j = 0; j < NUM_CANDIDATE_PER_DST; j++)\n+\t\t\tm[j].dst = -1;\n+\n \t\tfor (j = 0; j < rename_src_nr; j++) {\n \t\t\tstruct diff_filespec *one = rename_src[j].one;\n-\t\t\tstruct diff_score *m = &mx[base+j];\n-\t\t\tm->src = j;\n-\t\t\tm->dst = i;\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\tstruct diff_score this_src;\n+\t\t\tthis_src.score = estimate_similarity(one, two,\n+\t\t\t\t\t\t\t     minimum_score);\n+\t\t\tthis_src.name_score = basename_same(one, two);\n+\t\t\tthis_src.dst = i;\n+\t\t\tthis_src.src = j;\n+\t\t\trecord_if_better(m, &this_src);\n \t\t\tdiff_free_filespec_blob(one);\n \t\t}\n \t\t/* We do not need the text anymore */\n \t\tdiff_free_filespec_blob(two);\n \t\tdst_cnt++;\n \t}\n+\n \t/* cost matrix sorted by most to least similar pair */\n-\tqsort(mx, num_create * num_src, sizeof(*mx), score_compare);\n-\tfor (i = 0; i < num_create * num_src; i++) {\n-\t\tstruct diff_rename_dst *dst = &rename_dst[mx[i].dst];\n-\t\tstruct diff_filespec *src;\n+\tqsort(mx, dst_cnt * NUM_CANDIDATE_PER_DST, sizeof(*mx), score_compare);\n+\n+\tfor (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {\n+\t\tstruct diff_rename_dst *dst;\n+\n+\t\tif ((mx[i].dst < 0) ||\n+\t\t    (mx[i].score < minimum_score))\n+\t\t\tbreak; /* there is no more usable pair. */\n+\t\tdst = &rename_dst[mx[i].dst];\n \t\tif (dst->pair)\n \t\t\tcontinue; /* already done, either exact or fuzzy. */\n-\t\tif (mx[i].score < minimum_score)\n-\t\t\tbreak; /* there is no more usable pair. */\n-\t\tsrc = rename_src[mx[i].src].one;\n-\t\tif (src->rename_used)\n+\t\tif (rename_src[mx[i].src].one->rename_used)\n \t\t\tcontinue;\n \t\trecord_rename_pair(mx[i].dst, mx[i].src, mx[i].score);\n \t\trename_count++;\n \t}\n-\tfor (i = 0; i < num_create * num_src; i++) {\n-\t\tstruct diff_rename_dst *dst = &rename_dst[mx[i].dst];\n+\n+\tfor (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {\n+\t\tstruct diff_rename_dst *dst;\n+\n+\t\tif ((mx[i].dst < 0) ||\n+\t\t    (mx[i].score < minimum_score))\n+\t\t\tbreak; /* there is no more usable pair. */\n+\t\tdst = &rename_dst[mx[i].dst];\n \t\tif (dst->pair)\n \t\t\tcontinue; /* already done, either exact or fuzzy. */\n-\t\tif (mx[i].score < minimum_score)\n-\t\t\tbreak; /* there is no more usable pair. */\n \t\trecord_rename_pair(mx[i].dst, mx[i].src, mx[i].score);\n \t\trename_count++;\n \t}\n+\n \tfree(mx);\n \n  cleanup:\n"},{"id":"66898","messageId":"1AC39411-D78E-4663-A4E0-7B179AAA56EB@vicaya.com","threadId":"11760","inReplyTo":"7vprvkj58q.fsf_-_@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Optimize rename detection for a huge diff","fromName":"Luke Lu","fromEmail":"git@vicaya.com","sentAt":"2008-01-30T06:57:28Z","receivedAt":"2008-01-30T06:57:28Z","isPatch":true,"sender":{"key":"git@vicaya.com","avatar":null},"body":"On Jan 29, 2008, at 8:40 PM, Junio C Hamano wrote:\n> When there are N deleted paths and M created paths, we used to\n> allocate (N x M) \"struct diff_score\" that record how similar\n> each of the pair is, and picked the <src,dst> pair that gives\n> the best match first, and then went on to process worse matches.\n>\n> This sorting is done so that when two new files in the postimage\n> that are similar to the same file deleted from the preimage, we\n> can process the more similar one first, and when processing the\n> second one, it can notice \"Ah, the source I was planning to say\n> I am a copy of is already taken by somebody else\" and continue\n> on to match itself with another file in the preimage with a\n> lessor match.  This matters to a change introduced between\n> 1.5.3.X series and 1.5.4-rc, that lets the code to favor unused\n> matches first and then falls back to using already used\n> matches.\n>\n> This instead allocates and keeps only a handful rename source\n> candidates per new files in the postimage.  I.e. it makes the\n> memory requirement from O(N x M) to O(M).\n>\n> For each dst, we compute similarlity with all sources (i.e. the\n> number of similarity estimate computations is still O(N x M)),\n> but we keep handful best src candidates for each dst.\n\nI can think of cases where you'll throw away better candidates this  \nway. How about using a priority queue of size max(N, M)?\n\nI don't know about the details of the current algorithm but it seems  \nto me that using a naive Rabin Karp fingerprinting approach would not  \nuse too much memory: say L is total number of bytes of created files  \nand the fingerprint size S and hash size of 4 bytes. To keep track of  \nM files You only need to keep 8(additional 4 bytes as an index to the  \nfile names)*(L/S + M(for filenames)) plus some overhead for the hash  \ntable in memory. One pass through D (number of bytes of deleted  \nfiles) you can get the NxM scores. The score is defined as Wf * Mf +  \nWt, where Wf is the weight for fingerprinting match and Wt is the  \nweight for title match score; Mf is the fingerprint match score =  \n(number of matching fingerprints)/(number of fingerprints of original  \n(deleted) file). Wf and Wt can be tuned to boost exact basename match.\n\nBy pushing the scores into a priority queue you'll get the final top  \n(max(N, M) = K) scores in the end. The computation complexity is  \nreally O(D+L+(MxN)logK) and memory requirement O(L)\n\nYou can compute the entire linux source tree renaming (24K files and  \ntotal 260MB uncompressed) this way using only about 92MB of memory in  \n18 seconds (limited by hash lookup speed, assuming 15M lookups per  \nsecond based on my past experience).\n\n__Luke\n"},{"id":"66901","messageId":"EB54EAD7-EC20-4449-B1A1-DEC5EECD70B3@vicaya.com","threadId":"11760","inReplyTo":"1AC39411-D78E-4663-A4E0-7B179AAA56EB@vicaya.com","subject":"Re: [PATCH] Optimize rename detection for a huge diff","fromName":"Luke Lu","fromEmail":"git@vicaya.com","sentAt":"2008-01-30T07:24:13Z","receivedAt":"2008-01-30T07:24:13Z","isPatch":true,"sender":{"key":"git@vicaya.com","avatar":null},"body":"On Jan 29, 2008, at 10:57 PM, Luke Lu wrote:\n> On Jan 29, 2008, at 8:40 PM, Junio C Hamano wrote:\n>> When there are N deleted paths and M created paths, we used to\n>> allocate (N x M) \"struct diff_score\" that record how similar\n>> each of the pair is, and picked the <src,dst> pair that gives\n>> the best match first, and then went on to process worse matches.\n>>\n>> This sorting is done so that when two new files in the postimage\n>> that are similar to the same file deleted from the preimage, we\n>> can process the more similar one first, and when processing the\n>> second one, it can notice \"Ah, the source I was planning to say\n>> I am a copy of is already taken by somebody else\" and continue\n>> on to match itself with another file in the preimage with a\n>> lessor match.  This matters to a change introduced between\n>> 1.5.3.X series and 1.5.4-rc, that lets the code to favor unused\n>> matches first and then falls back to using already used\n>> matches.\n>>\n>> This instead allocates and keeps only a handful rename source\n>> candidates per new files in the postimage.  I.e. it makes the\n>> memory requirement from O(N x M) to O(M).\n>>\n>> For each dst, we compute similarlity with all sources (i.e. the\n>> number of similarity estimate computations is still O(N x M)),\n>> but we keep handful best src candidates for each dst.\n>\n> I can think of cases where you'll throw away better candidates this  \n> way. How about using a priority queue of size max(N, M)?\n>\n> I don't know about the details of the current algorithm but it  \n> seems to me that using a naive Rabin Karp fingerprinting approach  \n> would not use too much memory: say L is total number of bytes of  \n> created files and the fingerprint size S and hash size of 4 bytes.  \n> To keep track of M files You only need to keep 8(additional 4 bytes  \n> as an index to the file names)*(L/S + M(for filenames)) plus some  \n> overhead for the hash table in memory. One pass through D (number  \n> of bytes of deleted files) you can get the NxM scores. The score is  \n> defined as Wf * Mf + Wt, where Wf is the weight for fingerprinting  \n> match and Wt is the weight for title match score; Mf is the  \n> fingerprint match score = (number of matching fingerprints)/(number  \n> of fingerprints of original (deleted) file). Wf and Wt can be tuned  \n> to boost exact basename match.\n>\n> By pushing the scores into a priority queue you'll get the final  \n> top (max(N, M) = K) scores in the end. The computation complexity  \n> is really O(D+L+(MxN)logK) and memory requirement O(L)\n>\n> You can compute the entire linux source tree renaming (24K files  \n> and total 260MB uncompressed) this way using only about 92MB of  \n> memory in 18 seconds (limited by hash lookup speed, assuming 15M  \n> lookups per second based on my past experience).\n\nThe estimate is based on fingerprint size of 64 bytes and a 2.4GHz  \nC2D class Intel CPU, YMMV. One can trade off the accuracy for less  \nmemory by using larger fingerprint size and vice versa.\n\n__Luke\n"},{"id":"68621","messageId":"7vodalqj0s.fsf@gitster.siamese.dyndns.org","threadId":"11760","inReplyTo":"7vprvkj58q.fsf_-_@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Optimize rename detection for a huge diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-13T09:53:55Z","receivedAt":"2008-02-13T09:53:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Mon, 28 Jan 2008, Jeff King wrote:\n>> \n>> I tried to reproduce this, but my peak heap allocation was only around\n>> 20MB. Is your repository fully packed? Not packed at all? Can you use\n>> valgrind/massif to figure out where the memory is going?\n>\n> I definitely can reproduce it, it's horrid.\n>\n> This is from \"top\" fairly late in the game, but with the thing not even \n> done yet. Current git, pretty much fully (and fairly aggressively) packed \n> current kernel repo, and using \"diff.renamelmit=0\".\n>\n> \t4751 torvalds  20   0  852m 446m  47m R   72 22.4   2:46.58 git-merge-recur\n>\n> It finally finished with time reporting:\n>\n> \t208.15user 3.50system 4:01.50elapsed 87%CPU (0avgtext+0avgdata 0maxresident)k\n> \t238736inputs+4544outputs (8261major+280971minor)pagefaults 0swaps\n>\n> where those 280971 minor page faults are what largely indicates how much \n> memory it used (the technical term for that number is \"metric buttload of \n> memory\").\n\nWith a bit of tweak, now I am getting these numbers to the\nrename detection that used to spend 800MB (the peak I observed\nwas somewhere around 430MB).\n\n(after patch, in the kernel repository, master at 96b5a46)\n$ /usr/bin/time git-diff -M -l0 --name-status d19fbe8a7 master >/var/tmp/3\n157.20user 1.03system 2:38.72elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (32major+237315minor)pagefaults 0swaps\n\n$ /usr/bin/time git-diff -M -l0 --name-status d19fbe8a7 master >/var/tmp/4\n174.00user 2.73system 3:09.55elapsed 93%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (6106major+459314minor)pagefaults 0swaps\n\nSo it is not that much of an improvement, but it seems to help\nsomewhat.\n\nThe first hunk is about shrinking the diff_score structure;\nbefore the patch, it was O(NxM) where N and M are number of\nrename source and destination candidates, but after the patch it\nis now O(M), so this shrinkage should not matter, but score is\ncapped to MAX_SCORE (60000) and name_score is actually 0 or 1.\nWe cannot make it 1-bit unsigned bitfield as there is a qsort\ncomparison callback that does (b->name_score - a->name_score).\n\nWe would need to see where the remaining 400MB is going and try\nto shrink it, but this would be an improvement so I'll soon be\nmoving this to 'next'.\n\n---\n\n diffcore-rename.c |    6 +++---\n 1 files changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 90d06f0..99953e7 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -112,8 +112,8 @@ static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n struct diff_score {\n \tint src; /* index in rename_src */\n \tint dst; /* index in rename_dst */\n-\tint score;\n-\tint name_score;\n+\tunsigned short score;\n+\tshort name_score;\n };\n \n static int estimate_similarity(struct diff_filespec *src,\n@@ -393,7 +393,7 @@ static int find_exact_renames(void)\n \treturn i;\n }\n \n-#define NUM_CANDIDATE_PER_DST 8\n+#define NUM_CANDIDATE_PER_DST 4\n static void record_if_better(struct diff_score m[], struct diff_score *o)\n {\n \tint i, worst;\n"},{"id":"68624","messageId":"864pcd9n0e.fsf@lola.quinscape.zz","threadId":"11760","inReplyTo":"7vodalqj0s.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Optimize rename detection for a huge diff","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2008-02-13T10:19:45Z","receivedAt":"2008-02-13T10:19:45Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n\n> The first hunk is about shrinking the diff_score structure;\n> before the patch, it was O(NxM) where N and M are number of\n> rename source and destination candidates, but after the patch it\n> is now O(M), so this shrinkage should not matter, but score is\n> capped to MAX_SCORE (60000) and name_score is actually 0 or 1.\n> We cannot make it 1-bit unsigned bitfield as there is a qsort\n> comparison callback that does (b->name_score - a->name_score).\n\nHm?  Can't that be changed into\n\n(b->name_score > a->name_score ? 1 \n : b->name_score < a->name_score ? -1 : 0)\n\nor something?  Or perhaps just\n\n  ((int)b->name_score - (int)a->name_score)\n\nor so?\n\nIt sounds like a factor 2 is in question here, and that would seem like\nan easy fix?\n\n-- \nDavid Kastrup\n"},{"id":"68625","messageId":"7vk5l9qhnv.fsf@gitster.siamese.dyndns.org","threadId":"11760","inReplyTo":"864pcd9n0e.fsf@lola.quinscape.zz","subject":"Re: [PATCH] Optimize rename detection for a huge diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-13T10:23:16Z","receivedAt":"2008-02-13T10:23:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup <dak@gnu.org> writes:\n\n> Junio C Hamano <gitster@pobox.com> writes:\n> ...\n>> We cannot make it 1-bit unsigned bitfield as there is a qsort\n>> comparison callback that does (b->name_score - a->name_score).\n>\n> Hm?  Can't that be changed into ...\n\nSorry, my \"we cannot\" was misleading.  We do not have anything\nelse that we need to store that is 15-bit, so even if we can, it\nwon't gain us anything.\n"},{"id":"68700","messageId":"7vprv0medk.fsf@gitster.siamese.dyndns.org","threadId":"11760","inReplyTo":"7vodalqj0s.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Optimize rename detection for a huge diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-14T03:00:07Z","receivedAt":"2008-02-14T03:00:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> With a bit of tweak, now I am getting these numbers to the\n> rename detection that used to spend 800MB (the peak I observed\n> was somewhere around 430MB).\n>\n> (after patch, in the kernel repository, master at 96b5a46)\n> $ /usr/bin/time git-diff -M -l0 --name-status d19fbe8a7 master >/var/tmp/3\n> 157.20user 1.03system 2:38.72elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n> 0inputs+0outputs (32major+237315minor)pagefaults 0swaps\n>\n> (before patch, same diff)\n> $ /usr/bin/time git-diff -M -l0 --name-status d19fbe8a7 master >/var/tmp/4\n> 174.00user 2.73system 3:09.55elapsed 93%CPU (0avgtext+0avgdata 0maxresident)k\n> 0inputs+0outputs (6106major+459314minor)pagefaults 0swaps\n>\n> So it is not that much of an improvement, but it seems to help\n> somewhat.\n> ...\n> We would need to see where the remaining 400MB is going and try\n> to shrink it, but this would be an improvement so I'll soon be\n> moving this to 'next'.\n\nI noticed that massif reported diff_queue() very high in the\nlist, so came up with this patch on top of the previous ones.\n\n162.75user 1.92system 2:45.22elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+215490minor)pagefaults 0swaps\n\nStill not much of an improvement (10%, judging from the minor\nfault counts?), and it risks crashing if there is an unconvered\nfree() that frees a diff_filepair that was obtained from the\nbulk allocator.\n\n---\n alloc.c               |   33 ++++++++++++++++++++\n builtin-diff-tree.c   |    2 +-\n builtin-rev-parse.c   |    2 +-\n builtin-send-pack.c   |    2 +-\n builtin-show-branch.c |    2 +-\n cache.h               |    4 ++\n commit.c              |   14 ++++----\n diff.c                |    4 +-\n diffcore-break.c      |   12 ++++---\n diffcore-rename.c     |   80 +++++++++++++++++++++++++++++++++++-------------\n diffcore.h            |    4 ++\n http-push.c           |    2 +-\n revision.c            |    6 ++--\n upload-pack.c         |    2 +-\n 14 files changed, 124 insertions(+), 45 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 216c23a..08c2591 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -15,6 +15,8 @@\n #include \"tree.h\"\n #include \"commit.h\"\n #include \"tag.h\"\n+#include \"diff.h\"\n+#include \"diffcore.h\"\n \n #define BLOCKING 1024\n \n@@ -51,6 +53,35 @@ DEFINE_ALLOCATOR(commit, struct commit)\n DEFINE_ALLOCATOR(tag, struct tag)\n DEFINE_ALLOCATOR(object, union any_object)\n \n+#define DEFINE_FREEABLE_ALLOCATOR(name, type)\t\t\t\\\n+DEFINE_ALLOCATOR(name, type)\t\t\t\t\t\\\n+union freeable_##name {\t\t\t\t\t\t\\\n+\tunion freeable_##name *next;\t\t\t\t\\\n+\ttype body;\t\t\t\t\t\t\\\n+};\t\t\t\t\t\t\t\t\\\n+static union freeable_##name *name##_freepool;\t\t\t\\\n+type *alloc_freeable_##name##_node(void)\t\t\t\\\n+{\t\t\t\t\t\t\t\t\\\n+\tif (name##_freepool) {\t\t\t\t\t\\\n+\t\tunion freeable_##name *one = name##_freepool;\t\\\n+\t\tname##_freepool = one->next;\t\t\t\\\n+\t\tmemset(one, 0, sizeof(*one));\t\t\t\\\n+\t\treturn &(one->body);\t\t\t\t\\\n+\t}\t\t\t\t\t\t\t\\\n+\treturn alloc_##name##_node();\t\t\t\t\\\n+}\t\t\t\t\t\t\t\t\\\n+void free_##name##_node(type *it_)\t\t\t\t\\\n+{\t\t\t\t\t\t\t\t\\\n+\tunion freeable_##name *it = (union freeable_##name *)it_; \\\n+\tif (it) {\t\t\t\t\t\t\\\n+\t\tit->next = name##_freepool;\t\t\t\\\n+\t\tname##_freepool = it;\t\t\t\t\\\n+\t}\t\t\t\t\t\t\t\\\n+}\n+\n+DEFINE_FREEABLE_ALLOCATOR(commit_list, struct commit_list)\n+DEFINE_FREEABLE_ALLOCATOR(diff_filepair, struct diff_filepair)\n+\n #ifdef NO_C99_FORMAT\n #define SZ_FMT \"%u\"\n #else\n@@ -73,4 +104,6 @@ void alloc_report(void)\n \tREPORT(tree);\n \tREPORT(commit);\n \tREPORT(tag);\n+\tREPORT(commit_list);\n }\n+\ndiff --git a/builtin-diff-tree.c b/builtin-diff-tree.c\nindex 832797f..04f93f5 100644\n--- a/builtin-diff-tree.c\n+++ b/builtin-diff-tree.c\n@@ -36,7 +36,7 @@ static int diff_tree_stdin(char *line)\n \t\t/* Free the real parent list */\n \t\tfor (parents = commit->parents; parents; ) {\n \t\t\tstruct commit_list *tmp = parents->next;\n-\t\t\tfree(parents);\n+\t\t\tfree_commit_list_node(parents);\n \t\t\tparents = tmp;\n \t\t}\n \t\tcommit->parents = NULL;\ndiff --git a/builtin-rev-parse.c b/builtin-rev-parse.c\nindex b9af1a5..580ec51 100644\n--- a/builtin-rev-parse.c\n+++ b/builtin-rev-parse.c\n@@ -227,7 +227,7 @@ static int try_difference(const char *arg)\n \t\t\t\tstruct commit_list *n = exclude->next;\n \t\t\t\tshow_rev(REVERSED,\n \t\t\t\t\t exclude->item->object.sha1,NULL);\n-\t\t\t\tfree(exclude);\n+\t\t\t\tfree_commit_list_node(exclude);\n \t\t\t\texclude = n;\n \t\t\t}\n \t\t}\ndiff --git a/builtin-send-pack.c b/builtin-send-pack.c\nindex 8afb1d0..6a83258 100644\n--- a/builtin-send-pack.c\n+++ b/builtin-send-pack.c\n@@ -82,7 +82,7 @@ static void unmark_and_free(struct commit_list *list, unsigned int mark)\n \t\tstruct commit_list *temp = list;\n \t\ttemp->item->object.flags &= ~mark;\n \t\tlist = temp->next;\n-\t\tfree(temp);\n+\t\tfree_commit_list_node(temp);\n \t}\n }\n \ndiff --git a/builtin-show-branch.c b/builtin-show-branch.c\nindex 019abd3..0d7cf89 100644\n--- a/builtin-show-branch.c\n+++ b/builtin-show-branch.c\n@@ -38,7 +38,7 @@ static struct commit *pop_one_commit(struct commit_list **list_p)\n \tlist = *list_p;\n \tcommit = list->item;\n \t*list_p = list->next;\n-\tfree(list);\n+\tfree_commit_list_node(list);\n \treturn commit;\n }\n \ndiff --git a/cache.h b/cache.h\nindex 3867ba7..196a0d7 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -667,6 +667,10 @@ extern void *alloc_tree_node(void);\n extern void *alloc_commit_node(void);\n extern void *alloc_tag_node(void);\n extern void *alloc_object_node(void);\n+\n+extern struct commit_list *alloc_freeable_commit_list_node(void);\n+extern void free_commit_list_node(struct commit_list *);\n+\n extern void alloc_report(void);\n \n /* trace.c */\ndiff --git a/commit.c b/commit.c\nindex 8b8fb04..6696968 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -333,7 +333,7 @@ int parse_commit(struct commit *item)\n \n struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p)\n {\n-\tstruct commit_list *new_list = xmalloc(sizeof(struct commit_list));\n+\tstruct commit_list *new_list = alloc_freeable_commit_list_node();\n \tnew_list->item = item;\n \tnew_list->next = *list_p;\n \t*list_p = new_list;\n@@ -345,11 +345,11 @@ void free_commit_list(struct commit_list *list)\n \twhile (list) {\n \t\tstruct commit_list *temp = list;\n \t\tlist = temp->next;\n-\t\tfree(temp);\n+\t\tfree_commit_list_node(temp);\n \t}\n }\n \n-struct commit_list * insert_by_date(struct commit *item, struct commit_list **list)\n+struct commit_list *insert_by_date(struct commit *item, struct commit_list **list)\n {\n \tstruct commit_list **pp = list;\n \tstruct commit_list *p;\n@@ -381,7 +381,7 @@ struct commit *pop_most_recent_commit(struct commit_list **list,\n \tstruct commit_list *old = *list;\n \n \t*list = (*list)->next;\n-\tfree(old);\n+\tfree_commit_list_node(old);\n \n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n@@ -423,7 +423,7 @@ struct commit *pop_commit(struct commit_list **stack)\n \n \tif (top) {\n \t\t*stack = top->next;\n-\t\tfree(top);\n+\t\tfree_commit_list_node(top);\n \t}\n \treturn item;\n }\n@@ -568,7 +568,7 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)\n \n \t\tcommit = list->item;\n \t\tn = list->next;\n-\t\tfree(list);\n+\t\tfree_commit_list_node(list);\n \t\tlist = n;\n \n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n@@ -599,7 +599,7 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)\n \t\tstruct commit_list *n = list->next;\n \t\tif (!(list->item->object.flags & STALE))\n \t\t\tinsert_by_date(list->item, &result);\n-\t\tfree(list);\n+\t\tfree_commit_list_node(list);\n \t\tlist = n;\n \t}\n \treturn result;\ndiff --git a/diff.c b/diff.c\nindex cd8bc4d..63ac8db 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2433,7 +2433,7 @@ struct diff_filepair *diff_queue(struct diff_queue_struct *queue,\n \t\t\t\t struct diff_filespec *one,\n \t\t\t\t struct diff_filespec *two)\n {\n-\tstruct diff_filepair *dp = xcalloc(1, sizeof(*dp));\n+\tstruct diff_filepair *dp = alloc_freeable_diff_filepair_node();\n \tdp->one = one;\n \tdp->two = two;\n \tif (queue)\n@@ -2445,7 +2445,7 @@ void diff_free_filepair(struct diff_filepair *p)\n {\n \tfree_filespec(p->one);\n \tfree_filespec(p->two);\n-\tfree(p);\n+\tfree_diff_filepair_node(p);\n }\n \n /* This is different from find_unique_abbrev() in that\ndiff --git a/diffcore-break.c b/diffcore-break.c\nindex 31cdcfe..debd26d 100644\n--- a/diffcore-break.c\n+++ b/diffcore-break.c\n@@ -205,9 +205,11 @@ void diffcore_break(int break_score)\n \t\t\t\tdp->score = score;\n \t\t\t\tdp->broken_pair = 1;\n \n-\t\t\t\tfree(p); /* not diff_free_filepair(), we are\n-\t\t\t\t\t  * reusing one and two here.\n-\t\t\t\t\t  */\n+\t\t\t\t/*\n+\t\t\t\t * not diff_free_filepair(), we are\n+\t\t\t\t * reusing one and two here.\n+\t\t\t\t */\n+\t\t\t\tfree_diff_filepair_node(p);\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t}\n@@ -243,8 +245,8 @@ static void merge_broken(struct diff_filepair *p,\n \tdp->score = p->score;\n \tdiff_free_filespec_data(d->two);\n \tdiff_free_filespec_data(c->one);\n-\tfree(d);\n-\tfree(c);\n+\tfree_diff_filepair_node(d);\n+\tfree_diff_filepair_node(c);\n }\n \n void diffcore_merge_broken(void)\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 3d37725..5974362 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -112,8 +112,8 @@ static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n struct diff_score {\n \tint src; /* index in rename_src */\n \tint dst; /* index in rename_dst */\n-\tint score;\n-\tint name_score;\n+\tunsigned short score;\n+\tshort name_score;\n };\n \n static int estimate_similarity(struct diff_filespec *src,\n@@ -223,6 +223,12 @@ static int score_compare(const void *a_, const void *b_)\n {\n \tconst struct diff_score *a = a_, *b = b_;\n \n+\t/* sink the unused ones to the bottom */\n+\tif (a->dst < 0)\n+\t\treturn (0 <= b->dst);\n+\telse if (b->dst < 0)\n+\t\treturn -1;\n+\n \tif (a->score == b->score)\n \t\treturn b->name_score - a->name_score;\n \n@@ -387,6 +393,22 @@ static int find_exact_renames(void)\n \treturn i;\n }\n \n+#define NUM_CANDIDATE_PER_DST 4\n+static void record_if_better(struct diff_score m[], struct diff_score *o)\n+{\n+\tint i, worst;\n+\n+\t/* find the worst one */\n+\tworst = 0;\n+\tfor (i = 1; i < NUM_CANDIDATE_PER_DST; i++)\n+\t\tif (score_compare(&m[i], &m[worst]) > 0)\n+\t\t\tworst = i;\n+\n+\t/* is it better than the worst one? */\n+\tif (score_compare(&m[worst], o) > 0)\n+\t\tm[worst] = *o;\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -473,47 +495,61 @@ void diffcore_rename(struct diff_options *options)\n \tif (num_create * num_src > rename_limit * rename_limit)\n \t\tgoto cleanup;\n \n-\tmx = xmalloc(sizeof(*mx) * num_create * num_src);\n+\tmx = xcalloc(num_create * NUM_CANDIDATE_PER_DST, sizeof(*mx));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n-\t\tint base = dst_cnt * num_src;\n \t\tstruct diff_filespec *two = rename_dst[i].two;\n+\t\tstruct diff_score *m;\n+\n \t\tif (rename_dst[i].pair)\n \t\t\tcontinue; /* dealt with exact match already. */\n+\n+\t\tm = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];\n+\t\tfor (j = 0; j < NUM_CANDIDATE_PER_DST; j++)\n+\t\t\tm[j].dst = -1;\n+\n \t\tfor (j = 0; j < rename_src_nr; j++) {\n \t\t\tstruct diff_filespec *one = rename_src[j].one;\n-\t\t\tstruct diff_score *m = &mx[base+j];\n-\t\t\tm->src = j;\n-\t\t\tm->dst = i;\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\tstruct diff_score this_src;\n+\t\t\tthis_src.score = estimate_similarity(one, two,\n+\t\t\t\t\t\t\t     minimum_score);\n+\t\t\tthis_src.name_score = basename_same(one, two);\n+\t\t\tthis_src.dst = i;\n+\t\t\tthis_src.src = j;\n+\t\t\trecord_if_better(m, &this_src);\n \t\t\tdiff_free_filespec_blob(one);\n \t\t}\n \t\t/* We do not need the text anymore */\n \t\tdiff_free_filespec_blob(two);\n \t\tdst_cnt++;\n \t}\n+\n \t/* cost matrix sorted by most to least similar pair */\n-\tqsort(mx, num_create * num_src, sizeof(*mx), score_compare);\n-\tfor (i = 0; i < num_create * num_src; i++) {\n-\t\tstruct diff_rename_dst *dst = &rename_dst[mx[i].dst];\n-\t\tstruct diff_filespec *src;\n+\tqsort(mx, dst_cnt * NUM_CANDIDATE_PER_DST, sizeof(*mx), score_compare);\n+\n+\tfor (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {\n+\t\tstruct diff_rename_dst *dst;\n+\n+\t\tif ((mx[i].dst < 0) ||\n+\t\t    (mx[i].score < minimum_score))\n+\t\t\tbreak; /* there is no more usable pair. */\n+\t\tdst = &rename_dst[mx[i].dst];\n \t\tif (dst->pair)\n \t\t\tcontinue; /* already done, either exact or fuzzy. */\n-\t\tif (mx[i].score < minimum_score)\n-\t\t\tbreak; /* there is no more usable pair. */\n-\t\tsrc = rename_src[mx[i].src].one;\n-\t\tif (src->rename_used)\n+\t\tif (rename_src[mx[i].src].one->rename_used)\n \t\t\tcontinue;\n \t\trecord_rename_pair(mx[i].dst, mx[i].src, mx[i].score);\n \t\trename_count++;\n \t}\n-\tfor (i = 0; i < num_create * num_src; i++) {\n-\t\tstruct diff_rename_dst *dst = &rename_dst[mx[i].dst];\n+\n+\tfor (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {\n+\t\tstruct diff_rename_dst *dst;\n+\n+\t\tif ((mx[i].dst < 0) ||\n+\t\t    (mx[i].score < minimum_score))\n+\t\t\tbreak; /* there is no more usable pair. */\n+\t\tdst = &rename_dst[mx[i].dst];\n \t\tif (dst->pair)\n \t\t\tcontinue; /* already done, either exact or fuzzy. */\n-\t\tif (mx[i].score < minimum_score)\n-\t\t\tbreak; /* there is no more usable pair. */\n \t\trecord_rename_pair(mx[i].dst, mx[i].src, mx[i].score);\n \t\trename_count++;\n \t}\ndiff --git a/diffcore.h b/diffcore.h\nindex cc96c20..00aef4c 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -118,4 +118,8 @@ extern int diffcore_count_changes(struct diff_filespec *src,\n \t\t\t\t  unsigned long *src_copied,\n \t\t\t\t  unsigned long *literal_added);\n \n+/* alloc.c */\n+extern struct diff_filepair *alloc_freeable_diff_filepair_node(void);\n+extern void free_diff_filepair_node(struct diff_filepair *);\n+\n #endif\ndiff --git a/http-push.c b/http-push.c\nindex b2b410d..314141f 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1817,7 +1817,7 @@ static void unmark_and_free(struct commit_list *list, unsigned int mark)\n \t\tstruct commit_list *temp = list;\n \t\ttemp->item->object.flags &= ~mark;\n \t\tlist = temp->next;\n-\t\tfree(temp);\n+\t\tfree_commit_list_node(temp);\n \t}\n }\n \ndiff --git a/revision.c b/revision.c\nindex 6e85aaa..df9b062 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -571,7 +571,7 @@ static int limit_list(struct rev_info *revs)\n \t\tshow_early_output_fn_t show;\n \n \t\tlist = list->next;\n-\t\tfree(entry);\n+\t\tfree_commit_list_node(entry);\n \n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n@@ -752,7 +752,7 @@ static void prepare_show_merge(struct rev_info *revs)\n \twhile (bases) {\n \t\tstruct commit *it = bases->item;\n \t\tstruct commit_list *n = bases->next;\n-\t\tfree(bases);\n+\t\tfree_commit_list_node(bases);\n \t\tbases = n;\n \t\tit->object.flags |= UNINTERESTING;\n \t\tadd_pending_object(revs, &it->object, \"(merge-base)\");\n@@ -1472,7 +1472,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\tstruct commit *commit = entry->item;\n \n \t\trevs->commits = entry->next;\n-\t\tfree(entry);\n+\t\tfree_commit_list_node(entry);\n \n \t\tif (revs->reflog_info)\n \t\t\tfake_reflog_parent(revs->reflog_info, commit);\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 51e3ec4..86a4e7e 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -331,7 +331,7 @@ static int reachable(struct commit *want)\n \twhile (work) {\n \t\tstruct commit_list *list = work->next;\n \t\tstruct commit *commit = work->item;\n-\t\tfree(work);\n+\t\tfree_commit_list_node(work);\n \t\twork = list;\n \n \t\tif (commit->object.flags & THEY_HAVE) {\n"}]}