{"thread":{"id":"33054","subject":"[PATCH] Avoid loading commits twice in log with diffs","startedAt":"2013-03-02T10:05:52Z","lastAt":"2013-03-28T13:51:14Z","messageCount":5,"participants":["Thomas Rast","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"210505","messageId":"3193c96cf5b036a91bc78b508b8b30ac87ca0f21.1362218700.git.trast@student.ethz.ch","threadId":"33054","inReplyTo":null,"subject":"[PATCH] Avoid loading commits twice in log with diffs","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-02T10:05:52Z","receivedAt":"2013-03-02T10:05:52Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"If you run a log with diffs (such as -p, --raw, --stat etc.) the\ncurrent code ends up loading many objects twice.  For example, for\n'log -3000 -p' my instrumentation said the objects loaded more than\nonce are distributed as follows:\n\n  2008 blob\n  2103 commit\n  2678 tree\n\nFixing blobs and trees will be harder, because those are really used\nwithin the diff engine and need some form of caching.\n\nHowever, fixing the commits is easy at least at the band-aid level.\nThey are triggered by log_tree_diff() invoking diff_tree_sha1() on\ncommits, which duly loads the specified object to dereference it to a\ntree.  Since log_tree_diff() knows that it works with commits and they\nmust have trees, we can simply pass through the trees.\n\nThis has a quite dramatic effect on log --raw, though only a\nnegligible impact on log -p:\n\nTest                      with patch        before\n--------------------------------------------------------------------\n4000.2: log --raw -3000   0.50(0.43+0.06)   0.54(0.46+0.06) +7.0%***\n4000.3: log -p -3000      2.34(2.20+0.13)   2.37(2.22+0.13) +1.2%\n--------------------------------------------------------------------\nSignificance hints:  '.' 0.1  '*' 0.05  '**' 0.01  '***' 0.001\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n log-tree.c | 8 +++++---\n 1 file changed, 5 insertions(+), 3 deletions(-)\n\ndiff --git a/log-tree.c b/log-tree.c\nindex eb1a1b4..277a38f 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -715,7 +715,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n {\n \tint showed_log;\n \tstruct commit_list *parents;\n-\tunsigned const char *sha1 = commit->object.sha1;\n+\tunsigned const char *sha1 = commit->tree->object.sha1;\n \n \tif (!opt->diff && !DIFF_OPT_TST(&opt->diffopt, EXIT_WITH_STATUS))\n \t\treturn 0;\n@@ -742,7 +742,8 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \t\t\t * parent, showing summary diff of the others\n \t\t\t * we merged _in_.\n \t\t\t */\n-\t\t\tdiff_tree_sha1(parents->item->object.sha1, sha1, \"\", &opt->diffopt);\n+\t\t\tparse_commit(parents->item);\n+\t\t\tdiff_tree_sha1(parents->item->tree->object.sha1, sha1, \"\", &opt->diffopt);\n \t\t\tlog_tree_diff_flush(opt);\n \t\t\treturn !opt->loginfo;\n \t\t}\n@@ -755,7 +756,8 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \tfor (;;) {\n \t\tstruct commit *parent = parents->item;\n \n-\t\tdiff_tree_sha1(parent->object.sha1, sha1, \"\", &opt->diffopt);\n+\t\tparse_commit(parent);\n+\t\tdiff_tree_sha1(parent->tree->object.sha1, sha1, \"\", &opt->diffopt);\n \t\tlog_tree_diff_flush(opt);\n \n \t\tshowed_log |= !opt->loginfo;\n-- \n1.8.2.rc1.393.ga167915\n"},{"id":"210521","messageId":"7va9qlc690.fsf@alter.siamese.dyndns.org","threadId":"33054","inReplyTo":"3193c96cf5b036a91bc78b508b8b30ac87ca0f21.1362218700.git.trast@student.ethz.ch","subject":"Re: [PATCH] Avoid loading commits twice in log with diffs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-03T07:06:03Z","receivedAt":"2013-03-03T07:06:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast <trast@student.ethz.ch> writes:\n\n> Test                      with patch        before\n> --------------------------------------------------------------------\n> 4000.2: log --raw -3000   0.50(0.43+0.06)   0.54(0.46+0.06) +7.0%***\n> 4000.3: log -p -3000      2.34(2.20+0.13)   2.37(2.22+0.13) +1.2%\n> --------------------------------------------------------------------\n> Significance hints:  '.' 0.1  '*' 0.05  '**' 0.01  '***' 0.001\n\nIt may be a silly question but what is a significance hint?\n\n> Signed-off-by: Thomas Rast <trast@student.ethz.ch>\n> ---\n>  log-tree.c | 8 +++++---\n>  1 file changed, 5 insertions(+), 3 deletions(-)\n>\n> diff --git a/log-tree.c b/log-tree.c\n> index eb1a1b4..277a38f 100644\n> --- a/log-tree.c\n> +++ b/log-tree.c\n> @@ -715,7 +715,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n>  {\n>  \tint showed_log;\n>  \tstruct commit_list *parents;\n> -\tunsigned const char *sha1 = commit->object.sha1;\n> +\tunsigned const char *sha1 = commit->tree->object.sha1;\n\nOverall I think this goes in the right direction and I can see why\nthe changes in later two hunks are correct, but I am not sure if we\ncan safely assume that the caller has parsed the incoming commit and\nwe have a good commit->tree here already.\n\nRight now, this static function has a single call-site in a public\nfunction log_tree_commit(), whose existing callers may all pass an\nalready parsed commit, but I feel somewhat uneasy to do the above\nwithout some mechanism in place (either parse it here or in the\ncaller if unparsed, or document that log_tree_commit() must be\ncalled with a parsed commit and perhaps add an assert there) to\nensure that the invariant is not broken in the future.\n\nThanks.\n\n>  \tif (!opt->diff && !DIFF_OPT_TST(&opt->diffopt, EXIT_WITH_STATUS))\n>  \t\treturn 0;\n> @@ -742,7 +742,8 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n>  \t\t\t * parent, showing summary diff of the others\n>  \t\t\t * we merged _in_.\n>  \t\t\t */\n> -\t\t\tdiff_tree_sha1(parents->item->object.sha1, sha1, \"\", &opt->diffopt);\n> +\t\t\tparse_commit(parents->item);\n> +\t\t\tdiff_tree_sha1(parents->item->tree->object.sha1, sha1, \"\", &opt->diffopt);\n>  \t\t\tlog_tree_diff_flush(opt);\n>  \t\t\treturn !opt->loginfo;\n>  \t\t}\n> @@ -755,7 +756,8 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n>  \tfor (;;) {\n>  \t\tstruct commit *parent = parents->item;\n>  \n> -\t\tdiff_tree_sha1(parent->object.sha1, sha1, \"\", &opt->diffopt);\n> +\t\tparse_commit(parent);\n> +\t\tdiff_tree_sha1(parent->tree->object.sha1, sha1, \"\", &opt->diffopt);\n>  \t\tlog_tree_diff_flush(opt);\n>  \n>  \t\tshowed_log |= !opt->loginfo;\n"},{"id":"210573","messageId":"871ubvtrj5.fsf@pctrast.inf.ethz.ch","threadId":"33054","inReplyTo":"7va9qlc690.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] Avoid loading commits twice in log with diffs","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-04T09:58:54Z","receivedAt":"2013-03-04T09:58:54Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Thomas Rast <trast@student.ethz.ch> writes:\n>\n>> Test                      with patch        before\n>> --------------------------------------------------------------------\n>> 4000.2: log --raw -3000   0.50(0.43+0.06)   0.54(0.46+0.06) +7.0%***\n>> 4000.3: log -p -3000      2.34(2.20+0.13)   2.37(2.22+0.13) +1.2%\n>> --------------------------------------------------------------------\n>> Significance hints:  '.' 0.1  '*' 0.05  '**' 0.01  '***' 0.001\n>\n> It may be a silly question but what is a significance hint?\n\nThat's from my still-not-rerolled perf improvements series from, ahem,\nages ago:\n\n  http://thread.gmane.org/gmane.comp.version-control.git/192884\n\nI stole the idea from R (and in fact use R to compute it).  The ***\ntells you that the probability of the 7% difference is attributable to\nchance only with 0.1% probability, or in other words, it's highly likely\nthat the difference is *not* down to chance.  On the other hand, note\nthat the p4000.3 measurements do not show a significant difference\n(significance hint is absent).\n\nThe statistical background: Assume that the two series of measurements\nare drawn from two normal distributions (possibly with different\nmean/variance).  Welch's t-test estimates the probability of the null\nhypothesis that the two distributions in fact had the same mean.  If you\ncan reject the null hypothesis, you have essentially proven that there's\n*some* difference in the timing runs.  (Hopefully for the better, and\nhopefully _not_ caused just by CPU scaling or such.)\n\nBy the way, in the above test Jakub pointed me at the Dumbbench perl\nmodule.  I've had a look at the ideas within, and I'll try to put some\nsample rejection along their lines into perf-lib.  However, several\nthings make the module itself rather deserve the name.  Most\nprominently, I can only get it to print timings to stdout in a fixed\nformat designed for human consumption.\n\n>> --- a/log-tree.c\n>> +++ b/log-tree.c\n>> @@ -715,7 +715,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n>>  {\n>>  \tint showed_log;\n>>  \tstruct commit_list *parents;\n>> -\tunsigned const char *sha1 = commit->object.sha1;\n>> +\tunsigned const char *sha1 = commit->tree->object.sha1;\n>\n> Overall I think this goes in the right direction and I can see why\n> the changes in later two hunks are correct, but I am not sure if we\n> can safely assume that the caller has parsed the incoming commit and\n> we have a good commit->tree here already.\n>\n> Right now, this static function has a single call-site in a public\n> function log_tree_commit(), whose existing callers may all pass an\n> already parsed commit, but I feel somewhat uneasy to do the above\n> without some mechanism in place (either parse it here or in the\n> caller if unparsed, or document that log_tree_commit() must be\n> called with a parsed commit and perhaps add an assert there) to\n> ensure that the invariant is not broken in the future.\n\nIn that case I'll reroll with the parsing -- it will have about the same\ncost as the assertion, since it'll just check ->object.parsed and\nreturn.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"212493","messageId":"f519e4af34cecd6aa4c905aa48288a9c2c841ae1.1364458249.git.trast@inf.ethz.ch","threadId":"33054","inReplyTo":"7va9qlc690.fsf@alter.siamese.dyndns.org","subject":"[PATCH v2] Avoid loading commits twice in log with diffs","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-28T08:19:34Z","receivedAt":"2013-03-28T08:19:34Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"If you run a log with diffs (such as -p, --raw, --stat etc.) the\ncurrent code ends up loading many objects twice.  For example, for\n'log -3000 -p' my instrumentation said the objects loaded more than\nonce are distributed as follows:\n\n  2008 blob\n  2103 commit\n  2678 tree\n\nFixing blobs and trees will be harder, because those are really used\nwithin the diff engine and need some form of caching.\n\nHowever, fixing the commits is easy at least at the band-aid level.\nThey are triggered by log_tree_diff() invoking diff_tree_sha1() on\ncommits, which duly loads the specified object to dereference it to a\ntree.  Since log_tree_diff() knows that it works with commits and they\nmust have trees, we can simply pass through the trees.\n\nWe add some parse_commit() calls.  The ones for the parents are\nrequired; we do not know at this stage if they have been looked at.\nThe one for the commit itself is pure paranoia, but has about the same\ncost as an assertion on commit->object.parsed.\n\nThis has a quite dramatic effect on log --raw, though only a\nnegligible impact on log -p:\n\nTest                      this tree         HEAD\n--------------------------------------------------------------------\n4000.2: log --raw -3000   0.50(0.43+0.06)   0.54(0.46+0.06) +7.0%***\n4000.3: log -p -3000      2.34(2.20+0.13)   2.37(2.22+0.13) +1.2%\n--------------------------------------------------------------------\nSignificance hints:  '.' 0.1  '*' 0.05  '**' 0.01  '***' 0.001\n\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\nSigned-off-by: Thomas Rast <trast@inf.ethz.ch>\n---\n\nAdjusted for the concern that the commit might not be parsed yet.  I\nthink it's now more paranoid than the original code, since we cannot\nlook at commit->parents without parsing.  But it's really an almost\nfree check.\n\n\n log-tree.c | 13 ++++++++++---\n 1 file changed, 10 insertions(+), 3 deletions(-)\n\ndiff --git a/log-tree.c b/log-tree.c\nindex 5dc45c4..8a34332 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -792,11 +792,14 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n {\n \tint showed_log;\n \tstruct commit_list *parents;\n-\tunsigned const char *sha1 = commit->object.sha1;\n+\tunsigned const char *sha1;\n \n \tif (!opt->diff && !DIFF_OPT_TST(&opt->diffopt, EXIT_WITH_STATUS))\n \t\treturn 0;\n \n+\tparse_commit(commit);\n+\tsha1 = commit->tree->object.sha1;\n+\n \t/* Root commit? */\n \tparents = commit->parents;\n \tif (!parents) {\n@@ -819,7 +822,9 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \t\t\t * parent, showing summary diff of the others\n \t\t\t * we merged _in_.\n \t\t\t */\n-\t\t\tdiff_tree_sha1(parents->item->object.sha1, sha1, \"\", &opt->diffopt);\n+\t\t\tparse_commit(parents->item);\n+\t\t\tdiff_tree_sha1(parents->item->tree->object.sha1,\n+\t\t\t\t       sha1, \"\", &opt->diffopt);\n \t\t\tlog_tree_diff_flush(opt);\n \t\t\treturn !opt->loginfo;\n \t\t}\n@@ -832,7 +837,9 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \tfor (;;) {\n \t\tstruct commit *parent = parents->item;\n \n-\t\tdiff_tree_sha1(parent->object.sha1, sha1, \"\", &opt->diffopt);\n+\t\tparse_commit(parent);\n+\t\tdiff_tree_sha1(parent->tree->object.sha1,\n+\t\t\t       sha1, \"\", &opt->diffopt);\n \t\tlog_tree_diff_flush(opt);\n \n \t\tshowed_log |= !opt->loginfo;\n-- \n1.8.2.351.g867a5da\n"},{"id":"212516","messageId":"20130328135114.GA12898@sigill.intra.peff.net","threadId":"33054","inReplyTo":"f519e4af34cecd6aa4c905aa48288a9c2c841ae1.1364458249.git.trast@inf.ethz.ch","subject":"Re: [PATCH v2] Avoid loading commits twice in log with diffs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-28T13:51:14Z","receivedAt":"2013-03-28T13:51:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 28, 2013 at 09:19:34AM +0100, Thomas Rast wrote:\n\n> However, fixing the commits is easy at least at the band-aid level.\n> They are triggered by log_tree_diff() invoking diff_tree_sha1() on\n> commits, which duly loads the specified object to dereference it to a\n> tree.  Since log_tree_diff() knows that it works with commits and they\n> must have trees, we can simply pass through the trees.\n\nReading this made me wonder if we could be doing the optimization at a\nlower level, by re-using objects that we have in our lookup_object cache\n(which would include the commit->tree peeling that you're optimizing\nhere).\n\nMy first instinct was to look at read_object_with_reference, but it's a\nbit general; for trees, we can indeed find the buffer/size pair. But for\ncommits, we must infer the size from the buffer (by using strlen). And\nfor blobs, we do not win at all, as we do not cache the blob contents.\n\nAnother option is for diff_tree_sha1 to use parse_tree_indirect. That\nwill pull the commit object from the cache and avoid re-parsing it, as\nwell as re-use any trees (although that should not happen much in a\nregular \"log\" traversal).\n\nThat patch looks something like:\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex ba01563..db454bc 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -269,27 +269,28 @@ int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const cha\n \n int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)\n {\n-\tvoid *tree1, *tree2;\n+\tstruct tree *tree1, *tree2;\n \tstruct tree_desc t1, t2;\n-\tunsigned long size1, size2;\n \tint retval;\n \n-\ttree1 = read_object_with_reference(old, tree_type, &size1, NULL);\n+\ttree1 = parse_tree_indirect(old);\n \tif (!tree1)\n \t\tdie(\"unable to read source tree (%s)\", sha1_to_hex(old));\n-\ttree2 = read_object_with_reference(new, tree_type, &size2, NULL);\n+\ttree2 = parse_tree_indirect(new);\n \tif (!tree2)\n \t\tdie(\"unable to read destination tree (%s)\", sha1_to_hex(new));\n-\tinit_tree_desc(&t1, tree1, size1);\n-\tinit_tree_desc(&t2, tree2, size2);\n+\tinit_tree_desc(&t1, tree1->buffer, tree1->size);\n+\tinit_tree_desc(&t2, tree2->buffer, tree2->size);\n \tretval = diff_tree(&t1, &t2, base, opt);\n \tif (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename()) {\n-\t\tinit_tree_desc(&t1, tree1, size1);\n-\t\tinit_tree_desc(&t2, tree2, size2);\n+\t\tinit_tree_desc(&t1, tree1->buffer, tree1->size);\n+\t\tinit_tree_desc(&t2, tree2->buffer, tree2->size);\n \t\ttry_to_follow_renames(&t1, &t2, base, opt);\n \t}\n-\tfree(tree1);\n-\tfree(tree2);\n+\t/*\n+\t * Note that we are now filling up our cache with extra tree data; we\n+\t * could potentially unparse the tree objects.\n+\t */\n \treturn retval;\n }\n \n\nbut it turns out to actually be slower! The problem is that parse_object\nwill actually re-check the sha1 on every object it reads, which\nread_object_with_reference will not do.\n\nUsing this hack:\n\ndiff --git a/object.c b/object.c\nindex 20703f5..361eb74 100644\n--- a/object.c\n+++ b/object.c\n@@ -195,6 +195,7 @@ struct object *parse_object_or_die(const unsigned char *sha1,\n \tdie(_(\"unable to parse object: %s\"), name ? name : sha1_to_hex(sha1));\n }\n \n+int parse_object_quick = 0;\n struct object *parse_object(const unsigned char *sha1)\n {\n \tunsigned long size;\n@@ -221,7 +222,8 @@ struct object *parse_object(const unsigned char *sha1)\n \n \tbuffer = read_sha1_file(sha1, &type, &size);\n \tif (buffer) {\n-\t\tif (check_sha1_signature(repl, buffer, size, typename(type)) < 0) {\n+\t\tif (!parse_object_quick &&\n+\t\t    check_sha1_signature(repl, buffer, size, typename(type)) < 0) {\n \t\t\tfree(buffer);\n \t\t\terror(\"sha1 mismatch %s\", sha1_to_hex(repl));\n \t\t\treturn NULL;\ndiff --git a/tree-diff.c b/tree-diff.c\nindex db454bc..4b55a1a 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -267,18 +267,23 @@ int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const cha\n \tq->nr = 1;\n }\n \n+/* hacky */\n+extern int parse_object_quick;\n+\n int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)\n {\n \tstruct tree *tree1, *tree2;\n \tstruct tree_desc t1, t2;\n \tint retval;\n \n+\tparse_object_quick = 1;\n \ttree1 = parse_tree_indirect(old);\n \tif (!tree1)\n \t\tdie(\"unable to read source tree (%s)\", sha1_to_hex(old));\n \ttree2 = parse_tree_indirect(new);\n \tif (!tree2)\n \t\tdie(\"unable to read destination tree (%s)\", sha1_to_hex(new));\n+\tparse_object_quick = 0;\n \tinit_tree_desc(&t1, tree1->buffer, tree1->size);\n \tinit_tree_desc(&t2, tree2->buffer, tree2->size);\n \tretval = diff_tree(&t1, &t2, base, opt);\n\nmy best-of-five \"git log --raw\" on git.git went from ~4.3s to ~4.1s,\nwhich is on par with what you saw.\n\n-Peff\n"}]}