{"thread":{"id":"21637","subject":"[PATCH 0/2] diffcore-break optimizations","startedAt":"2009-11-16T15:53:32Z","lastAt":"2009-11-20T07:32:20Z","messageCount":6,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"127684","messageId":"20091116155331.GA30719@coredump.intra.peff.net","threadId":"21637","inReplyTo":null,"subject":"[PATCH 0/2] diffcore-break optimizations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-11-16T15:53:32Z","receivedAt":"2009-11-16T15:53:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On one of my more ridiculously gigantic repositories, I recently tried\nto make a commit that ran git out of memory while trying to commit. The\nrepository has about 3 gigabytes of data, and I made a small-ish change\nto every file. Pathological, yes, but I think we can do better than\nchugging for 5 minutes and dying.\n\nThe culprit turned out to be memory usage in diffcore-break, which is on\nby default for \"git status\" (and for the \"git commit\" template message).\nIt wants to have every changed blob in memory at once, which is just\nsilly.\n\nThe patches are:\n\n [1/2]: diffcore-break: free filespec data as we go\n\n This addresses the memory consumption issue. If you have enough\n memory, it doesn't actually yield a speed improvement, but nor does it\n show any slowdown for practical workloads.\n\n There is a theoretical slowdown when doing -B -M, because the rename\n phase has to re-fetch the blobs from the object store. However, I\n wasn't able to measure any slowdown for real-world cases (like \"git\n log --summary -M -B >/dev/null\" on git.git).\n\n I did manage to produce the slowdown on a pathological case: ten\n 20-megabyte files, each copied with a slight modification to another\n file, and then replaced with totally different contents (so each one\n will be broken and then trigger an inexact rename). That diff went\n from 16s to 17s.\n\n But I improved that and more with the next optimization.\n\n [2/2]: diffcore-break: save cnt_data for other phases\n\n We already do this in rename detection, and since they use the same\n data format, there is little reason not to do so. My pathological case\n above went from 17s down to 12s. I wasn't able to detect any speedup\n or slowdown for sane cases.\n\n So I doubt anybody will even notice this, but I think since we can\n address pathological cases, we might as well (and as you will see, the\n code change is quite small).\n\nAll of that being said, I was able to do my commit, but I still had to\nwait five minutes for it to chug through 3G of data. :) I am tempted to\nadd a \"quick\" mode to git-commit, but perhaps such a ridiculous case is\nrare enough not to worry about. I worked around it by writing my commit\nmessage separately and using \"git commit -F\".\n\n-Peff\n"},{"id":"127685","messageId":"20091116155625.GA30777@coredump.intra.peff.net","threadId":"21637","inReplyTo":"20091116155331.GA30719@coredump.intra.peff.net","subject":"[PATCH 1/2] diffcore-break: free filespec data as we go","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-11-16T15:56:25Z","receivedAt":"2009-11-16T15:56:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"As we look at each changed file and consider breaking it, we\nload the blob data and make a decision about whether to\nbreak, which is independent of any other blobs that might\nhave changed. However, we keep the data in memory while we\nconsider breaking all of the other files. Which means that\nboth versions of every file you are diffing are in memory at\nthe same time.\n\nThis patch instead frees the blob data as we finish with\neach file pair, leading to much lower memory usage.\n\nSigned-off-by: Jeff King \n---\nAs I noted in the cover letter, this can actually slow things down\nslightly for some pathological cases, but I think the reduced memory\nconsumption is worth it. I couldn't come up with a real-world case where\nit made any difference to the speed.\n\nOne other thing where _thought_ I might cause a slowdown was in fetching\nthe blobs for doing patch generation. But it turns out we drop the blobs\nalready after the diffcore merge, so they weren't living that long\nanyway.\n\n diffcore-break.c | 4 ++++\n 1 files changed, 4 insertions(+), 0 deletions(-)\n\ndiff --git a/diffcore-break.c b/diffcore-break.c\nindex d7097bb..15562e4 100644\n--- a/diffcore-break.c\n+++ b/diffcore-break.c\n@@ -204,12 +204,16 @@ 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\tdiff_free_filespec_data(p->one);\n+\t\t\t\tdiff_free_filespec_data(p->two);\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\tcontinue;\n \t\t\t}\n \t\t}\n+\t\tdiff_free_filespec_data(p->one);\n+\t\tdiff_free_filespec_data(p->two);\n \t\tdiff_q(&outq, p);\n \t}\n \tfree(q->queue);\n-- \n1.6.5.2.187.g29317\n"},{"id":"127686","messageId":"20091116160202.GB30777@coredump.intra.peff.net","threadId":"21637","inReplyTo":"20091116155331.GA30719@coredump.intra.peff.net","subject":"[PATCH 2/2] diffcore-break: save cnt_data for other phases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-11-16T16:02:02Z","receivedAt":"2009-11-16T16:02:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The \"break\" phase works by counting changes between two\nblobs with the same path. We do this by splitting the file\ninto chunks (or lines for text oriented files) and then\nkeeping a count of chunk hashes.\n\nThe \"rename\" phase counts changes between blobs at two\ndifferent paths. However, it uses the exact same set of\nchunk hashes (which are immutable for a given sha1).\n\nThe rename phase can therefore use the same hash data as\nbreak. Unfortunately, we were throwing this data away after\ncomputing it in the break phase. This patch instead attaches\nit to the filespec and lets it live through the rename\nphase, working under the assumption that most of the time\nthat breaks are being computed, renames will be too.\n\nWe only do this optimization for files which have actually\nbeen broken, as those ones will be candidates for rename\ndetection (and it is a time-space tradeoff, so we don't want\nto waste space keeping useless data).\n\nSigned-off-by: Jeff King \n---\nNote the two assumptions above:\n\n 1. If we are running break, we will probably run rename detection.\n\n 2. We are not looking for inexact copies, which could re-use data even\n for non-broken pairs.\n\nWe could test both of those assumptions by peeking at the other\ndiff_options that have been set up, but that would involve some code\nrestructuring. I'm also not sure it is worth it.\n\nFor (1), if we don't do rename detection, the next thing we will do is\nthe diffcore merge, which will then free the data anyway. So we are\nreally just carrying around the extra cnt_data through the break, and it\nis much smaller than the actual blob data.\n\nFor (2), keep in mind that this is just a heuristic. We may not have any\ngood rename candidates anyway, or we may find an exact rename. So it is\njust a guess as to which data might be useful. Keeping all the data for\nall pairs, broken or not, may be pushing us too far along the time-space\ntradeoff.\n\n diffcore-break.c | 6 +++---\n 1 files changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/diffcore-break.c b/diffcore-break.c\nindex 15562e4..3a7b60a 100644\n--- a/diffcore-break.c\n+++ b/diffcore-break.c\n@@ -69,7 +69,7 @@ static int should_break(struct diff_filespec *src,\n \t\treturn 0; /* we do not break too small filepair */\n \n \tif (diffcore_count_changes(src, dst,\n-\t\t\t\t NULL, NULL,\n+\t\t\t\t &src->cnt_data, &dst->cnt_data,\n \t\t\t\t 0,\n \t\t\t\t &src_copied, &literal_added))\n \t\treturn 0;\n@@ -204,8 +204,8 @@ 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\tdiff_free_filespec_data(p->one);\n-\t\t\t\tdiff_free_filespec_data(p->two);\n+\t\t\t\tdiff_free_filespec_blob(p->one);\n+\t\t\t\tdiff_free_filespec_blob(p->two);\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-- \n1.6.5.2.187.g29317\n"},{"id":"127697","messageId":"7vvdhanp4v.fsf@alter.siamese.dyndns.org","threadId":"21637","inReplyTo":"20091116160202.GB30777@coredump.intra.peff.net","subject":"Re: [PATCH 2/2] diffcore-break: save cnt_data for other phases","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-11-16T21:20:00Z","receivedAt":"2009-11-16T21:20:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> The \"break\" phase works by counting changes between two\n> blobs with the same path. We do this by splitting the file\n> into chunks (or lines for text oriented files) and then\n> keeping a count of chunk hashes.\n>\n> The \"rename\" phase counts changes between blobs at two\n> different paths. However, it uses the exact same set of\n> chunk hashes (which are immutable for a given sha1).\n>\n> The rename phase can therefore use the same hash data as\n> break. Unfortunately, we were throwing this data away after\n> computing it in the break phase. This patch instead attaches\n> it to the filespec and lets it live through the rename\n> phase, working under the assumption that most of the time\n> that breaks are being computed, renames will be too.\n\nThe change looks correct, but I initially got worried about your change\ninteracts badly with this part in estimate_similarity() around line 176:\n\n\tif (!src->cnt_data && diff_populate_filespec(src, 0))\n\t\treturn 0;\n\tif (!dst->cnt_data && diff_populate_filespec(dst, 0))\n\t\treturn 0;\n\nI think the reason why it (not your patch but the original code) felt a\nbit brittle is because the above if() statements know too much about the\ninternal of d-c-c (namely, it never looks at src->data when src->cnt_data\nis already available, so it is safe to leave src->data NULL).\n\nThe same logic suggests that the loop to build the matrix in\ndiffcore_rename() could free two->data at the end of the innermost loop.\n\nWe currently loop this way (around ll. 505-530):\n\n\tfor each two (i.e. rename destination candidate):\n \tfor each one (i.e. rename source candidate):\n \tcompute and record how similar one and two are\n\t\t\tfree one->data\n\t\tfree two->data\n\nAfter computing how similar \"one\" and something else is only once, we have\none->cnt_data so we won't need one->data (the same fact is exploited by\nyour patch for optimization), and that is why freeing one->data in the\ninnermost loop does not result in constant re-reading of the same blob\ndata when we iterate more than one rename destination. But the same logic\napplies to \"two\" and we should be able to free the blob data early to\nreduce the memory pressure.\n\nI dunno if it would give us measurable performance benefit, though.\n\nHere is the idea on top of your patch, but I think it can be applied\nindependently.\n\n diffcore-rename.c | 7 +++++--\n 1 files changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 63ac998..875ca81 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -523,10 +523,13 @@ void diffcore_rename(struct diff_options *options)\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\t/*\n+\t\t\t * Once we run estimate_similarity, \n+\t\t\t * We do not need the text anymore.\n+\t\t\t */\n \t\t\tdiff_free_filespec_blob(one);\n+\t\t\tdiff_free_filespec_blob(two);\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"},{"id":"127906","messageId":"20091119152234.GA6877@coredump.intra.peff.net","threadId":"21637","inReplyTo":"7vvdhanp4v.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] diffcore-break: save cnt_data for other phases","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-11-19T15:22:34Z","receivedAt":"2009-11-19T15:22:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 16, 2009 at 01:20:00PM -0800, Junio C Hamano wrote:\n\n> The change looks correct, but I initially got worried about your change\n> interacts badly with this part in estimate_similarity() around line 176:\n> \n> \tif (!src->cnt_data && diff_populate_filespec(src, 0))\n> \t\treturn 0;\n> \tif (!dst->cnt_data && diff_populate_filespec(dst, 0))\n> \t\treturn 0;\n> \n> I think the reason why it (not your patch but the original code) felt a\n> bit brittle is because the above if() statements know too much about the\n> internal of d-c-c (namely, it never looks at src->data when src->cnt_data\n> is already available, so it is safe to leave src->data NULL).\n\nNo, I am counting on those lines to actually optimize out the count\nlater on. But I agree it is a bit brittle. Probably a better design\nwould have been for diffcore_count_changes to simply call a new\n\"diff_filespec_hash\", which would assign to the cnt_data member and\nperform any optimizations, just as we do already with\ndiff_populate_filespec and the actual blob contents.\n\nI don't know if it is worth refactoring though. This is a pretty static\npart of the code these days, and what is there now is working.\n\n> The same logic suggests that the loop to build the matrix in\n> diffcore_rename() could free two->data at the end of the innermost loop.\n> \n> We currently loop this way (around ll. 505-530):\n> \n> \tfor each two (i.e. rename destination candidate):\n> \tfor each one (i.e. rename source candidate):\n> \tcompute and record how similar one and two are\n> \t\t\tfree one->data\n> \t\tfree two->data\n> \n> After computing how similar \"one\" and something else is only once, we have\n> one->cnt_data so we won't need one->data (the same fact is exploited by\n> your patch for optimization), and that is why freeing one->data in the\n> innermost loop does not result in constant re-reading of the same blob\n> data when we iterate more than one rename destination. But the same logic\n> applies to \"two\" and we should be able to free the blob data early to\n> reduce the memory pressure.\n> \n> I dunno if it would give us measurable performance benefit, though.\n> \n> Here is the idea on top of your patch, but I think it can be applied\n> independently.\n\nWith your patch, I shaved 0.2 seconds off of a 46-second rename\ndetection (one of my pathological \"rename and tweak the tags on a bunch\nof photos\" commits). To be fair, though, that commit is now quite old,\nso some of that CPU time was spent assembling delta chains.\n\nIt should also relieve memory pressure for large repositories, though\nthat is not nearly as big an issue for renames as for breaks, as we tend\nto have many fewer candidates.\n\nI think it is worth applying. Though perhaps the free-ing should simply\nhappen in estimate_similarity, which is the function that actually\npopulates the filespec.\n\nAlso, I don't see where we ever actually free the cnt_data. After we run\nthe whole O(n^2) loop, we should be able to drop cnt_data entirely. I\nthink in practice it doesn't matter all that much, since it isn't that\nbig, and afterwards we just generate the patch and exit (unless we are\ndoing diffcore-break, too, which will actually free all of the data).\n\n-Peff\n"},{"id":"127979","messageId":"7vtywp7it7.fsf@alter.siamese.dyndns.org","threadId":"21637","inReplyTo":"20091119152234.GA6877@coredump.intra.peff.net","subject":"Re: [PATCH 2/2] diffcore-break: save cnt_data for other phases","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-11-20T07:32:20Z","receivedAt":"2009-11-20T07:32:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I don't know if it is worth refactoring though.\n\nI would rather not touch it.\n\n> Also, I don't see where we ever actually free the cnt_data. After we run\n> the whole O(n^2) loop, we should be able to drop cnt_data entirely. I\n> think in practice it doesn't matter all that much, since it isn't that\n> big, and afterwards we just generate the patch and exit (unless we are\n> doing diffcore-break, too, which will actually free all of the data).\n\nOriginally, each phase of the diffcore pipeline was designed to be\nindependent from other phases, and keeping things in core was done as an\noptimization for smallish trees so that later phases in the diffcore\npipeline can reuse prepopulated data. If this were year 2006, I would\nhave said that keeping it in core would be better because we could add new\nphases after it later, even though there is nobody who uses cnt_data after\ndiffcore-rename in the diffcore pipeline right now,\n\nBut it seems that our performance is more than adequate without such\nkeeping-things-around for smallish trees anyway, and it is wiser to\noptimize for heavier workload. More importantly, nobody seems to be\nplanning new phases in the pipeline, so I agree it is a good idea to drop\ncnt_data once the rename detection phase is done with it.\n"}]}