{"thread":{"id":"47446","subject":"Question about the ahead-behind computation and status","startedAt":"2017-12-14T21:49:38Z","lastAt":"2017-12-15T19:40:35Z","messageCount":6,"participants":["Jeff Hostetler","Jeff King","Derrick Stolee","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"334850","messageId":"030bf57c-7a23-3391-4fc0-93efee791543@jeffhostetler.com","threadId":"47446","inReplyTo":null,"subject":"Question about the ahead-behind computation and status","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-12-14T21:49:31Z","receivedAt":"2017-12-14T21:49:38Z","isPatch":false,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\nWe working with the (enormous) Windows repo, we observed\na performance problem in the ahead-behind computation and\nwere considering a few options.\n\nWe had a local repo with a local branch that was 150K\ncommits behind the upstream branch[*].  There was a ~20\nsecond different in the run times for these 2 commands:\n\n     $ git status --porcelain=v2\n     $ git status --porcelain=v2 --branch\n\nProfiling showed the additional time was spent computing\nthe ahead/behind values for the branch.  (The problem is\nnot specific to porcelain V2, that was just the command\nwhere we discovered it; for example, there is a similar\nperf problem in \"git branch\" vs \"git branch -vv\".)\n\nI don't want to jump into the graph algorithm at this time,\nbut was wondering about adding a --no-ahead-behind flag (or\nsomething similar or a config setting) that would disable\nthe a/b computation during status.\n\nFor status V2 output, we could omit the \"# branch.ab x y\"\nline.  For normal status output, change the prose a/b\nmessage to say something like \"are [not] up to date\".\n\nThoughts or suggestions ???\n\nThanks,\nJeff\n\n\n[*] Sadly, the local repo was only about 20 days out of\n     date (including the Thanksgiving holidays)....\n"},{"id":"334871","messageId":"20171215100835.GC3567@sigill.intra.peff.net","threadId":"47446","inReplyTo":"030bf57c-7a23-3391-4fc0-93efee791543@jeffhostetler.com","subject":"Re: Question about the ahead-behind computation and status","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-12-15T10:08:35Z","receivedAt":"2017-12-15T10:08:44Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Dec 14, 2017 at 04:49:31PM -0500, Jeff Hostetler wrote:\n\n> I don't want to jump into the graph algorithm at this time,\n> but was wondering about adding a --no-ahead-behind flag (or\n> something similar or a config setting) that would disable\n> the a/b computation during status.\n> \n> For status V2 output, we could omit the \"# branch.ab x y\"\n> line.  For normal status output, change the prose a/b\n> message to say something like \"are [not] up to date\".\n\nIs it actually \"status --porcelain=v2\" that you care about here? Or is\nit normal \"git status\"?\n\nDo you care about seeing the branch at all? I.e., would \"--no-branch\" be\na viable option (though I notice it seems to be a silent noop with the\nlong-form, which should probably be fixed).\n\nIf you really do want to see all branch details but just skip the\nahead/behind, then yeah, I'd agree that adding an option to do so makes\nsense. Is \"status\" the only command that needs it? I think we do it\nunconditionally with \"git checkout\", too.\n\n> [*] Sadly, the local repo was only about 20 days out of\n>     date (including the Thanksgiving holidays)....\n\nTaking 20 seconds to traverse 20 days worth of history sounds pretty\nawful. How many commits is it?\n\n-Peff\n"},{"id":"334881","messageId":"88175f57-082d-ad61-c2dd-53ae50540460@jeffhostetler.com","threadId":"47446","inReplyTo":"20171215100835.GC3567@sigill.intra.peff.net","subject":"Re: Question about the ahead-behind computation and status","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-12-15T15:08:13Z","receivedAt":"2017-12-15T15:08:20Z","isPatch":false,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 12/15/2017 5:08 AM, Jeff King wrote:\n> On Thu, Dec 14, 2017 at 04:49:31PM -0500, Jeff Hostetler wrote:\n> \n>> I don't want to jump into the graph algorithm at this time,\n>> but was wondering about adding a --no-ahead-behind flag (or\n>> something similar or a config setting) that would disable\n>> the a/b computation during status.\n>>\n>> For status V2 output, we could omit the \"# branch.ab x y\"\n>> line.  For normal status output, change the prose a/b\n>> message to say something like \"are [not] up to date\".\n> \n> Is it actually \"status --porcelain=v2\" that you care about here? Or is\n> it normal \"git status\"?\n\nMy primary concern is for porcelain V2 because Visual Studio\nuses --branch with V2 to get the other branch details with\none process rather than two on inotify events.\n\nFixing/Helping normal \"git status\" would be nice for interactive\nusers.\n\n  \n> Do you care about seeing the branch at all? I.e., would \"--no-branch\" be\n> a viable option (though I notice it seems to be a silent noop with the\n> long-form, which should probably be fixed).\n\nVS does not use the a/b counts at all, so it is just overhead.\nVS does use some of the other branch fields, so it would be nice\nto still have them.\n\nIt would be nice to minimize changes to the user experience.\nNot printing anything about the a/b in the normal/short/long forms\nmight give the user a false sense of security.  I was thinking if\nwe changed the message to be \"you are [not] up to date\", they would\nstill know they needed to push.\n\nAs it is, at this scale, having the message give an exact count\njust isn't that useful -- who cares if you are 150,000 or 149,000\nbehind.\n\nMaybe we could do something like GCC and just give up at 100\nand print \"you are 100+ ...\".\n\n  \n> If you really do want to see all branch details but just skip the\n> ahead/behind, then yeah, I'd agree that adding an option to do so makes\n> sense. Is \"status\" the only command that needs it? I think we do it\n> unconditionally with \"git checkout\", too.\n\nok. thanks. i'll look at doing that.\n\nYeah, \"checkout\" and \"branch -vv\" could use it too.  I haven't looked\nyet to see anywhere else we might want it, but these can wait.\n\n\n>> [*] Sadly, the local repo was only about 20 days out of\n>>      date (including the Thanksgiving holidays)....\n> \n> Taking 20 seconds to traverse 20 days worth of history sounds pretty\n> awful. How many commits is it?\n\n150,000 commits, give or take.  The graph is many thousands of lanes\nwide because of the merges and that isn't helping.\n\n(But I should give you folks lots of credit -- it *only* took 20\nseconds to find, unzip and decode 150,000 commit objects and walk\nthe commit graph.)\n\nFor a true solution, I think we want to wait for client-side\ngeneration numbers before we spend any time looking at the\nalgorithm.\n\nThanks,\nJeff\n\n\n"},{"id":"334887","messageId":"d16339e0-54bd-073b-fa4a-7c3a84a025e9@gmail.com","threadId":"47446","inReplyTo":"88175f57-082d-ad61-c2dd-53ae50540460@jeffhostetler.com","subject":"Re: Question about the ahead-behind computation and status","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-12-15T15:43:34Z","receivedAt":"2017-12-15T15:43:43Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/15/2017 10:08 AM, Jeff Hostetler wrote:\n> On 12/15/2017 5:08 AM, Jeff King wrote:\n>> On Thu, Dec 14, 2017 at 04:49:31PM -0500, Jeff Hostetler wrote:\n>>> [*] Sadly, the local repo was only about 20 days out of\n>>>      date (including the Thanksgiving holidays)....\n>>\n>> Taking 20 seconds to traverse 20 days worth of history sounds pretty\n>> awful. How many commits is it?\n>\n> 150,000 commits, give or take.  The graph is many thousands of lanes\n> wide because of the merges and that isn't helping.\n>\n> (But I should give you folks lots of credit -- it *only* took 20\n> seconds to find, unzip and decode 150,000 commit objects and walk\n> the commit graph.)\n\nTo give a few more data points, I created similar situation by checking \nout a big repo I hadn't updated in three months and it was 16,000 \ncommits behind. That took 1.5s to calculate the ahead/behind. Moving it \n100,000 commits behind it took 5s. This repo has about 300,000 total \ncommits versus the 1.5 million commits in the Windows repo.\n\nThe biggest reason for the 20 seconds is not just the number of commits \nin the ahead/behind but how many commits are walked (including common to \nboth branches) before paint_down_to_common() breaks its while loop due \nto queue_has_nonstale().\n\nThanks,\n-Stolee\n\n"},{"id":"334899","messageId":"xmqqa7yjrghd.fsf@gitster.mtv.corp.google.com","threadId":"47446","inReplyTo":"d16339e0-54bd-073b-fa4a-7c3a84a025e9@gmail.com","subject":"Re: Question about the ahead-behind computation and status","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-12-15T18:30:38Z","receivedAt":"2017-12-15T18:30:45Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n\n> The biggest reason for the 20 seconds is not just the number of\n> commits in the ahead/behind but how many commits are walked (including\n> common to both branches) before paint_down_to_common() breaks its\n> while loop due to queue_has_nonstale().\n\nHmm, queue_has_nonstale() looks to see if any element is not STALE\n(where the definition of STALE is \"known to be a common ancestor\")\nby potentially checking all elements in the queue.  I wonder if we\nhave an opportunity for a trivial optimization?  When the caller\nknows that it dug one level and added the parents that are not\nstale, it does not have to ask queue_has_nonstale() if there is any\nnon stale element, for example.\n\nWhat do you exactly mean by \"not just the number of commits in the\nahead/behind\"?  Aren't the number of these commits pretty much\nproportional to the number of commits we need to paint down to\ncommon ancestors?  Is the latter a lot larger than the former\n(i.e. are we somehow not stopping when we _could_ notice that we\ncan with better information)?\n\n\n"},{"id":"334907","messageId":"5fd76b6f-15d0-b8ca-710b-d6289a63b9b4@gmail.com","threadId":"47446","inReplyTo":"xmqqa7yjrghd.fsf@gitster.mtv.corp.google.com","subject":"Re: Question about the ahead-behind computation and status","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2017-12-15T19:40:28Z","receivedAt":"2017-12-15T19:40:35Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/15/2017 1:30 PM, Junio C Hamano wrote:\n> Derrick Stolee <stolee@gmail.com> writes:\n>\n>> The biggest reason for the 20 seconds is not just the number of\n>> commits in the ahead/behind but how many commits are walked (including\n>> common to both branches) before paint_down_to_common() breaks its\n>> while loop due to queue_has_nonstale().\n> Hmm, queue_has_nonstale() looks to see if any element is not STALE\n> (where the definition of STALE is \"known to be a common ancestor\")\n> by potentially checking all elements in the queue.  I wonder if we\n> have an opportunity for a trivial optimization?  When the caller\n> knows that it dug one level and added the parents that are not\n> stale, it does not have to ask queue_has_nonstale() if there is any\n> non stale element, for example.\n\nI thought this, too, but my tracing did not show significant time spent \nin this method. 99% of the time is spent unzipping and parsing commits.\n\nIf this was taking too long, then we could track a minimum timestamp for \na commit that entered the queue in a non-stale state, but this will \ndelay the termination condition a bit since commits can be marked stale \nafter they enter the queue.\n\n> What do you exactly mean by \"not just the number of commits in the\n> ahead/behind\"?  Aren't the number of these commits pretty much\n> proportional to the number of commits we need to paint down to\n> common ancestors?  Is the latter a lot larger than the former\n> (i.e. are we somehow not stopping when we _could_ notice that we\n> can with better information)?\n>\n>\n\nWith the wide history, there is actually a large set of commits that are \nin the common history but have newer commit times than the oldest commit \nin only one history. Consider the following ASCII art:\n\n   A\n   |\n   1\n   |\n   2\n   |\n   3\n   |\\\n   4 B\n   |\\|\n   5 C\n   |\\|\n   6 D\n   |\\|\n    .\n    .\n    .\n   |\\|\n   N Z\n   |/\n   0\n\nBetween A and B, A is ahead by commits {A,1,2,3,4,5,6,...,N}. Meanwhile, \ncommits B,C,D,...,Z are in the common history, but still must be walked.\n\nNow imagine these two sets are actually much MUCH wider (thousands of \ncommits that are pairwise non-ancestors). This causes the number of \nwalked commits to be larger than just the number of commits in the \nsymmetric difference of the histories.\n\nUnfortunately, generation numbers are not the only optimization needed \nto make this call be sub-100ms. A graph data structure that lists the \nedges between commits would prevent the time spent in zlib decompressing \nand parsing commits. I'm working on investigating how such a data \nstructure (and corresponding file format) could integrate in the \ncommit-walking code.\n\nThanks,\n-Stolee\n"}]}