{"thread":{"id":"10018","subject":"[PATCH] diffcore-rename: cache file deltas","startedAt":"2007-09-25T19:29:42Z","lastAt":"2007-10-03T04:10:04Z","messageCount":5,"participants":["Jeff King","Junio C Hamano","Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"54027","messageId":"20070925192941.GA8564@coredump.intra.peff.net","threadId":"10018","inReplyTo":null,"subject":"[PATCH] diffcore-rename: cache file deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-09-25T19:29:42Z","receivedAt":"2007-09-25T19:29:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We find rename candidates by computing a fingerprint hash of\neach file, and then comparing those fingerprints. There are\ninherently O(n^2) comparisons, so it pays in CPU time to\nhoist the (rather expensive) computation of the fingerprint\nout of that loop (or to cache it once we have computed it once).\n\nPreviously, we didn't keep the filespec information around\nbecause then we had the potential to consume a great deal of\nmemory. However, instead of keeping all of the filespec\ndata, we can instead just keep the fingerprint.\n\nThis patch implements and uses diff_free_filespec_data_large\nto accomplish that goal. We also have to change\nestimate_similarity not to needlessly repopulate the\nfilespec data when we already have the hash.\n\nPractical tests showed 4.5x speedup for a 10% memory usage\nincrease.\n\nSigned-off-by: Jeff King \n---\nThe implementation is a little less nice than I would like, but I was\ntrying to be non-invasive. Specifically:\n\n - the name diff_free_filespec_data_large is horrible, but this is based\n on the fact that diff_free_filespec_data actually does too much (it\n frees the data _and_ some other auxiliary data). And renaming that\n would entail changing many callsites.\n\n - It seems that a better place to call diffcore_populate_filespec\n (rather than in estimate_similarity) would actually be in\n diffcore_count_changes (when we _know_ that we need to populate the\n contents data).\n\n - The hash_chars() should arguably be tied into\n diffcore_populate_filespec, which should have more of a \"what\n information do you want\" interface. I.e., the \"size_only\" parameter\n could be extended to a bitfield to say \"populate this, and I need the\n delta fingerprint, size, actual contents, etc\". Then callers could\n just use \"populate\" before looking at the filespec and it would\n lazily load whatever they needed.\n\nThis patch cuts my pathological case from 20 minutes to 2 minutes, which\nis a great improvement, but still unusable. However, now I should be\nable to get more useful numbers on what else can be sped up.\n\n diff.c | 7 ++++++-\n diffcore-rename.c | 7 ++++---\n diffcore.h | 1 +\n 3 files changed, 11 insertions(+), 4 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 2216d75..647bcf0 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -1654,7 +1654,7 @@ int diff_populate_filespec(struct diff_filespec *s, int size_only)\n \treturn 0;\n }\n \n-void diff_free_filespec_data(struct diff_filespec *s)\n+void diff_free_filespec_data_large(struct diff_filespec *s)\n {\n \tif (s->should_free)\n \t\tfree(s->data);\n@@ -1665,6 +1665,11 @@ void diff_free_filespec_data(struct diff_filespec *s)\n \t\ts->should_free = s->should_munmap = 0;\n \t\ts->data = NULL;\n \t}\n+}\n+\n+void diff_free_filespec_data(struct diff_filespec *s)\n+{\n+\tdiff_free_filespec_data_large(s);\n \tfree(s->cnt_data);\n \ts->cnt_data = NULL;\n }\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 41b35c3..4fc2000 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -184,7 +184,8 @@ static int estimate_similarity(struct diff_filespec *src,\n \tif (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n \t\treturn 0;\n \n-\tif (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0))\n+\tif ((!src->cnt_data && diff_populate_filespec(src, 0))\n+\t\t|| (!dst->cnt_data && diff_populate_filespec(dst, 0)))\n \t\treturn 0; /* error but caught downstream */\n \n \n@@ -377,10 +378,10 @@ 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\tdiff_free_filespec_data_large(one);\n \t\t}\n \t\t/* We do not need the text anymore */\n-\t\tdiff_free_filespec_data(two);\n+\t\tdiff_free_filespec_data_large(two);\n \t\tdst_cnt++;\n \t}\n \t/* cost matrix sorted by most to least similar pair */\ndiff --git a/diffcore.h b/diffcore.h\nindex eef17c4..4bf175b 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -48,6 +48,7 @@ extern void fill_filespec(struct diff_filespec *, const unsigned char *,\n \n extern int diff_populate_filespec(struct diff_filespec *, int);\n extern void diff_free_filespec_data(struct diff_filespec *);\n+extern void diff_free_filespec_data_large(struct diff_filespec *);\n extern int diff_filespec_is_binary(struct diff_filespec *);\n \n struct diff_filepair {\n-- \n1.5.3.2.1061.gc056e-dirty\n"},{"id":"54045","messageId":"7vy7eu4eos.fsf@gitster.siamese.dyndns.org","threadId":"10018","inReplyTo":"20070925192941.GA8564@coredump.intra.peff.net","subject":"Re: [PATCH] diffcore-rename: cache file deltas","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-25T21:29:07Z","receivedAt":"2007-09-25T21:29:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> We find rename candidates by computing a fingerprint hash of\n> each file, and then comparing those fingerprints. There are\n> inherently O(n^2) comparisons, so it pays in CPU time to\n> hoist the (rather expensive) computation of the fingerprint\n> out of that loop (or to cache it once we have computed it once).\n>\n> Previously, we didn't keep the filespec information around\n> because then we had the potential to consume a great deal of\n> memory. However, instead of keeping all of the filespec\n> data, we can instead just keep the fingerprint.\n>\n> This patch implements and uses diff_free_filespec_data_large\n> to accomplish that goal. We also have to change\n> estimate_similarity not to needlessly repopulate the\n> filespec data when we already have the hash.\n>\n> Practical tests showed 4.5x speedup for a 10% memory usage\n> increase.\n>\n> Signed-off-by: Jeff King \n\nVery nice.\n\n> The implementation is a little less nice than I would like, but I was\n> trying to be non-invasive. Specifically:\n>\n> - the name diff_free_filespec_data_large is horrible, but this is based\n> on the fact that diff_free_filespec_data actually does too much (it\n> frees the data _and_ some other auxiliary data). And renaming that\n> would entail changing many callsites.\n\nTrue. But we can rename it to diff_file_filespec_blob() and\nthat would perfectly well describe what it does. Will do so\nwhen applying if it is Ok to you.\n\n> - It seems that a better place to call diffcore_populate_filespec\n> (rather than in estimate_similarity) would actually be in\n> diffcore_count_changes (when we _know_ that we need to populate the\n> contents data).\n>\n> - The hash_chars() should arguably be tied into\n> diffcore_populate_filespec, which should have more of a \"what\n> information do you want\" interface. I.e., the \"size_only\" parameter\n> could be extended to a bitfield to say \"populate this, and I need the\n> delta fingerprint, size, actual contents, etc\". Then callers could\n> just use \"populate\" before looking at the filespec and it would\n> lazily load whatever they needed.\n\nBoth good points, but I agree with you that it is wise to do\nthat with a follow-up patch.\n"},{"id":"54047","messageId":"20070925214200.GA2886@sigill.intra.peff.net","threadId":"10018","inReplyTo":"7vy7eu4eos.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] diffcore-rename: cache file deltas","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-09-25T21:42:00Z","receivedAt":"2007-09-25T21:42:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 25, 2007 at 02:29:07PM -0700, Junio C Hamano wrote:\n\n> Very nice.\n\nThank you.\n\n> True. But we can rename it to diff_file_filespec_blob() and\n> that would perfectly well describe what it does. Will do so\n> when applying if it is Ok to you.\n\nYes, that is a much better name (assuming s/file/free). Please do change\nit.\n\n> > - The hash_chars() should arguably be tied into\n> > diffcore_populate_filespec, which should have more of a \"what\n> \n> Both good points, but I agree with you that it is wise to do\n> that with a follow-up patch.\n\nI think I will leave it, unless you are excited about the change. I feel\nlike there is a high chance of introducing some bug, and the benefit is\npurely stylistic at this point (i.e., the diff code isn't really\nchanging much at this point, so I think it should just be left alone).\n\n-Peff\n"},{"id":"54637","messageId":"alpine.LFD.0.999.0710021832520.3579@woody.linux-foundation.org","threadId":"10018","inReplyTo":"7vy7eu4eos.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] diffcore-rename: cache file deltas","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-03T01:36:50Z","receivedAt":"2007-10-03T01:36:50Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 25 Sep 2007, Junio C Hamano wrote:\n> >\n> > - the name diff_free_filespec_data_large is horrible, but this is based\n> > on the fact that diff_free_filespec_data actually does too much (it\n> > frees the data _and_ some other auxiliary data). And renaming that\n> > would entail changing many callsites.\n> \n> True. But we can rename it to diff_file_filespec_blob() and\n> that would perfectly well describe what it does. Will do so\n> when applying if it is Ok to you.\n\nWell, that renaming apparently never happened, and it's still called \ndiff_free_filespec_data_large() now that it's in master.\n\nThat said, I think this patch should make it into the maintenance branch \ntoo, renamed or not, since it's such a huge performance issue.\n\n\t\t\tLinus\n"},{"id":"54648","messageId":"7vbqbgj0tf.fsf@gitster.siamese.dyndns.org","threadId":"10018","inReplyTo":"alpine.LFD.0.999.0710021832520.3579@woody.linux-foundation.org","subject":"Re: [PATCH] diffcore-rename: cache file deltas","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-10-03T04:10:04Z","receivedAt":"2007-10-03T04:10:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Well, that renaming apparently never happened, and it's still called \n> diff_free_filespec_data_large() now that it's in master.\n>\n> That said, I think this patch should make it into the maintenance branch \n> too, renamed or not, since it's such a huge performance issue.\n\nThanks.\n"}]}