{"thread":{"id":"49598","subject":"commit-graph is cool (overcoming add_missing_tags() perf issues)","startedAt":"2018-10-17T18:00:18Z","lastAt":"2018-10-31T05:46:14Z","messageCount":7,"participants":["Elijah Newren","Derrick Stolee","Jeff King","Ævar Arnfjörð Bjarmason"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"360767","messageId":"CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com","threadId":"49598","inReplyTo":null,"subject":"commit-graph is cool (overcoming add_missing_tags() perf issues)","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2018-10-17T18:00:03Z","receivedAt":"2018-10-17T18:00:18Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi,\n\nJust wanted to give a shout-out for the commit-graph work and how\nimpressive it is.  I had an internal report from a user that git\npushes containing only one new tiny commit were taking over a minute\n(in a moderate size repo with good network connectivity). After\ndigging for a while, I noticed three unusual things about the repo[1]:\n  * he had push.followTags set to true\n  * upstream repo had about 20k tags (despite only 55k commits)\n  * his repo had an additional 2.5k tags, but none of these were in\n    the history of the branches he was pushing and thus would not be\n    included in any pushes.\n\nDigging in, almost all the time was CPU-bound and spent in\nadd_missing_tags()[2].  If I'm reading the code correctly, it appears\nthat function loops over each tag, calling in_merge_bases_many() once\nper tag.  Thus, for his case, we were potentially walking all of\nhistory of the main branch 2.5k times.  That seemed rather suboptimal.\n\nBefore attempting to optimize, I decided to try out the commit-graph\nwith a version of git from pu.  While I expected a speed-up, I was a\nbit suprised that it was a factor of over 100; dropping the time for\nlocal dry-run push[2] to sub-second.  A quick look suggests that\ncommit-graph doesn't fix the fact that we call in_merge_bases_many() N\ntimes from add_missing_tags() and thus likely need to do N merge base\ncomputations, it just makes each of the N much faster.  So, perhaps\nthere's still another scaling issue we'll eventually need to address,\nbut for now, I'm pretty excited about commit-graph.\n\n(And in the mean time I gave the user a one-liner to nuke his\nlocal-only tags that I suspect he doesn't need.)\n\nThanks,\nElijah\n\n\n[1] lerna seems to scale horribly, especially when you suddenly\ntransition dozens of web developers and even more independent\nrepositories into a single large monorepo.  Usage of lerna was\nthankfully ripped out at some point, but the crazy number of\nhistorical tags remain.  Also, this user did a bunch of the\nfilter-branch'ing to suck extra repos into the monorepo, likely\ninvolved somehow in the many extra tags he had.\n\n[2] In fact, I still had timings of over a minute when adjusting the command to:\n  git push --follow-tags --dry-run /PATH/TO/LOCAL-MIRROR $BRANCH\n"},{"id":"360772","messageId":"1d52a566-e7f5-9b7f-4bb1-cac5a50ebcb6@gmail.com","threadId":"49598","inReplyTo":"CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com","subject":"Re: commit-graph is cool (overcoming add_missing_tags() perf issues)","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-17T18:19:40Z","receivedAt":"2018-10-17T18:19:45Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/17/2018 2:00 PM, Elijah Newren wrote:\n> Hi,\n>\n> Just wanted to give a shout-out for the commit-graph work and how\n> impressive it is.  I had an internal report from a user that git\n> pushes containing only one new tiny commit were taking over a minute\n> (in a moderate size repo with good network connectivity). After\n> digging for a while, I noticed three unusual things about the repo[1]:\n>    * he had push.followTags set to true\n>    * upstream repo had about 20k tags (despite only 55k commits)\n>    * his repo had an additional 2.5k tags, but none of these were in\n>      the history of the branches he was pushing and thus would not be\n>      included in any pushes.\n>\n> Digging in, almost all the time was CPU-bound and spent in\n> add_missing_tags()[2].  If I'm reading the code correctly, it appears\n> that function loops over each tag, calling in_merge_bases_many() once\n> per tag.  Thus, for his case, we were potentially walking all of\n> history of the main branch 2.5k times.  That seemed rather suboptimal.\n\nThanks for the report. I made a note to inspect add_missing_tags() for \nmore improvement in the future.\n\n> Before attempting to optimize, I decided to try out the commit-graph\n> with a version of git from pu.  While I expected a speed-up, I was a\n> bit suprised that it was a factor of over 100; dropping the time for\n> local dry-run push[2] to sub-second.  A quick look suggests that\n> commit-graph doesn't fix the fact that we call in_merge_bases_many() N\n> times from add_missing_tags() and thus likely need to do N merge base\n> computations, it just makes each of the N much faster.  So, perhaps\n> there's still another scaling issue we'll eventually need to address,\n> but for now, I'm pretty excited about commit-graph.\n\nWithout the commit-graph, you are getting a quadratic problem (N commits \n* T tags), but with the commit-graph you are also getting the benefit of \ngeneration numbers, so the \"N commits\" is actually likely _zero_ for \nmost tags, because the tags have strictly lower generation number. In \nthose cases, we can terminate without any walk at all.\n\nThanks!\n-Stolee\n\n"},{"id":"360776","messageId":"20181017183125.GE28326@sigill.intra.peff.net","threadId":"49598","inReplyTo":"CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com","subject":"Re: commit-graph is cool (overcoming add_missing_tags() perf issues)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-10-17T18:31:25Z","receivedAt":"2018-10-17T18:31:30Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 17, 2018 at 11:00:03AM -0700, Elijah Newren wrote:\n\n> Digging in, almost all the time was CPU-bound and spent in\n> add_missing_tags()[2].  If I'm reading the code correctly, it appears\n> that function loops over each tag, calling in_merge_bases_many() once\n> per tag.  Thus, for his case, we were potentially walking all of\n> history of the main branch 2.5k times.  That seemed rather suboptimal.\n> \n> Before attempting to optimize, I decided to try out the commit-graph\n> with a version of git from pu.  While I expected a speed-up, I was a\n> bit suprised that it was a factor of over 100; dropping the time for\n> local dry-run push[2] to sub-second.  A quick look suggests that\n> commit-graph doesn't fix the fact that we call in_merge_bases_many() N\n> times from add_missing_tags() and thus likely need to do N merge base\n> computations, it just makes each of the N much faster.  So, perhaps\n> there's still another scaling issue we'll eventually need to address,\n> but for now, I'm pretty excited about commit-graph.\n\nYeah, I think this case would probably still benefit from an all-points\ntraversal. This want to be basically the same as what \"git tag --merged\"\nis doing, I would think (see ref-filter.c:do_merge_filter).\n\n  As an aside, it looks like do_merge_filter uses prepare_revision_walk(),\n  which IIRC means that it is susceptible to wrong answers due to\n  clock skew (basically because of the use of commit timestamps for\n  traversal order). This seems like another place where generation\n  numbers could make a quiet improvement.\n\n-Peff\n"},{"id":"361992","messageId":"302a9351-6133-f562-8c5a-d688d5cc3c88@gmail.com","threadId":"49598","inReplyTo":"CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com","subject":"Re: commit-graph is cool (overcoming add_missing_tags() perf issues)","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-30T14:22:36Z","receivedAt":"2018-10-30T14:22:41Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/17/2018 2:00 PM, Elijah Newren wrote:\n> Hi,\n>\n> Just wanted to give a shout-out for the commit-graph work and how\n> impressive it is.  I had an internal report from a user that git\n> pushes containing only one new tiny commit were taking over a minute\n> (in a moderate size repo with good network connectivity). After\n> digging for a while, I noticed three unusual things about the repo[1]:\n>    * he had push.followTags set to true\n>    * upstream repo had about 20k tags (despite only 55k commits)\n>    * his repo had an additional 2.5k tags, but none of these were in\n>      the history of the branches he was pushing and thus would not be\n>      included in any pushes.\n>\n> Digging in, almost all the time was CPU-bound and spent in\n> add_missing_tags()[2].  If I'm reading the code correctly, it appears\n> that function loops over each tag, calling in_merge_bases_many() once\n> per tag.  Thus, for his case, we were potentially walking all of\n> history of the main branch 2.5k times.  That seemed rather suboptimal.\n\nElijah,\n\nDo you still have this repo around? Could you by chance test the \nperformance with the new algorithm for add_missing_tags() in [1]? \nSpecifically, please test it without a commit-graph file, since your \ndata shape already makes use of generation numbers pretty well.\n\nThanks,\n-Stolee\n\n[1] https://public-inbox.org/git/pull.60.git.gitgitgadget@gmail.com/T/#t\n"},{"id":"361995","messageId":"CACBZZX5=CGvYqe07a5yzxc-=U92oSR5u7tpzJDEBEMzY6NDovA@mail.gmail.com","threadId":"49598","inReplyTo":"CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com","subject":"Re: commit-graph is cool (overcoming add_missing_tags() perf issues)","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-10-30T16:22:48Z","receivedAt":"2018-10-30T16:23:02Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Wed, Oct 17, 2018 at 8:41 PM Elijah Newren <newren@gmail.com> wrote:\n> (And in the mean time I gave the user a one-liner to nuke his\n> local-only tags that I suspect he doesn't need.)\n\nJust a note that you can usually set 'fetch.pruneTags=true' these days\nto make that happen.\n"},{"id":"362072","messageId":"CABPp-BHPZD2zRkrbAFOEp4KAT+fAvO4KzFrCsk_Pyy5V65t=ig@mail.gmail.com","threadId":"49598","inReplyTo":"302a9351-6133-f562-8c5a-d688d5cc3c88@gmail.com","subject":"Re: commit-graph is cool (overcoming add_missing_tags() perf issues)","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2018-10-31T05:45:13Z","receivedAt":"2018-10-31T05:45:28Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Oct 30, 2018 at 7:22 AM Derrick Stolee <stolee@gmail.com> wrote:\n>\n> On 10/17/2018 2:00 PM, Elijah Newren wrote:\n> > Hi,\n> >\n> > Just wanted to give a shout-out for the commit-graph work and how\n> > impressive it is.  I had an internal report from a user that git\n> > pushes containing only one new tiny commit were taking over a minute\n> > (in a moderate size repo with good network connectivity). After\n> > digging for a while, I noticed three unusual things about the repo[1]:\n> >    * he had push.followTags set to true\n> >    * upstream repo had about 20k tags (despite only 55k commits)\n> >    * his repo had an additional 2.5k tags, but none of these were in\n> >      the history of the branches he was pushing and thus would not be\n> >      included in any pushes.\n> >\n> > Digging in, almost all the time was CPU-bound and spent in\n> > add_missing_tags()[2].  If I'm reading the code correctly, it appears\n> > that function loops over each tag, calling in_merge_bases_many() once\n> > per tag.  Thus, for his case, we were potentially walking all of\n> > history of the main branch 2.5k times.  That seemed rather suboptimal.\n>\n> Elijah,\n>\n> Do you still have this repo around? Could you by chance test the\n> performance with the new algorithm for add_missing_tags() in [1]?\n> Specifically, please test it without a commit-graph file, since your\n> data shape already makes use of generation numbers pretty well.\n>\n> Thanks,\n> -Stolee\n\nI nuked it, but turns out I had a backup that I found after digging\naround for a bit.  I'll post a comment on the series with the results.\n\nBy the way, I've been running pu for about a week with this tweak:\n\ndiff --git a/revision.c b/revision.c\nindex b5108b75ab..d20c687e71 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1457,6 +1457,7 @@ void repo_init_revisions(struct repository *r,\n        revs->pruning.change = file_change;\n        revs->pruning.change_fn_data = revs;\n        revs->sort_order = REV_SORT_IN_GRAPH_ORDER;\n+       revs->topo_order = 1;\n        revs->dense = 1;\n        revs->prefix = prefix;\n        revs->max_age = -1;\n\nOnly ran into one small problem once, and it wasn't commit-graph\nrelated; rather it was related to my above patch and needing to not\nhave topo_order be set.  (I just bailed and used my older\nsystem-installed git from /usr/bin/ in that one case.)  So, I think\nthe commit-graph stuff is looking pretty good, and I find the recent\nthread on further improvements with corrected commit date (among other\npossibilities) very intriguing...even if I haven't had much time to\ncomment or test recently.\n"},{"id":"362073","messageId":"CABPp-BF1JwtTCQ0EqSWZ-VaXJogtBDJs9HqFQFcWxHV3x0_SzA@mail.gmail.com","threadId":"49598","inReplyTo":"CACBZZX5=CGvYqe07a5yzxc-=U92oSR5u7tpzJDEBEMzY6NDovA@mail.gmail.com","subject":"Re: commit-graph is cool (overcoming add_missing_tags() perf issues)","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2018-10-31T05:46:01Z","receivedAt":"2018-10-31T05:46:14Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Oct 30, 2018 at 9:23 AM Ævar Arnfjörð Bjarmason\n<avarab@gmail.com> wrote:\n>\n> On Wed, Oct 17, 2018 at 8:41 PM Elijah Newren <newren@gmail.com> wrote:\n> > (And in the mean time I gave the user a one-liner to nuke his\n> > local-only tags that I suspect he doesn't need.)\n>\n> Just a note that you can usually set 'fetch.pruneTags=true' these days\n> to make that happen.\n\nTIL.  Thanks for the heads up.\n"}]}