{"thread":{"id":"35701","subject":"[PATCH 0/2] performance regression in mark_edges_uninteresting","startedAt":"2014-01-20T21:28:45Z","lastAt":"2014-01-21T22:49:06Z","messageCount":13,"participants":["Jeff King","Thomas Rast","Duy Nguyen","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"233413","messageId":"20140120212845.GA11451@sigill.intra.peff.net","threadId":"35701","inReplyTo":null,"subject":"[PATCH 0/2] performance regression in mark_edges_uninteresting","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-20T21:28:45Z","receivedAt":"2014-01-20T21:28:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This series fixes a rev-list performance regression in fbd4a70 (list-objects:\nmark more commits as edges in mark_edges_uninteresting, 2013-08-16). That\ncommit is a little tricky because it actually _knows_ it's trading off CPU for\na better packfile, but I think we're performing the tradeoff in too many\nplaces. See the second commit for details.\n\n [1/2]: t/perf: time rev-list with UNINTERESTING commits\n [2/2]: list-objects: only look at cmdline trees with edge_hint\n\nHere's t/perf/p0001 output that shows the problem:\n\n 0001.5: rev-list --objects $commit --not --all\n fbd4a703^ fbd4a703 HEAD\n 0.04(0.04+0.00) 0.28(0.27+0.00) +600.0% 0.04(0.04+0.00) +0.0%\n\n-Peff\n\nPS If you are wondering about the output format above, I had to munge it\nmanually to avoid giant 115-character lines. We should maybe teach the\nperf suite an alternate output format. :)\n"},{"id":"233414","messageId":"20140120213101.GA16095@sigill.intra.peff.net","threadId":"35701","inReplyTo":"20140120212845.GA11451@sigill.intra.peff.net","subject":"[PATCH 1/2] t/perf: time rev-list with UNINTERESTING commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-20T21:31:01Z","receivedAt":"2014-01-20T21:31:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We time a straight \"rev-list --all\" and its \"--object\"\ncounterpart, both going all the way to the root. However, we\ndo not time a partial history walk. This patch adds an\nextreme case: a walk over a very small slice of history, but\nwith a very large set of UNINTERESTING tips. This is similar\nto the connectivity check run by git on a small fetch, or\nthe walk done by any pre-receive hooks that want to check\nincoming commits.\n\nThis test reveals a performance regression in git v1.8.4.2,\ncaused by fbd4a70 (list-objects: mark more commits as edges\nin mark_edges_uninteresting, 2013-08-16):\n\nTest fbd4a703^ fbd4a703\n------------------------------------------------------------------------------------------\n0001.1: rev-list --all 0.69(0.67+0.02) 0.69(0.68+0.01) +0.0%\n0001.2: rev-list --all --objects 3.47(3.44+0.02) 3.48(3.44+0.03) +0.3%\n0001.4: rev-list $commit --not --all 0.04(0.04+0.00) 0.04(0.04+0.00) +0.0%\n0001.5: rev-list --objects $commit --not --all 0.04(0.03+0.00) 0.27(0.24+0.02) +575.0%\n\nSigned-off-by: Jeff King \n---\nSorry for the long lines in the commit message. I'm open to suggestions\non reformatting.\n\n t/perf/p0001-rev-list.sh | 17 +++++++++++++++++\n 1 file changed, 17 insertions(+)\n\ndiff --git a/t/perf/p0001-rev-list.sh b/t/perf/p0001-rev-list.sh\nindex 4f71a63..b7258a7 100755\n--- a/t/perf/p0001-rev-list.sh\n+++ b/t/perf/p0001-rev-list.sh\n@@ -14,4 +14,21 @@ test_perf 'rev-list --all --objects' '\n \tgit rev-list --all --objects >/dev/null\n '\n \n+test_expect_success 'create new unreferenced commit' '\n+\tgit checkout --detach HEAD &&\n+\techo content >>file &&\n+\tgit add file &&\n+\tgit commit -m detached &&\n+\tcommit=$(git rev-parse --verify HEAD) &&\n+\tgit checkout -\n+'\n+\n+test_perf 'rev-list $commit --not --all' '\n+\tgit rev-list $commit --not --all >/dev/null\n+'\n+\n+test_perf 'rev-list --objects $commit --not --all' '\n+\tgit rev-list --objects $commit --not --all >/dev/null\n+'\n+\n test_done\n-- \n1.8.5.2.500.g8060133\n"},{"id":"233415","messageId":"20140120213250.GB16095@sigill.intra.peff.net","threadId":"35701","inReplyTo":"20140120212845.GA11451@sigill.intra.peff.net","subject":"[PATCH 2/2] list-objects: only look at cmdline trees with edge_hint","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-20T21:32:50Z","receivedAt":"2014-01-20T21:32:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When rev-list is given a command-line like:\n\n git rev-list --objects $commit --not --all\n\nthe most accurate answer is the difference between the set\nof objects reachable from $commit and the set reachable from\nall of the existing refs. However, we have not historically\nprovided that answer, because it is very expensive to\ncalculate. We would have to open every tree of every commit\nin the entire history.\n\nInstead, we find the accurate set difference of the\nreachable commits, and then mark the trees at the boundaries\nas uninteresting. This misses objects which appear in the\ntrees of both the interesting commits and deep within the\nuninteresting history.\n\nCommit fbd4a70 (list-objects: mark more commits as edges in\nmark_edges_uninteresting, 2013-08-16) noticed that we miss\nthose objects during pack-objects, and added code to examine\nthe trees of all of the \"--not\" refs given on the\ncommand-line. Note that this is still not the complete set\ndifference, because we look only at the tips of the\ncommand-line arguments, not all of their reachable commits.\nBut it increases the set of boundary objects we consider,\nwhich is especially important for shallow fetches. So we\nare trading extra CPU time for a larger set of boundary\nobjects, which can improve the resulting pack size for a\n--thin pack.\n\nThis tradeoff probably makes sense in the context of\npack-objects, where we have set revs->edge_hint to have the\ntraversal feed us the set of boundary objects. For a\nregular rev-list, though, it is probably not a good\ntradeoff. It is true that it makes our list slightly closer\nto a true set difference, but it is a rare case where this\nis important. And because we do not have revs->edge_hint\nset, we do nothing useful with the larger set of boundary\nobjects.\n\nThis patch therefore ties the extra tree examination to the\nrevs->edge_hint flag; it is the presence of that flag that\nmakes the tradeoff worthwhile.\n\nHere is output from the p0001-rev-list showing the\nimprovement in performance:\n\nTest HEAD^ HEAD\n-----------------------------------------------------------------------------------------\n0001.1: rev-list --all 0.69(0.65+0.02) 0.69(0.66+0.02) +0.0%\n0001.2: rev-list --all --objects 3.22(3.19+0.03) 3.23(3.20+0.03) +0.3%\n0001.4: rev-list $commit --not --all 0.04(0.04+0.00) 0.04(0.04+0.00) +0.0%\n0001.5: rev-list --objects $commit --not --all 0.27(0.26+0.01) 0.04(0.04+0.00) -85.2%\n\nSigned-off-by: Jeff King \n---\n list-objects.c | 20 +++++++++++---------\n 1 file changed, 11 insertions(+), 9 deletions(-)\n\ndiff --git a/list-objects.c b/list-objects.c\nindex 6cbedf0..43ce1d9 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -162,15 +162,17 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)\n \t\t}\n \t\tmark_edge_parents_uninteresting(commit, revs, show_edge);\n \t}\n-\tfor (i = 0; i < revs->cmdline.nr; i++) {\n-\t\tstruct object *obj = revs->cmdline.rev[i].item;\n-\t\tstruct commit *commit = (struct commit *)obj;\n-\t\tif (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n-\t\t\tcontinue;\n-\t\tmark_tree_uninteresting(commit->tree);\n-\t\tif (revs->edge_hint && !(obj->flags & SHOWN)) {\n-\t\t\tobj->flags |= SHOWN;\n-\t\t\tshow_edge(commit);\n+\tif (revs->edge_hint) {\n+\t\tfor (i = 0; i < revs->cmdline.nr; i++) {\n+\t\t\tstruct object *obj = revs->cmdline.rev[i].item;\n+\t\t\tstruct commit *commit = (struct commit *)obj;\n+\t\t\tif (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n+\t\t\t\tcontinue;\n+\t\t\tmark_tree_uninteresting(commit->tree);\n+\t\t\tif (revs->edge_hint && !(obj->flags & SHOWN)) {\n+\t\t\t\tobj->flags |= SHOWN;\n+\t\t\t\tshow_edge(commit);\n+\t\t\t}\n \t\t}\n \t}\n }\n-- \n1.8.5.2.500.g8060133\n"},{"id":"233418","messageId":"20140120221142.GA24320@sigill.intra.peff.net","threadId":"35701","inReplyTo":"20140120213101.GA16095@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] t/perf: time rev-list with UNINTERESTING commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-20T22:11:42Z","receivedAt":"2014-01-20T22:11:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 20, 2014 at 04:31:01PM -0500, Jeff King wrote:\n\n> diff --git a/t/perf/p0001-rev-list.sh b/t/perf/p0001-rev-list.sh\n> index 4f71a63..b7258a7 100755\n> --- a/t/perf/p0001-rev-list.sh\n> +++ b/t/perf/p0001-rev-list.sh\n> @@ -14,4 +14,21 @@ test_perf 'rev-list --all --objects' '\n> \tgit rev-list --all --objects >/dev/null\n> '\n> \n> +test_expect_success 'create new unreferenced commit' '\n> +\tgit checkout --detach HEAD &&\n> +\techo content >>file &&\n> +\tgit add file &&\n> +\tgit commit -m detached &&\n> +\tcommit=$(git rev-parse --verify HEAD) &&\n> +\tgit checkout -\n> +'\n\nThis is bad to be touching the repo and assuming it is non-bare. For\nsome reason I assumed that the perf suite made a copy of the repo, but\nit doesn't. If you point to a bare repo via GIT_PERF_REPO, this part of\nthe test fails.\n\nIt's actually enough to demonstrate the problem without changing the\ntree at all. So this produces the same numbers, and works everywhere:\n\ndiff --git a/t/perf/p0001-rev-list.sh b/t/perf/p0001-rev-list.sh\nindex b7258a7..16359d5 100755\n--- a/t/perf/p0001-rev-list.sh\n+++ b/t/perf/p0001-rev-list.sh\n@@ -15,12 +15,7 @@ test_perf 'rev-list --all --objects' '\n '\n \n test_expect_success 'create new unreferenced commit' '\n-\tgit checkout --detach HEAD &&\n-\techo content >>file &&\n-\tgit add file &&\n-\tgit commit -m detached &&\n-\tcommit=$(git rev-parse --verify HEAD) &&\n-\tgit checkout -\n+\tcommit=$(git commit-tree HEAD^{tree} -p HEAD)\n '\n \n test_perf 'rev-list $commit --not --all' '\n\nIt still modifies the test repo, but at least in a fairly innocuous way.\n\n-Peff\n"},{"id":"233419","messageId":"20140120222936.GA25291@sigill.intra.peff.net","threadId":"35701","inReplyTo":"20140120212845.GA11451@sigill.intra.peff.net","subject":"Re: [PATCH 0/2] performance regression in mark_edges_uninteresting","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-20T22:29:36Z","receivedAt":"2014-01-20T22:29:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 20, 2014 at 04:28:45PM -0500, Jeff King wrote:\n\n> [1/2]: t/perf: time rev-list with UNINTERESTING commits\n> [2/2]: list-objects: only look at cmdline trees with edge_hint\n> \n> Here's t/perf/p0001 output that shows the problem:\n> \n> 0001.5: rev-list --objects $commit --not --all\n> fbd4a703^ fbd4a703 HEAD\n> 0.04(0.04+0.00) 0.28(0.27+0.00) +600.0% 0.04(0.04+0.00) +0.0%\n\nThose numbers are on git.git. Obviously 600% is a lot, but 24ms is not.\nHowever, the cost is a factor of the tree size times the number of refs.\nFor the \"homebrew.git\" repository stored at GitHub, which has ~28,000\nrefs (mostly pointing at pull-request tips in refs/pull), the numbers\nare much more dramatic:\n\nfbd4a703^ fbd4a703 HEAD \n0.50(0.46+0.02) 8.23(8.17+0.06) +1546.0% 0.50(0.48+0.01) +0.0%\n\n-Peff\n"},{"id":"233420","messageId":"87ppnmb7yr.fsf@thomasrast.ch","threadId":"35701","inReplyTo":"20140120221142.GA24320@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] t/perf: time rev-list with UNINTERESTING commits","fromName":"Thomas Rast","fromEmail":"tr@thomasrast.ch","sentAt":"2014-01-20T22:32:12Z","receivedAt":"2014-01-20T22:32:12Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Jeff King writes:\n\n> On Mon, Jan 20, 2014 at 04:31:01PM -0500, Jeff King wrote:\n>\n>> diff --git a/t/perf/p0001-rev-list.sh b/t/perf/p0001-rev-list.sh\n>> index 4f71a63..b7258a7 100755\n>> --- a/t/perf/p0001-rev-list.sh\n>> +++ b/t/perf/p0001-rev-list.sh\n>> @@ -14,4 +14,21 @@ test_perf 'rev-list --all --objects' '\n>> \tgit rev-list --all --objects >/dev/null\n>> '\n>> \n>> +test_expect_success 'create new unreferenced commit' '\n>> +\tgit checkout --detach HEAD &&\n>> +\techo content >>file &&\n>> +\tgit add file &&\n>> +\tgit commit -m detached &&\n>> +\tcommit=$(git rev-parse --verify HEAD) &&\n>> +\tgit checkout -\n>> +'\n>\n> This is bad to be touching the repo and assuming it is non-bare. For\n> some reason I assumed that the perf suite made a copy of the repo, but\n> it doesn't. If you point to a bare repo via GIT_PERF_REPO, this part of\n> the test fails.\n\nIt does make a copy, but with cp -Rl. I haven't actually ever tried\nwhat happens if you point it at a bare though. It *should* fail because\nit tries to cd $repo/.git, but if that was itself bare...\n\n-- \nThomas Rast\ntr@thomasrast.ch\n"},{"id":"233421","messageId":"20140120223936.GA2350@sigill.intra.peff.net","threadId":"35701","inReplyTo":"87ppnmb7yr.fsf@thomasrast.ch","subject":"Re: [PATCH 1/2] t/perf: time rev-list with UNINTERESTING commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-20T22:39:36Z","receivedAt":"2014-01-20T22:39:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 20, 2014 at 11:32:12PM +0100, Thomas Rast wrote:\n\n> > This is bad to be touching the repo and assuming it is non-bare. For\n> > some reason I assumed that the perf suite made a copy of the repo, but\n> > it doesn't. If you point to a bare repo via GIT_PERF_REPO, this part of\n> > the test fails.\n> \n> It does make a copy, but with cp -Rl. I haven't actually ever tried\n> what happens if you point it at a bare though. It *should* fail because\n> it tries to cd $repo/.git, but if that was itself bare...\n\nOh, hmph. I checked my linux repo, which I had used as GIT_PERF_REPO,\nand noticed that it had the test commit in its reflog. But I forgot that\nis because I did the test manually there right before writing up the\nt/perf script! So yes, it copies, and it's totally fine to be modifying\nthe repo.\n\nBare repos seem to work just fine for me. It looks like we use `git\nrev-parse --git-dir` to get the source, and then copy that to `.git` in\nthe temporary directory. So that works fine either way, and we do have a\ndirectory available as the working dir. But of course the config from\nthe bare repo says `core.bare = true`, so some commands will bail.\n\nWe could perhaps just set GIT_WORK_TREE in the perf scripts, which I\nbelieve would override the bare setting in the .git/config. And then we\nknow the repos will be consistently non-bare.\n\nWhether we do that or not, I think the update I posted is preferable, as\nit reproduces the problem in a much simpler manner.\n\n-Peff\n"},{"id":"233424","messageId":"CACsJy8CBuW0dXgbSLgFHye9-aCDQCaK47MFpqeCh3m3JWHJOEw@mail.gmail.com","threadId":"35701","inReplyTo":"20140120213250.GB16095@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] list-objects: only look at cmdline trees with edge_hint","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-01-20T23:57:08Z","receivedAt":"2014-01-20T23:57:08Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Jan 21, 2014 at 4:32 AM, Jeff King wrote:\n> This patch therefore ties the extra tree examination to the\n> revs->edge_hint flag; it is the presence of that flag that\n> makes the tradeoff worthwhile.\n>\n> Here is output from the p0001-rev-list showing the\n> improvement in performance:\n>\n> Test HEAD^ HEAD\n> -----------------------------------------------------------------------------------------\n> 0001.1: rev-list --all 0.69(0.65+0.02) 0.69(0.66+0.02) +0.0%\n> 0001.2: rev-list --all --objects 3.22(3.19+0.03) 3.23(3.20+0.03) +0.3%\n> 0001.4: rev-list $commit --not --all 0.04(0.04+0.00) 0.04(0.04+0.00) +0.0%\n> 0001.5: rev-list --objects $commit --not --all 0.27(0.26+0.01) 0.04(0.04+0.00) -85.2%\n\nYou must have so much fun (or headache, depending on your view) with\nthe variety of repos on github :)\n\n> diff --git a/list-objects.c b/list-objects.c\n> index 6cbedf0..43ce1d9 100644\n> --- a/list-objects.c\n> +++ b/list-objects.c\n> @@ -162,15 +162,17 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)\n> }\n> mark_edge_parents_uninteresting(commit, revs, show_edge);\n> }\n> - for (i = 0; i < revs->cmdline.nr; i++) {\n> - struct object *obj = revs->cmdline.rev[i].item;\n> - struct commit *commit = (struct commit *)obj;\n> - if (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n> - continue;\n> - mark_tree_uninteresting(commit->tree);\n> - if (revs->edge_hint && !(obj->flags & SHOWN)) {\n> - obj->flags |= SHOWN;\n> - show_edge(commit);\n> + if (revs->edge_hint) {\n> + for (i = 0; i < revs->cmdline.nr; i++) {\n> + struct object *obj = revs->cmdline.rev[i].item;\n> + struct commit *commit = (struct commit *)obj;\n> + if (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n> + continue;\n> + mark_tree_uninteresting(commit->tree);\n> + if (revs->edge_hint && !(obj->flags & SHOWN)) {\n\nNot really important, but perhaps remove revs->edge_hint here because\nit's already checked?\n\n> + obj->flags |= SHOWN;\n> + show_edge(commit);\n> + }\n> }\n> }\n> }\n-- \nDuy\n"},{"id":"233425","messageId":"20140121022254.GA4597@sigill.intra.peff.net","threadId":"35701","inReplyTo":"CACsJy8CBuW0dXgbSLgFHye9-aCDQCaK47MFpqeCh3m3JWHJOEw@mail.gmail.com","subject":"Re: [PATCH 2/2] list-objects: only look at cmdline trees with edge_hint","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-21T02:22:54Z","receivedAt":"2014-01-21T02:22:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 21, 2014 at 06:57:08AM +0700, Duy Nguyen wrote:\n\n> You must have so much fun (or headache, depending on your view) with\n> the variety of repos on github :)\n\nIt's fun on days like these when the solution is fairly straightforward.\n:)\n\n> > + if (revs->edge_hint) {\n> > + for (i = 0; i < revs->cmdline.nr; i++) {\n> > + struct object *obj = revs->cmdline.rev[i].item;\n> > + struct commit *commit = (struct commit *)obj;\n> > + if (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n> > + continue;\n> > + mark_tree_uninteresting(commit->tree);\n> > + if (revs->edge_hint && !(obj->flags & SHOWN)) {\n> \n> Not really important, but perhaps remove revs->edge_hint here because\n> it's already checked?\n\nYes, I think that is a good idea. Thanks.\n\nRe-roll coming in a moment.\n\n-Peff\n"},{"id":"233426","messageId":"20140121022431.GA4614@sigill.intra.peff.net","threadId":"35701","inReplyTo":"20140120212845.GA11451@sigill.intra.peff.net","subject":"[PATCH v2 0/2] performance regression in mark_edges_uninteresting","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-21T02:24:31Z","receivedAt":"2014-01-21T02:24:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 20, 2014 at 04:28:45PM -0500, Jeff King wrote:\n\n> This series fixes a rev-list performance regression in fbd4a70 (list-objects:\n> mark more commits as edges in mark_edges_uninteresting, 2013-08-16). That\n> commit is a little tricky because it actually _knows_ it's trading off CPU for\n> a better packfile, but I think we're performing the tradeoff in too many\n> places. See the second commit for details.\n> \n> [1/2]: t/perf: time rev-list with UNINTERESTING commits\n> [2/2]: list-objects: only look at cmdline trees with edge_hint\n> \n> Here's t/perf/p0001 output that shows the problem:\n> \n> 0001.5: rev-list --objects $commit --not --all\n> fbd4a703^ fbd4a703 HEAD\n> 0.04(0.04+0.00) 0.28(0.27+0.00) +600.0% 0.04(0.04+0.00) +0.0%\n\nHere's v2 that addresses the minor comments on the list (simpler test in\nthe first patch, and dropping the now-redundant revs->edge_hint check in\nthe second patch).\n\n-Peff\n"},{"id":"233427","messageId":"20140121022511.GA4672@sigill.intra.peff.net","threadId":"35701","inReplyTo":"20140121022431.GA4614@sigill.intra.peff.net","subject":"[PATCH v2 1/2] t/perf: time rev-list with UNINTERESTING commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-21T02:25:12Z","receivedAt":"2014-01-21T02:25:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We time a straight \"rev-list --all\" and its \"--object\"\ncounterpart, both going all the way to the root. However, we\ndo not time a partial history walk. This patch adds an\nextreme case: a walk over a very small slice of history, but\nwith a very large set of UNINTERESTING tips. This is similar\nto the connectivity check run by git on a small fetch, or\nthe walk done by any pre-receive hooks that want to check\nincoming commits.\n\nThis test reveals a performance regression in git v1.8.4.2,\ncaused by fbd4a70 (list-objects: mark more commits as edges\nin mark_edges_uninteresting, 2013-08-16):\n\nTest fbd4a703^ fbd4a703\n------------------------------------------------------------------------------------------\n0001.1: rev-list --all 0.69(0.67+0.02) 0.69(0.68+0.01) +0.0%\n0001.2: rev-list --all --objects 3.47(3.44+0.02) 3.48(3.44+0.03) +0.3%\n0001.4: rev-list $commit --not --all 0.04(0.04+0.00) 0.04(0.04+0.00) +0.0%\n0001.5: rev-list --objects $commit --not --all 0.04(0.03+0.00) 0.27(0.24+0.02) +575.0%\n\nSigned-off-by: Jeff King \n---\n t/perf/p0001-rev-list.sh | 12 ++++++++++++\n 1 file changed, 12 insertions(+)\n\ndiff --git a/t/perf/p0001-rev-list.sh b/t/perf/p0001-rev-list.sh\nindex 4f71a63..16359d5 100755\n--- a/t/perf/p0001-rev-list.sh\n+++ b/t/perf/p0001-rev-list.sh\n@@ -14,4 +14,16 @@ test_perf 'rev-list --all --objects' '\n \tgit rev-list --all --objects >/dev/null\n '\n \n+test_expect_success 'create new unreferenced commit' '\n+\tcommit=$(git commit-tree HEAD^{tree} -p HEAD)\n+'\n+\n+test_perf 'rev-list $commit --not --all' '\n+\tgit rev-list $commit --not --all >/dev/null\n+'\n+\n+test_perf 'rev-list --objects $commit --not --all' '\n+\tgit rev-list --objects $commit --not --all >/dev/null\n+'\n+\n test_done\n-- \n1.8.5.2.500.g8060133\n"},{"id":"233428","messageId":"20140121022540.GB4672@sigill.intra.peff.net","threadId":"35701","inReplyTo":"20140121022431.GA4614@sigill.intra.peff.net","subject":"[PATCH v2 2/2] list-objects: only look at cmdline trees with edge_hint","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-21T02:25:40Z","receivedAt":"2014-01-21T02:25:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When rev-list is given a command-line like:\n\n git rev-list --objects $commit --not --all\n\nthe most accurate answer is the difference between the set\nof objects reachable from $commit and the set reachable from\nall of the existing refs. However, we have not historically\nprovided that answer, because it is very expensive to\ncalculate. We would have to open every tree of every commit\nin the entire history.\n\nInstead, we find the accurate set difference of the\nreachable commits, and then mark the trees at the boundaries\nas uninteresting. This misses objects which appear in the\ntrees of both the interesting commits and deep within the\nuninteresting history.\n\nCommit fbd4a70 (list-objects: mark more commits as edges in\nmark_edges_uninteresting, 2013-08-16) noticed that we miss\nthose objects during pack-objects, and added code to examine\nthe trees of all of the \"--not\" refs given on the\ncommand-line. Note that this is still not the complete set\ndifference, because we look only at the tips of the\ncommand-line arguments, not all of their reachable commits.\nBut it increases the set of boundary objects we consider,\nwhich is especially important for shallow fetches. So we\nare trading extra CPU time for a larger set of boundary\nobjects, which can improve the resulting pack size for a\n--thin pack.\n\nThis tradeoff probably makes sense in the context of\npack-objects, where we have set revs->edge_hint to have the\ntraversal feed us the set of boundary objects. For a\nregular rev-list, though, it is probably not a good\ntradeoff. It is true that it makes our list slightly closer\nto a true set difference, but it is a rare case where this\nis important. And because we do not have revs->edge_hint\nset, we do nothing useful with the larger set of boundary\nobjects.\n\nThis patch therefore ties the extra tree examination to the\nrevs->edge_hint flag; it is the presence of that flag that\nmakes the tradeoff worthwhile.\n\nHere is output from the p0001-rev-list showing the\nimprovement in performance:\n\nTest HEAD^ HEAD\n-----------------------------------------------------------------------------------------\n0001.1: rev-list --all 0.69(0.65+0.02) 0.69(0.66+0.02) +0.0%\n0001.2: rev-list --all --objects 3.22(3.19+0.03) 3.23(3.20+0.03) +0.3%\n0001.4: rev-list $commit --not --all 0.04(0.04+0.00) 0.04(0.04+0.00) +0.0%\n0001.5: rev-list --objects $commit --not --all 0.27(0.26+0.01) 0.04(0.04+0.00) -85.2%\n\nSigned-off-by: Jeff King \n---\n list-objects.c | 20 +++++++++++---------\n 1 file changed, 11 insertions(+), 9 deletions(-)\n\ndiff --git a/list-objects.c b/list-objects.c\nindex 6cbedf0..206816f 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -162,15 +162,17 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)\n \t\t}\n \t\tmark_edge_parents_uninteresting(commit, revs, show_edge);\n \t}\n-\tfor (i = 0; i < revs->cmdline.nr; i++) {\n-\t\tstruct object *obj = revs->cmdline.rev[i].item;\n-\t\tstruct commit *commit = (struct commit *)obj;\n-\t\tif (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n-\t\t\tcontinue;\n-\t\tmark_tree_uninteresting(commit->tree);\n-\t\tif (revs->edge_hint && !(obj->flags & SHOWN)) {\n-\t\t\tobj->flags |= SHOWN;\n-\t\t\tshow_edge(commit);\n+\tif (revs->edge_hint) {\n+\t\tfor (i = 0; i < revs->cmdline.nr; i++) {\n+\t\t\tstruct object *obj = revs->cmdline.rev[i].item;\n+\t\t\tstruct commit *commit = (struct commit *)obj;\n+\t\t\tif (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n+\t\t\t\tcontinue;\n+\t\t\tmark_tree_uninteresting(commit->tree);\n+\t\t\tif (!(obj->flags & SHOWN)) {\n+\t\t\t\tobj->flags |= SHOWN;\n+\t\t\t\tshow_edge(commit);\n+\t\t\t}\n \t\t}\n \t}\n }\n-- \n1.8.5.2.500.g8060133\n"},{"id":"233470","messageId":"xmqq8uu9t0gt.fsf@gitster.dls.corp.google.com","threadId":"35701","inReplyTo":"20140121022540.GB4672@sigill.intra.peff.net","subject":"Re: [PATCH v2 2/2] list-objects: only look at cmdline trees with edge_hint","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-01-21T22:49:06Z","receivedAt":"2014-01-21T22:49:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> This tradeoff probably makes sense in the context of\n> pack-objects, where we have set revs->edge_hint to have the\n> traversal feed us the set of boundary objects. For a\n> regular rev-list, though, it is probably not a good\n> tradeoff. It is true that it makes our list slightly closer\n> to a true set difference, but it is a rare case where this\n> is important. And because we do not have revs->edge_hint\n> set, we do nothing useful with the larger set of boundary\n> objects.\n>\n> This patch therefore ties the extra tree examination to the\n> revs->edge_hint flag; it is the presence of that flag that\n> makes the tradeoff worthwhile.\n\nMakes sense. Thanks. Will queue.\n\n>\n> Here is output from the p0001-rev-list showing the\n> improvement in performance:\n>\n> Test HEAD^ HEAD\n> -----------------------------------------------------------------------------------------\n> 0001.1: rev-list --all 0.69(0.65+0.02) 0.69(0.66+0.02) +0.0%\n> 0001.2: rev-list --all --objects 3.22(3.19+0.03) 3.23(3.20+0.03) +0.3%\n> 0001.4: rev-list $commit --not --all 0.04(0.04+0.00) 0.04(0.04+0.00) +0.0%\n> 0001.5: rev-list --objects $commit --not --all 0.27(0.26+0.01) 0.04(0.04+0.00) -85.2%\n>\n> Signed-off-by: Jeff King \n> ---\n> list-objects.c | 20 +++++++++++---------\n> 1 file changed, 11 insertions(+), 9 deletions(-)\n>\n> diff --git a/list-objects.c b/list-objects.c\n> index 6cbedf0..206816f 100644\n> --- a/list-objects.c\n> +++ b/list-objects.c\n> @@ -162,15 +162,17 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)\n> \t\t}\n> \t\tmark_edge_parents_uninteresting(commit, revs, show_edge);\n> \t}\n> -\tfor (i = 0; i < revs->cmdline.nr; i++) {\n> -\t\tstruct object *obj = revs->cmdline.rev[i].item;\n> -\t\tstruct commit *commit = (struct commit *)obj;\n> -\t\tif (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n> -\t\t\tcontinue;\n> -\t\tmark_tree_uninteresting(commit->tree);\n> -\t\tif (revs->edge_hint && !(obj->flags & SHOWN)) {\n> -\t\t\tobj->flags |= SHOWN;\n> -\t\t\tshow_edge(commit);\n> +\tif (revs->edge_hint) {\n> +\t\tfor (i = 0; i < revs->cmdline.nr; i++) {\n> +\t\t\tstruct object *obj = revs->cmdline.rev[i].item;\n> +\t\t\tstruct commit *commit = (struct commit *)obj;\n> +\t\t\tif (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n> +\t\t\t\tcontinue;\n> +\t\t\tmark_tree_uninteresting(commit->tree);\n> +\t\t\tif (!(obj->flags & SHOWN)) {\n> +\t\t\t\tobj->flags |= SHOWN;\n> +\t\t\t\tshow_edge(commit);\n> +\t\t\t}\n> \t\t}\n> \t}\n> }\n"}]}