{"thread":{"id":"51119","subject":"Revision walking, commit dates, slop","startedAt":"2019-05-18T00:54:18Z","lastAt":"2019-09-18T12:26:45Z","messageCount":23,"participants":["Mike Hommey","SZEDER Gábor","Jakub Narebski","Derrick Stolee","Jonathan Nieder"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"375836","messageId":"20190518005412.n45pj5p2rrtm2bfj@glandium.org","threadId":"51119","inReplyTo":null,"subject":"Revision walking, commit dates, slop","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2019-05-18T00:54:12Z","receivedAt":"2019-05-18T00:54:18Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"Hi,\n\nThere are established corner cases, where in a repo where commit dates\nare not monotonically increasing, revision walking can go horribly\nwrong. This was discussed in the past in e.g.\nhttps://public-inbox.org/git/20150521061553.GA29269@glandium.org/\n\nThe only (simple) workable way, given the current algorithm, to get an\naccurate view off rev-list is to essentially make slop infinite. This\nworks fine, at the expense of runtime.\n\nNow, ignoring any modification for the above, I'm hitting another corner\ncase in some other \"weird\" history, where I have 500k commits all with\nthe same date. With such a commit dag, something as trivial as\n`git rev-list HEAD~..HEAD` goes through all commits from the root commit\nto HEAD, which takes multiple seconds, when the (obvious) output is one\ncommit.\n\nIt looks like the only way revision walking stops going through all the\nancestry is through slop, and slop is essentially made infinite by the\nfact all commits have the same date (because of the date check in\nstill_interesting(). By extension, this means the workaound for the\nfirst corner case above, which is to make slop infinite, essentially\nmakes all rev walking go through the entire ancestry of the commits\ngiven on the command line.\n\nIt feels like some cases of everybody_uninteresting should shorcut slop\nentirely, but considering the only way for slop to decrease at all is\nwhen everybody_uninteresting returns true, that would seem like a wrong\nassumption. But I'm also not sure what slop helps with in the first\nplace (but I don't have a clear view of the broader picture of how the\nentire revision walking works).\n\nAnyways, a rather easy way to witness this happening is to create a\ndummy repo like:\n  git init foo\n  cd foo\n  for i in $(seq 1 50); do\n    echo $i > a;\n    git add a;\n    git commit -a -m $i;\n  done\n\nThe something as simple as `git rev-list HEAD~..HEAD` will go through\nall 50 commits (assuming the script above created commits in the same\nsecond, which it did on my machine)\n\nBy the time both HEAD~ and HEAD have been processed, the revision\nwalking should have enough information to determine that it doesn't need\nto go further, but still does. Even with something like HEAD~2..HEAD,\nafter the first round of processing parents it should be able to see\nthere's not going to be any more interesting commits.\n\nI'm willing to dig into this, but if someone familiar with the\nalgorithm could give me some hints as to what I might be missing in the\nbig picture, that would be helpful.\n\nCheers,\n\nMike\n"},{"id":"375837","messageId":"20190518015005.GA951@szeder.dev","threadId":"51119","inReplyTo":"20190518005412.n45pj5p2rrtm2bfj@glandium.org","subject":"Re: Revision walking, commit dates, slop","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-05-18T01:50:05Z","receivedAt":"2019-05-18T01:50:15Z","isPatch":false,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Sat, May 18, 2019 at 09:54:12AM +0900, Mike Hommey wrote:\n> There are established corner cases, where in a repo where commit dates\n> are not monotonically increasing, revision walking can go horribly\n> wrong. This was discussed in the past in e.g.\n> https://public-inbox.org/git/20150521061553.GA29269@glandium.org/\n> \n> The only (simple) workable way, given the current algorithm, to get an\n> accurate view off rev-list is to essentially make slop infinite. This\n> works fine, at the expense of runtime.\n> \n> Now, ignoring any modification for the above, I'm hitting another corner\n> case in some other \"weird\" history, where I have 500k commits all with\n> the same date. With such a commit dag, something as trivial as\n> `git rev-list HEAD~..HEAD` goes through all commits from the root commit\n> to HEAD, which takes multiple seconds, when the (obvious) output is one\n> commit.\n> \n> It looks like the only way revision walking stops going through all the\n> ancestry is through slop, and slop is essentially made infinite by the\n> fact all commits have the same date (because of the date check in\n> still_interesting(). By extension, this means the workaound for the\n> first corner case above, which is to make slop infinite, essentially\n> makes all rev walking go through the entire ancestry of the commits\n> given on the command line.\n> \n> It feels like some cases of everybody_uninteresting should shorcut slop\n> entirely, but considering the only way for slop to decrease at all is\n> when everybody_uninteresting returns true, that would seem like a wrong\n> assumption. But I'm also not sure what slop helps with in the first\n> place (but I don't have a clear view of the broader picture of how the\n> entire revision walking works).\n> \n> Anyways, a rather easy way to witness this happening is to create a\n> dummy repo like:\n>   git init foo\n>   cd foo\n>   for i in $(seq 1 50); do\n>     echo $i > a;\n>     git add a;\n>     git commit -a -m $i;\n>   done\n> \n> The something as simple as `git rev-list HEAD~..HEAD` will go through\n> all 50 commits (assuming the script above created commits in the same\n> second, which it did on my machine)\n> \n> By the time both HEAD~ and HEAD have been processed, the revision\n> walking should have enough information to determine that it doesn't need\n> to go further, but still does. Even with something like HEAD~2..HEAD,\n> after the first round of processing parents it should be able to see\n> there's not going to be any more interesting commits.\n> \n> I'm willing to dig into this, but if someone familiar with the\n> algorithm could give me some hints as to what I might be missing in the\n> big picture, that would be helpful.\n\nAll the above is without commit-graph, I presume?  If so, then you\nshould give it a try, as it might bring immediate help in your\npathological repo.  With 5k commit in the same second (enforced via\n'export GIT_COMMITTER_DATE=$(date); for i in {1..5000} ...') I get:\n\n  $ best-of-five -q git rev-list HEAD~..HEAD\n  0.069\n  $ git commit-graph write --reachableComputing commit graph generation\n  numbers: 100% (5000/5000), done.\n  $ best-of-five -q git rev-list HEAD~..HEAD\n  0.004\n\n\n"},{"id":"375839","messageId":"20190518035828.pjaqfrkkvldhri6v@glandium.org","threadId":"51119","inReplyTo":"20190518015005.GA951@szeder.dev","subject":"Re: Revision walking, commit dates, slop","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2019-05-18T03:58:28Z","receivedAt":"2019-05-18T03:58:36Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Sat, May 18, 2019 at 03:50:05AM +0200, SZEDER Gábor wrote:\n> On Sat, May 18, 2019 at 09:54:12AM +0900, Mike Hommey wrote:\n> > There are established corner cases, where in a repo where commit dates\n> > are not monotonically increasing, revision walking can go horribly\n> > wrong. This was discussed in the past in e.g.\n> > https://public-inbox.org/git/20150521061553.GA29269@glandium.org/\n> > \n> > The only (simple) workable way, given the current algorithm, to get an\n> > accurate view off rev-list is to essentially make slop infinite. This\n> > works fine, at the expense of runtime.\n> > \n> > Now, ignoring any modification for the above, I'm hitting another corner\n> > case in some other \"weird\" history, where I have 500k commits all with\n> > the same date. With such a commit dag, something as trivial as\n> > `git rev-list HEAD~..HEAD` goes through all commits from the root commit\n> > to HEAD, which takes multiple seconds, when the (obvious) output is one\n> > commit.\n> > \n> > It looks like the only way revision walking stops going through all the\n> > ancestry is through slop, and slop is essentially made infinite by the\n> > fact all commits have the same date (because of the date check in\n> > still_interesting(). By extension, this means the workaound for the\n> > first corner case above, which is to make slop infinite, essentially\n> > makes all rev walking go through the entire ancestry of the commits\n> > given on the command line.\n> > \n> > It feels like some cases of everybody_uninteresting should shorcut slop\n> > entirely, but considering the only way for slop to decrease at all is\n> > when everybody_uninteresting returns true, that would seem like a wrong\n> > assumption. But I'm also not sure what slop helps with in the first\n> > place (but I don't have a clear view of the broader picture of how the\n> > entire revision walking works).\n> > \n> > Anyways, a rather easy way to witness this happening is to create a\n> > dummy repo like:\n> >   git init foo\n> >   cd foo\n> >   for i in $(seq 1 50); do\n> >     echo $i > a;\n> >     git add a;\n> >     git commit -a -m $i;\n> >   done\n> > \n> > The something as simple as `git rev-list HEAD~..HEAD` will go through\n> > all 50 commits (assuming the script above created commits in the same\n> > second, which it did on my machine)\n> > \n> > By the time both HEAD~ and HEAD have been processed, the revision\n> > walking should have enough information to determine that it doesn't need\n> > to go further, but still does. Even with something like HEAD~2..HEAD,\n> > after the first round of processing parents it should be able to see\n> > there's not going to be any more interesting commits.\n> > \n> > I'm willing to dig into this, but if someone familiar with the\n> > algorithm could give me some hints as to what I might be missing in the\n> > big picture, that would be helpful.\n> \n> All the above is without commit-graph, I presume?  If so, then you\n> should give it a try, as it might bring immediate help in your\n> pathological repo.  With 5k commit in the same second (enforced via\n> 'export GIT_COMMITTER_DATE=$(date); for i in {1..5000} ...') I get:\n> \n>   $ best-of-five -q git rev-list HEAD~..HEAD\n>   0.069\n>   $ git commit-graph write --reachableComputing commit graph generation\n>   numbers: 100% (5000/5000), done.\n>   $ best-of-five -q git rev-list HEAD~..HEAD\n>   0.004\n\nI'm not observing any difference from using commit-graph, whether in\ntime or in the number of commits that are looked at in limit_list().\n\nMike\n"},{"id":"375840","messageId":"20190518041706.ct6ie5trvxgdhjar@glandium.org","threadId":"51119","inReplyTo":"20190518035828.pjaqfrkkvldhri6v@glandium.org","subject":"Re: Revision walking, commit dates, slop","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2019-05-18T04:17:06Z","receivedAt":"2019-05-18T04:17:11Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Sat, May 18, 2019 at 12:58:28PM +0900, Mike Hommey wrote:\n> On Sat, May 18, 2019 at 03:50:05AM +0200, SZEDER Gábor wrote:\n> > On Sat, May 18, 2019 at 09:54:12AM +0900, Mike Hommey wrote:\n> > > There are established corner cases, where in a repo where commit dates\n> > > are not monotonically increasing, revision walking can go horribly\n> > > wrong. This was discussed in the past in e.g.\n> > > https://public-inbox.org/git/20150521061553.GA29269@glandium.org/\n> > > \n> > > The only (simple) workable way, given the current algorithm, to get an\n> > > accurate view off rev-list is to essentially make slop infinite. This\n> > > works fine, at the expense of runtime.\n> > > \n> > > Now, ignoring any modification for the above, I'm hitting another corner\n> > > case in some other \"weird\" history, where I have 500k commits all with\n> > > the same date. With such a commit dag, something as trivial as\n> > > `git rev-list HEAD~..HEAD` goes through all commits from the root commit\n> > > to HEAD, which takes multiple seconds, when the (obvious) output is one\n> > > commit.\n> > > \n> > > It looks like the only way revision walking stops going through all the\n> > > ancestry is through slop, and slop is essentially made infinite by the\n> > > fact all commits have the same date (because of the date check in\n> > > still_interesting(). By extension, this means the workaound for the\n> > > first corner case above, which is to make slop infinite, essentially\n> > > makes all rev walking go through the entire ancestry of the commits\n> > > given on the command line.\n> > > \n> > > It feels like some cases of everybody_uninteresting should shorcut slop\n> > > entirely, but considering the only way for slop to decrease at all is\n> > > when everybody_uninteresting returns true, that would seem like a wrong\n> > > assumption. But I'm also not sure what slop helps with in the first\n> > > place (but I don't have a clear view of the broader picture of how the\n> > > entire revision walking works).\n> > > \n> > > Anyways, a rather easy way to witness this happening is to create a\n> > > dummy repo like:\n> > >   git init foo\n> > >   cd foo\n> > >   for i in $(seq 1 50); do\n> > >     echo $i > a;\n> > >     git add a;\n> > >     git commit -a -m $i;\n> > >   done\n> > > \n> > > The something as simple as `git rev-list HEAD~..HEAD` will go through\n> > > all 50 commits (assuming the script above created commits in the same\n> > > second, which it did on my machine)\n> > > \n> > > By the time both HEAD~ and HEAD have been processed, the revision\n> > > walking should have enough information to determine that it doesn't need\n> > > to go further, but still does. Even with something like HEAD~2..HEAD,\n> > > after the first round of processing parents it should be able to see\n> > > there's not going to be any more interesting commits.\n> > > \n> > > I'm willing to dig into this, but if someone familiar with the\n> > > algorithm could give me some hints as to what I might be missing in the\n> > > big picture, that would be helpful.\n> > \n> > All the above is without commit-graph, I presume?  If so, then you\n> > should give it a try, as it might bring immediate help in your\n> > pathological repo.  With 5k commit in the same second (enforced via\n> > 'export GIT_COMMITTER_DATE=$(date); for i in {1..5000} ...') I get:\n> > \n> >   $ best-of-five -q git rev-list HEAD~..HEAD\n> >   0.069\n> >   $ git commit-graph write --reachableComputing commit graph generation\n> >   numbers: 100% (5000/5000), done.\n> >   $ best-of-five -q git rev-list HEAD~..HEAD\n> >   0.004\n> \n> I'm not observing any difference from using commit-graph, whether in\n> time or in the number of commits that are looked at in limit_list().\n\n-c core.commitGraph=true does make a difference in time, but not in the\nnumber of commits looked at in limit_list(). So it's only faster because\neach iteration of the loop is faster. It means it's still dependent on\nthe depth of the dag, and the larger the repo will grow, the slower it\nwill get.\n\nMike\n"},{"id":"375850","messageId":"20190518120140.GB951@szeder.dev","threadId":"51119","inReplyTo":"20190518041706.ct6ie5trvxgdhjar@glandium.org","subject":"Re: Revision walking, commit dates, slop","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-05-18T12:01:40Z","receivedAt":"2019-05-18T12:01:47Z","isPatch":false,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Sat, May 18, 2019 at 01:17:06PM +0900, Mike Hommey wrote:\n> On Sat, May 18, 2019 at 12:58:28PM +0900, Mike Hommey wrote:\n> > On Sat, May 18, 2019 at 03:50:05AM +0200, SZEDER Gábor wrote:\n> > > On Sat, May 18, 2019 at 09:54:12AM +0900, Mike Hommey wrote:\n> > > > There are established corner cases, where in a repo where commit dates\n> > > > are not monotonically increasing, revision walking can go horribly\n> > > > wrong. This was discussed in the past in e.g.\n> > > > https://public-inbox.org/git/20150521061553.GA29269@glandium.org/\n> > > > \n> > > > The only (simple) workable way, given the current algorithm, to get an\n> > > > accurate view off rev-list is to essentially make slop infinite. This\n> > > > works fine, at the expense of runtime.\n> > > > \n> > > > Now, ignoring any modification for the above, I'm hitting another corner\n> > > > case in some other \"weird\" history, where I have 500k commits all with\n> > > > the same date. With such a commit dag, something as trivial as\n> > > > `git rev-list HEAD~..HEAD` goes through all commits from the root commit\n> > > > to HEAD, which takes multiple seconds, when the (obvious) output is one\n> > > > commit.\n> > > > \n> > > > It looks like the only way revision walking stops going through all the\n> > > > ancestry is through slop, and slop is essentially made infinite by the\n> > > > fact all commits have the same date (because of the date check in\n> > > > still_interesting(). By extension, this means the workaound for the\n> > > > first corner case above, which is to make slop infinite, essentially\n> > > > makes all rev walking go through the entire ancestry of the commits\n> > > > given on the command line.\n> > > > \n> > > > It feels like some cases of everybody_uninteresting should shorcut slop\n> > > > entirely, but considering the only way for slop to decrease at all is\n> > > > when everybody_uninteresting returns true, that would seem like a wrong\n> > > > assumption. But I'm also not sure what slop helps with in the first\n> > > > place (but I don't have a clear view of the broader picture of how the\n> > > > entire revision walking works).\n> > > > \n> > > > Anyways, a rather easy way to witness this happening is to create a\n> > > > dummy repo like:\n> > > >   git init foo\n> > > >   cd foo\n> > > >   for i in $(seq 1 50); do\n> > > >     echo $i > a;\n> > > >     git add a;\n> > > >     git commit -a -m $i;\n> > > >   done\n> > > > \n> > > > The something as simple as `git rev-list HEAD~..HEAD` will go through\n> > > > all 50 commits (assuming the script above created commits in the same\n> > > > second, which it did on my machine)\n> > > > \n> > > > By the time both HEAD~ and HEAD have been processed, the revision\n> > > > walking should have enough information to determine that it doesn't need\n> > > > to go further, but still does. Even with something like HEAD~2..HEAD,\n> > > > after the first round of processing parents it should be able to see\n> > > > there's not going to be any more interesting commits.\n> > > > \n> > > > I'm willing to dig into this, but if someone familiar with the\n> > > > algorithm could give me some hints as to what I might be missing in the\n> > > > big picture, that would be helpful.\n> > > \n> > > All the above is without commit-graph, I presume?  If so, then you\n> > > should give it a try, as it might bring immediate help in your\n> > > pathological repo.  With 5k commit in the same second (enforced via\n> > > 'export GIT_COMMITTER_DATE=$(date); for i in {1..5000} ...') I get:\n> > > \n> > >   $ best-of-five -q git rev-list HEAD~..HEAD\n> > >   0.069\n> > >   $ git commit-graph write --reachableComputing commit graph generation\n> > >   numbers: 100% (5000/5000), done.\n> > >   $ best-of-five -q git rev-list HEAD~..HEAD\n> > >   0.004\n> > \n> > I'm not observing any difference from using commit-graph, whether in\n> > time or in the number of commits that are looked at in limit_list().\n> \n> -c core.commitGraph=true does make a difference in time, but not in the\n> number of commits looked at in limit_list(). So it's only faster because\n> each iteration of the loop is faster. It means it's still dependent on\n> the depth of the dag, and the larger the repo will grow, the slower it\n> will get.\n\nOh, indeed.  Well, at least you'll waste about an order of magnitude\nless processor time until you figure out how to fix it :)\n\nBtw, once upon a time this was fast, but it became slow with commit\nc19d1b4e84 (Fix revision walk for commits with the same dates,\n2013-03-22).\n\n\n"},{"id":"375893","messageId":"8636laqdtf.fsf@gmail.com","threadId":"51119","inReplyTo":"20190518120140.GB951@szeder.dev","subject":"Re: Revision walking, commit dates, slop","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2019-05-19T22:28:28Z","receivedAt":"2019-05-19T22:28:35Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"SZEDER Gábor <szeder.dev@gmail.com> writes:\n> On Sat, May 18, 2019 at 01:17:06PM +0900, Mike Hommey wrote:\n>> On Sat, May 18, 2019 at 12:58:28PM +0900, Mike Hommey wrote:\n>>> On Sat, May 18, 2019 at 03:50:05AM +0200, SZEDER Gábor wrote:\n>>>> On Sat, May 18, 2019 at 09:54:12AM +0900, Mike Hommey wrote:\n[...]\n>>>>> There are established corner cases, where in a repo where commit dates\n>>>>> are not monotonically increasing, revision walking can go horribly\n>>>>> wrong. This was discussed in the past in e.g.\n>>>>> https://public-inbox.org/git/20150521061553.GA29269@glandium.org/\n>>>>> \n>>>>> The only (simple) workable way, given the current algorithm, to get an\n>>>>> accurate view off rev-list is to essentially make slop infinite. This\n>>>>> works fine, at the expense of runtime.\n>>>>> \n>>>>> Now, ignoring any modification for the above, I'm hitting another corner\n>>>>> case in some other \"weird\" history, where I have 500k commits all with\n>>>>> the same date. With such a commit dag, something as trivial as\n>>>>> `git rev-list HEAD~..HEAD` goes through all commits from the root commit\n>>>>> to HEAD, which takes multiple seconds, when the (obvious) output is one\n>>>>> commit.\n[...]\n>>>> All the above is without commit-graph, I presume?  If so, then you\n>>>> should give it a try, as it might bring immediate help in your\n>>>> pathological repo.  With 5k commit in the same second (enforced via\n>>>> 'export GIT_COMMITTER_DATE=$(date); for i in {1..5000} ...') I get:\n>>>> \n>>>>   $ best-of-five -q git rev-list HEAD~..HEAD\n>>>>   0.069\n>>>>   $ git commit-graph write --reachableComputing commit graph generation\n>>>>   numbers: 100% (5000/5000), done.\n>>>>   $ best-of-five -q git rev-list HEAD~..HEAD\n>>>>   0.004\n>>> \n>>> I'm not observing any difference from using commit-graph, whether in\n>>> time or in the number of commits that are looked at in limit_list().\n>> \n>> -c core.commitGraph=true does make a difference in time, but not in the\n>> number of commits looked at in limit_list(). So it's only faster because\n>> each iteration of the loop is faster. It means it's still dependent on\n>> the depth of the dag, and the larger the repo will grow, the slower it\n>> will get.\n>\n> Oh, indeed.  Well, at least you'll waste about an order of magnitude\n> less processor time until you figure out how to fix it :)\n>\n> Btw, once upon a time this was fast, but it became slow with commit\n> c19d1b4e84 (Fix revision walk for commits with the same dates,\n> 2013-03-22).\n\nThis might be related to the fact, that with generation numbers v1\n(i.e. topological levels) there were cases when using those generation\nnumbers for ordering caused performance regressions (e.g. for some parts\nof Linux kernel history).\n\nThere was an idea of replacing them with generation numbers v2 [1],\nwhich if I remember correctly was chosen to be corrected date (that is,\ncommitter date or one more than maximum of dates of parents).  This is\nincompatibile change; it turned out however that while commit-graph\nformat is versioned, unfortunately Git fails hard if commit-graph\nversion is too new, instead of falling back to not using commit graph.\n\n[1]: https://github.com/derrickstolee/gen-test\n\nStolee, could you tell us what is the current status on generation\nnumbers v2?  Thanks in advance.\n\nBest,\n--\nJakub Narębski\n"},{"id":"375897","messageId":"f14799c3-e343-eb41-3536-65de7e38fbd9@gmail.com","threadId":"51119","inReplyTo":"20190518041706.ct6ie5trvxgdhjar@glandium.org","subject":"Re: Revision walking, commit dates, slop","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-20T01:33:08Z","receivedAt":"2019-05-20T01:33:15Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/18/2019 12:17 AM, Mike Hommey wrote:\n> On Sat, May 18, 2019 at 12:58:28PM +0900, Mike Hommey wrote:\n>> On Sat, May 18, 2019 at 03:50:05AM +0200, SZEDER Gábor wrote:\n>>>\n>>> All the above is without commit-graph, I presume?  If so, then you\n>>> should give it a try, as it might bring immediate help in your\n>>> pathological repo.  With 5k commit in the same second (enforced via\n>>> 'export GIT_COMMITTER_DATE=$(date); for i in {1..5000} ...') I get:\n>>>\n>>>   $ best-of-five -q git rev-list HEAD~..HEAD\n>>>   0.069\n>>>   $ git commit-graph write --reachableComputing commit graph generation\n>>>   numbers: 100% (5000/5000), done.\n>>>   $ best-of-five -q git rev-list HEAD~..HEAD\n>>>   0.004\n>>\n>> I'm not observing any difference from using commit-graph, whether in\n>> time or in the number of commits that are looked at in limit_list().\n> \n> -c core.commitGraph=true does make a difference in time, but not in the\n> number of commits looked at in limit_list(). So it's only faster because\n> each iteration of the loop is faster. It means it's still dependent on\n> the depth of the dag, and the larger the repo will grow, the slower it\n> will get.\n\nThe plan is to use the commit-graph's generation numbers for these A..B\nqueries, but due to some cases when commit date is a _better_ heuristic\nthan generation numbers, we have not enabled them for A..B. You'll see\nthat 'git rev-list --topo-order -n 1 HEAD` will be much faster with the\ncommit-graph, but adding '--topo-order' to your 'HEAD~1..HEAD' query\nshould not change the time at all.\n\nSee [1] for the discussion about \"generation number v2\" which will allow\nus to use a better heuristic in these cases.\n\nThanks,\n-Stolee\n\n[1] https://public-inbox.org/git/6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com/\n"},{"id":"375907","messageId":"86mujhpewj.fsf@gmail.com","threadId":"51119","inReplyTo":"f14799c3-e343-eb41-3536-65de7e38fbd9@gmail.com","subject":"Re: Revision walking, commit dates, slop","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2019-05-20T11:02:36Z","receivedAt":"2019-05-20T11:02:41Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n> On 5/18/2019 12:17 AM, Mike Hommey wrote:\n>> On Sat, May 18, 2019 at 12:58:28PM +0900, Mike Hommey wrote:\n>>> On Sat, May 18, 2019 at 03:50:05AM +0200, SZEDER Gábor wrote:\n>>>>\n>>>> All the above is without commit-graph, I presume?  If so, then you\n>>>> should give it a try, as it might bring immediate help in your\n>>>> pathological repo.  With 5k commit in the same second (enforced via\n>>>> 'export GIT_COMMITTER_DATE=$(date); for i in {1..5000} ...') I get:\n>>>>\n>>>>   $ best-of-five -q git rev-list HEAD~..HEAD\n>>>>   0.069\n>>>>   $ git commit-graph write --reachableComputing commit graph generation\n>>>>   numbers: 100% (5000/5000), done.\n>>>>   $ best-of-five -q git rev-list HEAD~..HEAD\n>>>>   0.004\n>>>\n>>> I'm not observing any difference from using commit-graph, whether in\n>>> time or in the number of commits that are looked at in limit_list().\n>> \n>> -c core.commitGraph=true does make a difference in time, but not in the\n>> number of commits looked at in limit_list(). So it's only faster because\n>> each iteration of the loop is faster. It means it's still dependent on\n>> the depth of the dag, and the larger the repo will grow, the slower it\n>> will get.\n>\n> The plan is to use the commit-graph's generation numbers for these A..B\n> queries, but due to some cases when commit date is a _better_ heuristic\n> than generation numbers, we have not enabled them for A..B. You'll see\n> that 'git rev-list --topo-order -n 1 HEAD` will be much faster with the\n> commit-graph, but adding '--topo-order' to your 'HEAD~1..HEAD' query\n> should not change the time at all.\n>\n> See [1] for the discussion about \"generation number v2\" which will allow\n> us to use a better heuristic in these cases.\n>\n> [1] https://public-inbox.org/git/6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com/\n\nAre there any blockers that prevent the switch to this\n\"generation number v2\"?\n\n- Is it a problem with insufficient data to choose the correct numbering\n  as \"generation number v2' (there can be only one)?\n- Is it a problem with selected \"generation number v2\" being\n  incompatibile with gen v2, and Git failing when new version of\n  commit-graph is used instead of softly just not using commit-graph?\n- Or is it something else?\n\nBest,\n--\nJakub Narębski\n"},{"id":"375909","messageId":"cfa2c367-5cd7-add5-0293-caa75b103f34@gmail.com","threadId":"51119","inReplyTo":"86mujhpewj.fsf@gmail.com","subject":"Re: Revision walking, commit dates, slop","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-20T11:20:01Z","receivedAt":"2019-05-20T11:20:04Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/20/2019 7:02 AM, Jakub Narebski wrote:\n>\n> Are there any blockers that prevent the switch to this\n> \"generation number v2\"?\n> \n> - Is it a problem with insufficient data to choose the correct numbering\n>   as \"generation number v2' (there can be only one)?\n> - Is it a problem with selected \"generation number v2\" being\n>   incompatibile with gen v2, and Git failing when new version of\n>   commit-graph is used instead of softly just not using commit-graph?\n> - Or is it something else?\n\nThe switch becomes a bit complicated.\n\nFirst, the plan was to version the commit-graph file to v2, and that would\ninclude a byte in the header for the \"reachability index version\" [1]. Since\nolder clients fail hard on a newer file version, we are switching to instead\nincluding the reachability index version as a value in a more flexible \n\"metadata chunk\" [2]. Using the generation number column for the corrected\ncommit-date offsets (assuming we also guarantee the offset is strictly\nincreasing from parent to child), these new values will be backwards-\ncompatible _except_ for 'git commit-graph verify'.\n\nSecond, we need to pull the reachability index value into a commit slab.\nThe generation value is currently 32 bits, but we will expand that to\n64 as it stores a timestamp. The commit struct is a bit bloated already,\nso this will reduce the required memory space even when not using the\ncommit-graph. But, it requires some refactoring, including every place\nwhere we pass a \"min_generation\" needs to change type and name.\n\nThird and finally, we need to calculate the new values and change the\nread logic to sum the offset and commit-date (when the metadata chunk\nsays we are using corrected commit date).\n\nWhile none of this is _incredibly_ hard to do, it does require a bit\nof care. It's on my list to get to at some point, but making the file\nincremental is higher priority to me.\n\nThanks,\n-Stolee\n\n[1] https://public-inbox.org/git/pull.112.git.gitgitgadget@gmail.com/\n[2] https://public-inbox.org/git/87h8acivkh.fsf@evledraar.gmail.com/\n"},{"id":"375921","messageId":"86ftp9p7i8.fsf@gmail.com","threadId":"51119","inReplyTo":"cfa2c367-5cd7-add5-0293-caa75b103f34@gmail.com","subject":"Re: Revision walking, commit dates, slop","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2019-05-20T13:42:23Z","receivedAt":"2019-05-20T13:42:29Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n> On 5/20/2019 7:02 AM, Jakub Narebski wrote:\n>>\n>> Are there any blockers that prevent the switch to this\n>> \"generation number v2\"?\n>> \n>> - Is it a problem with insufficient data to choose the correct numbering\n>>   as \"generation number v2' (there can be only one)?\n>> - Is it a problem with selected \"generation number v2\" being\n>>   incompatibile with gen v2, and Git failing when new version of\n>>   commit-graph is used instead of softly just not using commit-graph?\n>> - Or is it something else?\n\nThanks for the explanation.\n\n> The switch becomes a bit complicated.\n>\n> First, the plan was to version the commit-graph file to v2, and that would\n> include a byte in the header for the \"reachability index version\" [1]. Since\n> older clients fail hard on a newer file version, we are switching to instead\n> including the reachability index version as a value in a more flexible \n> \"metadata chunk\" [2].\n\nUgh, that is bad.  The version number inn the commit-graph file format\nwas supposed to make it possible to easily change the format; now it\nlooks like we are stuck with workarounds until the released version that\ndies on never commit-graph file format version innstead of softly not\nutilizing the commit-graph file dies off.\n\nHow this issue got missed in review...\n\nIf we cannot change the format, all that is left is ading new chunks,\nand changes that conform to commit-graph file version 1.  \n\n>                      Using the generation number column for the corrected\n> commit-date offsets (assuming we also guarantee the offset is strictly\n> increasing from parent to child), these new values will be backwards-\n> compatible _except_ for 'git commit-graph verify'.\n\nO.K., so the \"generation number v2 (legacy)\" would be incremental and\nbackward-compatibile in use (though not in generation and validation).\n\nDo I understand it correctly how it is calculated:\n\n  corrected_date(C) = max(committer_date(C),\n                          max_{P ∈ parents(C)}(corrected_date(P)) + 1)\n  offset(C) = corrected_date(C) - committer_date(C)\n  gen_v2(C) = max(offset(C), max_{P ∈ parents(C)}(gen_v2(P)) + 1) \n\nDo you have benchmark for this \"monotonically offset corrected commit\ndate\" generation number in https://github.com/derrickstolee/git/commits/reach-perf\nand https://github.com/derrickstolee/gen-test ?\n\n\nAlso, what would happen if different versions of Git tried to add to\ncommit-graph in interleaved way, either with rewrite or incremental?\n\n> Second, we need to pull the reachability index value into a commit slab.\n\nIs commit slab documented somewhere in Documentation/technical/, or just\nin comments in commit-slab.h?\n\nAs I understand it, commit slab is Git-specific implementition of\ninside-out object storage for commit data (i.e. struct of arrays instead\nof array of structs), isn't it?  I wonder if using commit slab improves\ncache utilization...\n\n> The generation value is currently 32 bits, but we will expand that to\n> 64 as it stores a timestamp. The commit struct is a bit bloated already,\n> so this will reduce the required memory space even when not using the\n> commit-graph. But, it requires some refactoring, including every place\n> where we pass a \"min_generation\" needs to change type and name.\n\nCould this be done with Coccinelle's spatch, similar to\ne.g. contrib/coccinelle/commit.cocci?\n\n>\n> Third and finally, we need to calculate the new values and change the\n> read logic to sum the offset and commit-date (when the metadata chunk\n> says we are using corrected commit date).\n\nRight.\n\n> While none of this is _incredibly_ hard to do, it does require a bit\n> of care. It's on my list to get to at some point, but making the file\n> incremental is higher priority to me.\n\nAll right, I can understand that.\n\n> [1] https://public-inbox.org/git/pull.112.git.gitgitgadget@gmail.com/\n> [2] https://public-inbox.org/git/87h8acivkh.fsf@evledraar.gmail.com/\n\nBest,\n--\nJakub Narębski\n"},{"id":"375967","messageId":"864l5opuz1.fsf@gmail.com","threadId":"51119","inReplyTo":"86ftp9p7i8.fsf@gmail.com","subject":"Re: Revision walking, commit dates, slop","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2019-05-20T23:27:46Z","receivedAt":"2019-05-20T23:27:52Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jakub Narebski <jnareb@gmail.com> writes:\n> Derrick Stolee <stolee@gmail.com> writes:\n>> On 5/20/2019 7:02 AM, Jakub Narebski wrote:\n>>>\n>>> Are there any blockers that prevent the switch to this\n>>> \"generation number v2\"?\n[...]\n\n>>                      Using the generation number column for the corrected\n>> commit-date offsets (assuming we also guarantee the offset is strictly\n>> increasing from parent to child), these new values will be backwards-\n>> compatible _except_ for 'git commit-graph verify'.\n>\n> O.K., so the \"generation number v2 (legacy)\" would be incremental and\n> backward-compatibile in use (though not in generation and validation).\n>\n> Do I understand it correctly how it is calculated:\n>\n>   corrected_date(C) = max(committer_date(C),\n>                           max_{P ∈ parents(C)}(corrected_date(P)) + 1)\n\nThis should probably read\n\n    offset_date(P) = committer_date(P) + gen_v2(P)\n    corrected_date(C) = max(committer_date(C),\n                            max_{P ∈ parents(C)}(offset_date(P)) + 1)    \n\n>   offset(C) = corrected_date(C) - committer_date(C)\n>   gen_v2(C) = max(offset(C), max_{P ∈ parents(C)}(gen_v2(P)) + 1) \n>\n> Do you have benchmark for this \"monotonically offset corrected commit\n> date\" generation number in https://github.com/derrickstolee/git/commits/reach-perf\n> and https://github.com/derrickstolee/gen-test ?\n\n--\nJakub Narębski\n"},{"id":"375973","messageId":"88662e18-db51-cb48-3307-0ea2a91c4ebe@gmail.com","threadId":"51119","inReplyTo":"864l5opuz1.fsf@gmail.com","subject":"Re: Revision walking, commit dates, slop","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-21T01:20:45Z","receivedAt":"2019-05-21T01:20:48Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/20/2019 7:27 PM, Jakub Narebski wrote:\n> Jakub Narebski <jnareb@gmail.com> writes:\n>> Derrick Stolee <stolee@gmail.com> writes:\n>>> On 5/20/2019 7:02 AM, Jakub Narebski wrote:\n>>>>\n>>>> Are there any blockers that prevent the switch to this\n>>>> \"generation number v2\"?\n> [...]\n> \n>>>                      Using the generation number column for the corrected\n>>> commit-date offsets (assuming we also guarantee the offset is strictly\n>>> increasing from parent to child), these new values will be backwards-\n>>> compatible _except_ for 'git commit-graph verify'.\n>>\n>> O.K., so the \"generation number v2 (legacy)\" would be incremental and\n>> backward-compatibile in use (though not in generation and validation).\n>>\n>> Do I understand it correctly how it is calculated:\n>>\n>>   corrected_date(C) = max(committer_date(C),\n>>                           max_{P ∈ parents(C)}(corrected_date(P)) + 1)\n> \n> This should probably read\n> \n>     offset_date(P) = committer_date(P) + gen_v2(P)\n>     corrected_date(C) = max(committer_date(C),\n>                             max_{P ∈ parents(C)}(offset_date(P)) + 1)  \n\nThe final definition needs two conditions on the offset of a commit C for\nevery parent P:\n\n 1. committer_date(C) + offset(C) > committer_date(P) + offset(P)\n 2. offset(C) > offset(P)\n\nCondition (1) will give us the performance benefits related to the\ncommitter-date heuristic. Condition (2) will give us backwards-compatibility\nwith generation numbers.\n\nThanks,\n-Stolee\n"},{"id":"375976","messageId":"20190521020009.GC32230@google.com","threadId":"51119","inReplyTo":"20190518015005.GA951@szeder.dev","subject":"Re: Revision walking, commit dates, slop","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2019-05-21T02:00:09Z","receivedAt":"2019-05-21T02:00:13Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"SZEDER Gábor wrote:\n> On Sat, May 18, 2019 at 09:54:12AM +0900, Mike Hommey wrote:\n\n>> There are established corner cases, where in a repo where commit dates\n>> are not monotonically increasing,\n[...]\n> All the above is without commit-graph, I presume?  If so, then you\n> should give it a try, as it might bring immediate help in your\n> pathological repo.  With 5k commit in the same second (enforced via\n> 'export GIT_COMMITTER_DATE=$(date); for i in {1..5000} ...') I get:\n\nJust to emphasize this point: one field in the commit-graph file is a\ngeneration number (or more generally, a \"reachability index\" in the\nstandard jargon).  The reason I'm excited about having this field is\nthat it will allow us to stop playing games with slop.\n\nSo please join forces with Stolee and help us get to that future\nsooner. :)\n\nThanks,\nJonathan\n"},{"id":"375995","messageId":"20190521131438.58394-1-dstolee@microsoft.com","threadId":"51119","inReplyTo":"f14799c3-e343-eb41-3536-65de7e38fbd9@gmail.com","subject":"[PATCH] revision: use generation for A..B --topo-order queries","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-21T13:14:38Z","receivedAt":"2019-05-21T13:14:43Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"If a commit-graph exists with computed generation numbers, then a\n'git rev-list --topo-order -n <N> <rev>' query will use those generation\nnumbers to reduce the number of commits walked before writing N commits.\n\nOne caveat put in b454241 (revision.c: generation-based topo-order\nalgorithm, 2018-11-01) was to not enable the new algorithm for queries\nwith a revision range \"A..B\". The logic was placed to walk from \"A\" and\nmark those commits as uninteresting, but the performance was actually\nworse than the existing logic in some cases.\n\nThe root cause of this performance degradation is that generation\nnumbers _increase_ the number of commits we walk relative to the\nexisting heuristic of walking by commit date. While generation numbers\nactually guarantee that the algorithm is correct, the existing logic\nis very rarely wrong and that added requirement is not worth the cost.\n\nThis motivates the planned \"corrected commit date\" to replace\ngeneration numbers in a future version of Git.\n\nThe current change enables the logic to use whatever reachability\nindex is currently in the commit-graph (generation numbers or\ncorrected commit date).\n\nThe limited flag in struct rev_info forces a full walk of the\ncommit history (after discovering the A..B range). Previosuly, it\nis enabled whenever we see an uninteresting commit. We prevent\nenabling the parameter when we are planning to use the reachability\nindex for a topo-order.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n\nMike,\n\nIf you have the chance, then please apply this patch (on v2.22.0-rc1)\nand re-run your test. This will confirm if my thoughts on this matter\nare correct.\n\nThanks,\n-Stolee\n\n revision.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/revision.c b/revision.c\nindex d4aaf0ef25..be6ccf5786 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -436,7 +436,9 @@ static struct commit *handle_commit(struct rev_info *revs,\n \t\t\tdie(\"unable to parse commit %s\", name);\n \t\tif (flags & UNINTERESTING) {\n \t\t\tmark_parents_uninteresting(commit);\n-\t\t\trevs->limited = 1;\n+\n+\t\t\tif (!revs->topo_order || !generation_numbers_enabled(the_repository))\n+\t\t\t\trevs->limited = 1;\n \t\t}\n \t\tif (revs->sources) {\n \t\t\tchar **slot = revision_sources_at(revs->sources, commit);\n-- \n2.22.0.rc1\n\n"},{"id":"375997","messageId":"20190521135953.214701-1-dstolee@microsoft.com","threadId":"51119","inReplyTo":"20190521131438.58394-1-dstolee@microsoft.com","subject":"[PATCH 2/2] revision: keep topo-walk free of unintersting commits","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-21T13:59:53Z","receivedAt":"2019-05-21T13:59:59Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"When updating the topo-order walk in b454241 (revision.c: generation-based\ntopo-order algorithm, 2018-11-01), the logic was a huge rewrite of the\nwalk logic. In that massive change, we accidentally included the\nUNINTERESTING commits in expand_topo_walk(). This means that a simple\nquery like\n\n    git rev-list --topo-order HEAD~1..HEAD\n\nwill expand the topo walk for all commits reachable from HEAD, and not\njust one commit.\n\nThis change should speed up these cases, but there is still a need\nfor corrected commit-date for some A..B queries.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n\nSorry for the patch-spam, but I took a moment to check this command\non the Git repo, and was able to reproduce the slowness. That didn't\nmake sense to me, so I added some log messages to expand_topo_walk()\nand notices we were walking the UNINITERESTING commits. This is part\nof the reason the new logic is slower for A..B commands, but not the\nwhole reason.\n\nYou'll want this patch as well for a test.\n\nThanks,\n-Stolee\n\n revision.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/revision.c b/revision.c\nindex be6ccf5786..621feb9df7 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -3265,6 +3265,9 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n \t\tstruct commit *parent = p->item;\n \t\tint *pi;\n \n+\t\tif (parent->object.flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\n \t\tif (parse_commit_gently(parent, 1) < 0)\n \t\t\tcontinue;\n \n-- \n2.22.0.rc1\n\n"},{"id":"376036","messageId":"20190522021928.tsmg2rij6l44xvdj@glandium.org","threadId":"51119","inReplyTo":"20190521135953.214701-1-dstolee@microsoft.com","subject":"Re: [PATCH 2/2] revision: keep topo-walk free of unintersting commits","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2019-05-22T02:19:28Z","receivedAt":"2019-05-22T02:19:33Z","isPatch":true,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Tue, May 21, 2019 at 09:59:53AM -0400, Derrick Stolee wrote:\n> When updating the topo-order walk in b454241 (revision.c: generation-based\n> topo-order algorithm, 2018-11-01), the logic was a huge rewrite of the\n> walk logic. In that massive change, we accidentally included the\n> UNINTERESTING commits in expand_topo_walk(). This means that a simple\n> query like\n> \n>     git rev-list --topo-order HEAD~1..HEAD\n> \n> will expand the topo walk for all commits reachable from HEAD, and not\n> just one commit.\n> \n> This change should speed up these cases, but there is still a need\n> for corrected commit-date for some A..B queries.\n> \n> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>\n> ---\n> \n> Sorry for the patch-spam, but I took a moment to check this command\n> on the Git repo, and was able to reproduce the slowness. That didn't\n> make sense to me, so I added some log messages to expand_topo_walk()\n> and notices we were walking the UNINITERESTING commits. This is part\n> of the reason the new logic is slower for A..B commands, but not the\n> whole reason.\n> \n> You'll want this patch as well for a test.\n\nBoth patches help, thanks.\n\nMike\n"},{"id":"376063","messageId":"86lfyyny0p.fsf@gmail.com","threadId":"51119","inReplyTo":"88662e18-db51-cb48-3307-0ea2a91c4ebe@gmail.com","subject":"Re: Revision walking, commit dates, slop","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2019-05-22T18:29:26Z","receivedAt":"2019-05-22T18:29:34Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n> On 5/20/2019 7:27 PM, Jakub Narebski wrote:\n>> Jakub Narebski <jnareb@gmail.com> writes:\n>>> Derrick Stolee <stolee@gmail.com> writes:\n>>>> On 5/20/2019 7:02 AM, Jakub Narebski wrote:\n>>>>>\n>>>>> Are there any blockers that prevent the switch to this\n>>>>> \"generation number v2\"?\n>> [...]\n>> \n>>>>                      Using the generation number column for the corrected\n>>>> commit-date offsets (assuming we also guarantee the offset is strictly\n>>>> increasing from parent to child), these new values will be backwards-\n>>>> compatible _except_ for 'git commit-graph verify'.\n>>>\n>>> O.K., so the \"generation number v2 (legacy)\" would be incremental and\n>>> backward-compatibile in use (though not in generation and validation).\n>>>\n>>> Do I understand it correctly how it is calculated:\n>>>\n>>>   corrected_date(C) = max(committer_date(C),\n>>>                           max_{P ∈ parents(C)}(corrected_date(P)) + 1)\n>> \n>> This should probably read\n>> \n>>     offset_date(P) = committer_date(P) + gen_v2(P)\n>>     corrected_date(C) = max(committer_date(C),\n>>                             max_{P ∈ parents(C)}(offset_date(P)) + 1)\n\nRestating it yet again:\n\n   A.  corrected_date(C) = max(committer_date(C),\n                               max_P(committer_date(P) + offset(P)) + 1)\n\n   B.  offset(C) = max(corrected_date(C) - committer_date(C),\n                       max_P(offset(P)) + 1)\n\n> The final definition needs two conditions on the offset of a commit C for\n> every parent P:\n>\n>  1. committer_date(C) + offset(C) > committer_date(P) + offset(P)\n>  2. offset(C) > offset(P)\n\nThe equation (B) ensures the (2) condition, i.e offset(C) > offset(P).\nThe equation (A) ensures that condition (1) is fulfulled, because from\n(B) we have\n\n   corrected_date(C) <= committer_date(C) + offset(C)\n\nThis from (B) and (A( we get:\n\n   committer_date(C) + offset(C) >= corrected_date(C) >\n                                 >  committer_date(P) + offset(P)\n\n> Condition (1) will give us the performance benefits related to the\n> committer-date heuristic. Condition (2) will give us backwards-compatibility\n> with generation numbers.\n\nWell, we should check/test if performance benefits of \"offset date\"\n(\"corrected date with rising offset\") truly holds.\n\nBest,\n--\nJakub Narębski\n"},{"id":"376066","messageId":"f1f2c7f5-9b78-8404-2738-ab895a06c133@gmail.com","threadId":"51119","inReplyTo":"86lfyyny0p.fsf@gmail.com","subject":"Re: Revision walking, commit dates, slop","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-22T19:06:32Z","receivedAt":"2019-05-22T19:06:38Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/22/2019 2:29 PM, Jakub Narebski wrote:\n> Derrick Stolee <stolee@gmail.com> writes:\n>> On 5/20/2019 7:27 PM, Jakub Narebski wrote:\n> Restating it yet again:\n> \n>    A.  corrected_date(C) = max(committer_date(C),\n>                                max_P(committer_date(P) + offset(P)) + 1)\n> \n>    B.  offset(C) = max(corrected_date(C) - committer_date(C),\n>                        max_P(offset(P)) + 1)\n\nThe problem with this definition is that it \"defines\" the corrected date, and\nthen _adjusts_ it by updating the offset. I consider\n\n\tcorrected_date(C) = committer_date(C) + offset(C)\n\nto be part of the definition. You could restate the definition as follows:\n\n\tcorrected_date = max(committer_date(C) + max_P(offset(P)) + 1,\n        \t             max_P(corrected_date(P)))\n\nor, equivalently\n\n\tcorrected_date = max(committer_date(C) + max_P(offset(P)) + 1,\n        \t             max_P(committer_date(P) + offset(P)))\n\nThis definition, in a single step, satisfies the conditions below:\n\n> \n>> The final definition needs two conditions on the offset of a commit C for\n>> every parent P:\n>>\n>>  1. committer_date(C) + offset(C) > committer_date(P) + offset(P)\n>>  2. offset(C) > offset(P)\n\nPlus, the \"+ 1\" in the first step takes into account that \"0\" is a special offset\nvalue in the commit-graph file format meaning \"not computed\".\n\n> Well, we should check/test if performance benefits of \"offset date\"\n> (\"corrected date with rising offset\") truly holds.\n\nYes, a full performance test will be required. I have full confidence that the\nmonotonic offset requirement will have only positive effect. That is, it will\nnot affect the case where committer-date was better than generation number, but will\nhelp the cases where all the committer-dates are equal.\n\nThanks,\n-Stolee\n\n"},{"id":"376127","messageId":"8636l4rifi.fsf@gmail.com","threadId":"51119","inReplyTo":"f1f2c7f5-9b78-8404-2738-ab895a06c133@gmail.com","subject":"Re: Revision walking, commit dates, slop","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2019-05-23T21:04:49Z","receivedAt":"2019-05-23T21:04:54Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n> On 5/22/2019 2:29 PM, Jakub Narebski wrote:\n>> Derrick Stolee <stolee@gmail.com> writes:\n>>> On 5/20/2019 7:27 PM, Jakub Narebski wrote:\n>>\n>> Restating it yet again:\n>> \n>>    A.  corrected_date(C) = max(committer_date(C),\n>>                                max_P(committer_date(P) + offset(P)) + 1)\n>> \n>>    B.  offset(C) = max(corrected_date(C) - committer_date(C),\n>>                        max_P(offset(P)) + 1)\n>\n> The problem with this definition is that it \"defines\" the corrected date, and\n> then _adjusts_ it by updating the offset.\n\nFor me equation (A) was just an intermediate step; we might call it\nadjusted_date(C) or temp_date(C) instead.\n\nNote that with the following adjustment\n\n          corrected_date(C) = max(committer_date(C),\n                                  max_P(corrected_date(P)) + 1)\n\nit is +1 corrected \"V3: Corrected Commit Date\" from gen-test.\n\n> I consider\n>\n> \tcorrected_date(C) = committer_date(C) + offset(C)\n>\n> to be part of the definition. You could restate the definition as follows:\n>\n> \tcorrected_date = max(committer_date(C) + max_P(offset(P)) + 1,\n>         \t             max_P(corrected_date(P)))\n>\n> or, equivalently\n>\n> \tcorrected_date = max(committer_date(C) + max_P(offset(P)) + 1,\n>         \t             max_P(committer_date(P) + offset(P)))\n>\n> This definition, in a single step, satisfies the conditions below:\n>\n>> \n>>> The final definition needs two conditions on the offset of a commit C for\n>>> every parent P:\n>>>\n>>>  1. committer_date(C) + offset(C) > committer_date(P) + offset(P)\n>>>  2. offset(C) > offset(P)\n\nI think it is easier to prove the conditions (1) and (2) using two-step\ndefinition (A) + (B), as I have shown in previous email.\n\nAlso, what we need to calculate and store is offset(C), not\noffset_date(C) (i.e. corrected_date(C), if you prefer).\n\n> Plus, the \"+ 1\" in the first step takes into account that \"0\" is a special offset\n> value in the commit-graph file format meaning \"not computed\".\n\nThat assumes that max_P(function(P)) over empty set of P is taken to be\nzero.  Also, I think two step definition has the same property.\n\n>> Well, we should check/test if performance benefits of \"offset date\"\n>> (\"corrected date with rising offset\") truly holds.\n>\n> Yes, a full performance test will be required. I have full confidence that the\n> monotonic offset requirement will have only positive effect. That is, it will\n> not affect the case where committer-date was better than generation number, but will\n> help the cases where all the committer-dates are equal.\n\nI worry that monotonic offset corrected date would behave like\ntopological levels (i.e. like current generation number v1) in more\ncases rather than like commit date heuristics.\n\nP.S. there is _theoretical_ problem with all date-offset based\ngeneration numbers (slightly more likely to occur for monotonical\noffset), namely that in the commit-graph format v1 we have 34 bits for\ncommit date timestamp, but only 30 bits for offset; and there might be\nthe case where offset do not fit in 30 bits.  It would be however very\nunlikely, e.g. commit date of 2028, then commit date of 1970 (timestamp\nequal to zero).\n\nRegards,\n--\nJakub Narębski\n"},{"id":"377943","messageId":"86mui63xwr.fsf@gmail.com","threadId":"51119","inReplyTo":"86ftp9p7i8.fsf@gmail.com","subject":"Re: Revision walking, commit dates, slop","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2019-06-25T07:51:48Z","receivedAt":"2019-06-25T07:51:56Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jakub Narebski <jnareb@gmail.com> writes:\n> Derrick Stolee <stolee@gmail.com> writes:\n>> On 5/20/2019 7:02 AM, Jakub Narebski wrote:\n>>>\n>>> Are there any blockers that prevent the switch to this\n>>> \"generation number v2\"?\n>>> \n>>> - Is it a problem with insufficient data to choose the correct numbering\n>>>   as \"generation number v2' (there can be only one)?\n>>> - Is it a problem with selected \"generation number v2\" being\n>>>   incompatibile with gen v2, and Git failing when new version of\n>>>   commit-graph is used instead of softly just not using commit-graph?\n>>> - Or is it something else?\n[...]\n\n>>                      Using the generation number column for the corrected\n>> commit-date offsets (assuming we also guarantee the offset is strictly\n>> increasing from parent to child), these new values will be backwards-\n>> compatible _except_ for 'git commit-graph verify'.\n>\n> O.K., so the \"generation number v2 (legacy)\" would be incremental and\n> backward-compatibile in use (though not in generation and validation).\n>\n> Do I understand it correctly how it is calculated:\n>\n>   corrected_date(C) = max(committer_date(C),\n>                           max_{P ∈ parents(C)}(corrected_date(P)) + 1)\n>   offset(C) = corrected_date(C) - committer_date(C)\n>   gen_v2(C) = max(offset(C), max_{P ∈ parents(C)}(gen_v2(P)) + 1) \n\nDo you remember who first came up with this idea for backward\ncompatibile corrected commit date offsets (monotonically offset\ncorrected date)?\n\n> Do you have benchmark for this \"monotonically offset corrected commit\n> date\" generation number in https://github.com/derrickstolee/git/commits/reach-perf\n> and https://github.com/derrickstolee/gen-test ?\n\nI guess this will have to wait...\n\nBest,\n--\nJakub Narębski\n"},{"id":"377965","messageId":"55fad895-2c18-5a91-79b9-7b958fe280c6@gmail.com","threadId":"51119","inReplyTo":"86mui63xwr.fsf@gmail.com","subject":"Re: Revision walking, commit dates, slop","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-06-25T10:54:29Z","receivedAt":"2019-06-25T10:54:34Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/25/2019 3:51 AM, Jakub Narebski wrote:\n> Jakub Narebski <jnareb@gmail.com> writes:\n>> Derrick Stolee <stolee@gmail.com> writes:\n>>> On 5/20/2019 7:02 AM, Jakub Narebski wrote:\n>>>>\n>>>> Are there any blockers that prevent the switch to this\n>>>> \"generation number v2\"?\n>>>>\n>>>> - Is it a problem with insufficient data to choose the correct numbering\n>>>>   as \"generation number v2' (there can be only one)?\n>>>> - Is it a problem with selected \"generation number v2\" being\n>>>>   incompatibile with gen v2, and Git failing when new version of\n>>>>   commit-graph is used instead of softly just not using commit-graph?\n>>>> - Or is it something else?\n> [...]\n> \n>>>                      Using the generation number column for the corrected\n>>> commit-date offsets (assuming we also guarantee the offset is strictly\n>>> increasing from parent to child), these new values will be backwards-\n>>> compatible _except_ for 'git commit-graph verify'.\n>>\n>> O.K., so the \"generation number v2 (legacy)\" would be incremental and\n>> backward-compatibile in use (though not in generation and validation).\n>>\n>> Do I understand it correctly how it is calculated:\n>>\n>>   corrected_date(C) = max(committer_date(C),\n>>                           max_{P ∈ parents(C)}(corrected_date(P)) + 1)\n>>   offset(C) = corrected_date(C) - committer_date(C)\n>>   gen_v2(C) = max(offset(C), max_{P ∈ parents(C)}(gen_v2(P)) + 1) \n> \n> Do you remember who first came up with this idea for backward\n> compatibile corrected commit date offsets (monotonically offset\n> corrected date)?\n\nI remember saying that the \"corrected commit date\" that I had suggested\nwas weak because it was not backwards-compatible with generation numbers\nif you are only looking at the offsets. I don't remember who suggested\nsimply increasing the offset so they do become backwards-compatible.\n \n>> Do you have benchmark for this \"monotonically offset corrected commit\n>> date\" generation number in https://github.com/derrickstolee/git/commits/reach-perf\n>> and https://github.com/derrickstolee/gen-test ?\n> \n> I guess this will have to wait...\n\nI have not had time to revisit this topic and re-run performance\nnumbers, sorry.\n\n-Stolee\n"},{"id":"382544","messageId":"86o8ziatb2.fsf_-_@gmail.com","threadId":"51119","inReplyTo":"55fad895-2c18-5a91-79b9-7b958fe280c6@gmail.com","subject":"[RFC/PATCH] commit-graph: generation v5 (backward compatible date ceiling)","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2019-09-18T08:43:13Z","receivedAt":"2019-09-18T08:43:21Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n> On 6/25/2019 3:51 AM, Jakub Narebski wrote:\n>> Jakub Narebski <jnareb@gmail.com> writes:\n>>> Derrick Stolee <stolee@gmail.com> writes:\n[...]\n>>> O.K., so the \"generation number v2 (legacy)\" would be incremental and\n>>> backward-compatibile in use (though not in generation and validation).\n[...]\n>>> Do you have benchmark for this \"monotonically offset corrected commit\n>>> date\" generation number in https://github.com/derrickstolee/git/commits/reach-perf\n>>> and https://github.com/derrickstolee/gen-test ?\n>> \n>> I guess this will have to wait...\n>\n> I have not had time to revisit this topic and re-run performance\n> numbers, sorry.\n\nI have created pull requests against `reach-perf` branch of\nderrickstolee/git repository[1], and companion pull request against\ngen-test repository[2] with proposed prototype of backward-compatible\ncorrected commit date (with monotonic offsets).\n\nCould you please run the tests for this generation number v5?  I was not\nable to do so.  It was my first time trying to compile Git on MS\nWindows, and while there were no problems compiling `master` (well,\nexcept for compilation taking a long time), I was unable to do it for\n`reach-perf` branch because of independent of change compilation errors.\n\nIt would be good to test also the legacy mode, i.e. old Git (using\ngeneration number v0, i.e. topological levels (shortest path from node\nto sink, plus one) with all backward-compatible generation numbers, or\nat least generation number v5.\n\n\nDo I understand it correctly that for the time being because of\nbackward-compatibility concerns instead of incrementing the version\nnumber there would be used some kind of \"metadata\" chunk (at least until\nversion of Git that fails hard, instead of turning off commit-graph\nfeature softly, on unknown version numbers dies out).  Is there some\nproposal how such chunk should look like?\n\n[1]: https://github.com/derrickstolee/git/pull/10\n[2]: https://github.com/derrickstolee/gen-test/pull/1\n\n--- >8 ---- >8 ---- >8 ---- >8 ---- >8 ---- >8 ---- >8 ---- >8 ----\nFrom: Jakub Narębski <jnareb@gmail.com>\nSubject: [PATCH] commit-graph: generation v5 (backward compatible date ceiling)\n\nThis generation number option is backward-compatible (with\nreachability index v0) version of the generation number v3, that is\nthe corrected commit date.  It takes the simple approach of faking\n\"commit dates\" being in the right order by adding an offset to the\ncommit date (which is stored in the generation number column), so the\nmodified commit date is always at least one more than the maximum\nmodified commit date of all ancestors.  Additionally the offset itself\nis adjusted in such way that the offset of a commit is always at least\none more than the offsets of all ancestors.\n\nTwo following conditions are satisfied on the offset of a commit C for\nevery parent P:\n\n 1. committer_date(C) + offset(C) > committer_date(P) + offset(P)\n 2. offset(C) > offset(P)\n\nThis reachability index is locally computable, which means it is\ncompatible with incremental commit graph feature.\n\nIt has the same problem as v3, namely that we have a \"maximum clock\nskew\" based on the maximum generation number we can store, only more\nso.\n\nNote: it includes incidental whitespace cleanups for v3 code.\n\nSigned-off-by: Jakub Narębski <jnareb@gmail.com>\n---\nNote that the diff looks a bit strange in the part adding the code for\nthe new compute_generation_numbers_5() subroutine, because it got\nentangled in whitespace cleanup (which I shouldn't do, I'm sorry).\n\nRelevant part of README.md from `gen-test` repository:\n\n--------\n**V5: Corrected Commit Date with Strictly Monotonic Offset.**\nFor a commit C, let its _offset commit date_ (denoted by odate(C))\nbe a commit date plus some offset, i.e. odate(C) = date(C) + offset(C),\nsuch that:\n\n1. Offset commit date is greater than the maximum of the commit date\n   of C and the offset commit dates of its parents.\n\n     If odate(A) < odate(B), then A cannot reach B.\n\n2. Offset of a commit is one more than the maximum offset of a parent,\n   or more\n\n     If offset(A) < offset(B), then A cannot reach B.\n\nThis is backward-compatible version of V3: Corrected Commit Date.\n\n### Comparing Reachability Index Versions Viability\n[...]\n| Index                     | Compatible? | Immutable? | Local? |\n|---------------------------|-------------|------------|--------|\n| Minimum Generation Number | Yes         | Yes        | Yes    |\n| (Epoch, Date) pairs       | Yes         | Yes        | Yes    |\n| Maximum Generation Number | Yes         | No         | No     |\n| Corrected Commit Date     | No          | Yes        | Yes    |\n| FELINE index              | Yes         | No         | No     |\n| Offset Commit Date *NEW*  | Yes         | Yes        | Yes    |\n\n_Note:_ The corrected commit date uses the generation number column\nto store an offset of \"how much do I need to add to my commit date\nto get my corrected commit date?\" The values stored in that column\nare then not backwards-compatible.\n\n_Note:_ The corrected commit date with strictly monotonic offset also\nuses the generation number column to store the date offset, but the\noffset alone can be used as generation number (as reachability index)\nitself.\n\n\n commit-graph.c | 126 +++++++++++++++++++++++++++++++++++++------------\n 1 file changed, 95 insertions(+), 31 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 91863d4895..633b4b24f8 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -99,10 +99,9 @@ int compare_generations(struct generation *a, struct generation *b)\n \t\t\treturn 1;\n \t\treturn 0;\n \n-\tcase 3:\n-\t\tta = a->date + a->value1;\n-\t\ttb = b->date + b->value1;\n-\n+\tcase 3: /* V3: Corrected Commit Date */\n+\tcase 5: /* V5: Strictly Monotonic Corrected Commit Date */\n+\t\t/* handle special cases, i.e. commits outside commit graph */\n \t\tif (a->value1 == GENERATION_NUMBER_INFINITY) {\n \t\t\tif (b->value1 == GENERATION_NUMBER_INFINITY)\n \t\t\t\treturn 0;\n@@ -112,6 +111,10 @@ int compare_generations(struct generation *a, struct generation *b)\n \t\t\treturn -1;\n \t\t}\n \n+\t\t/* corrected commit date = date + offset (correction) */\n+\t\tta = a->date + a->value1;\n+\t\ttb = b->date + b->value1;\n+\n \t\tif (ta < tb)\n \t\t\treturn -1;\n \t\tif (ta > tb)\n@@ -162,6 +165,7 @@ void get_generation_version_from_commit(const struct commit *c,\n \n \t\tcase 1:\n \t\tcase 3:\n+\t\tcase 5:\n \t\t\tgen->value1 = c->generation;\n \t\t\tgen->date = c->date;\n \t\t\tbreak;\n@@ -212,9 +216,10 @@ void set_generation_below_commit(const struct commit *c, struct generation *g)\n \t\t\tbreak;\n \n \t\tcase 3:\n+\t\tcase 5: /* ??? */\n \t\t\tif (g->value1 + g->date >= gc.value1 + gc.date) {\n \t\t\t\tg->value1 = 0;\n-\t\t\t\tg->date = gc.value1 + gc.date;\t\t\t\n+\t\t\t\tg->date = gc.value1 + gc.date;\n \t\t\t}\n \t\t\tbreak;\n \n@@ -363,7 +368,7 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)\n \t\t\telse\n \t\t\t\tgraph->chunk_large_edges = data + chunk_offset;\n \t\t\tbreak;\n-\t\t\n+\n \t\tcase GRAPH_CHUNKID_FELINE:\n \t\t\tif (graph->chunk_feline_gen)\n \t\t\t\tchunk_repeated = 1;\n@@ -971,27 +976,27 @@ static void compute_generation_numbers_3(struct packed_commit_list *commits)\n \tint i;\n \tstruct commit_list *list = NULL;\n \n-        for (i = 0; i < commits->nr; i++) {\n-                if (commits->list[i]->generation != GENERATION_NUMBER_INFINITY &&\n-                    commits->list[i]->generation != GENERATION_NUMBER_ZERO)\n-                        continue;\n+\tfor (i = 0; i < commits->nr; i++) {\n+\t\tif (commits->list[i]->generation != GENERATION_NUMBER_INFINITY &&\n+\t\t\tcommits->list[i]->generation != GENERATION_NUMBER_ZERO)\n+\t\t\tcontinue;\n \n-                commit_list_insert(commits->list[i], &list);\n+\t\tcommit_list_insert(commits->list[i], &list);\n \n-                while (list) {\n-                        struct commit *current = list->item;\n-                        struct commit_list *parent;\n-                        int all_parents_computed = 1;\n+\t\twhile (list) {\n+\t\t\tstruct commit *current = list->item;\n+\t\t\tstruct commit_list *parent;\n+\t\t\tint all_parents_computed = 1;\n \n-                        timestamp_t max_timestamp = current->date;\n+\t\t\ttimestamp_t max_timestamp = current->date;\n \n-                        for (parent = current->parents; parent; parent = parent->next) {\n-                                if (parent->item->generation == GENERATION_NUMBER_INFINITY ||\n-                                    parent->item->generation == GENERATION_NUMBER_ZERO) {\n-                                        all_parents_computed = 0;\n-                                        commit_list_insert(parent->item, &list);\n-                                        break;\n-                                } else {\n+\t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n+\t\t\t\tif (parent->item->generation == GENERATION_NUMBER_INFINITY ||\n+\t\t\t\t\tparent->item->generation == GENERATION_NUMBER_ZERO) {\n+\t\t\t\t\tall_parents_computed = 0;\n+\t\t\t\t\tcommit_list_insert(parent->item, &list);\n+\t\t\t\t\tbreak;\n+\t\t\t\t} else {\n \t\t\t\t\tstruct generation pg;\n \t\t\t\t\ttimestamp_t pt;\n \t\t\t\t\tget_generation_version_from_commit(parent->item, 3, &pg);\n@@ -1001,19 +1006,75 @@ static void compute_generation_numbers_3(struct packed_commit_list *commits)\n \t\t\t\t\tif (pt > max_timestamp)\n \t\t\t\t\t\tmax_timestamp = pt + 1;\n \t\t\t\t}\n-                        }\n+\t\t\t}\n+\n+\t\t\tif (all_parents_computed) {\n+\t\t\t\tcurrent->generation = (uint32_t)(max_timestamp - current->date) + 1;\n+\t\t\t\tpop_commit(&list);\n+\n+\t\t\t\tif (current->generation > GENERATION_NUMBER_MAX)\n+\t\t\t\t\tdie(_(\"generation number gap is too high!\"));\n+\t\t\t}\n+\t\t}\n+\t}\n+}\n+\n+static void compute_generation_numbers_5(struct packed_commit_list *commits)\n+{\n+\tint i;\n+\tstruct commit_list *list = NULL;\n+\n+\tfor (i = 0; i < commits->nr; i++) {\n+\t\t/* skip already computed generation numbers */\n+\t\tif (commits->list[i]->generation != GENERATION_NUMBER_INFINITY &&\n+\t\t\tcommits->list[i]->generation != GENERATION_NUMBER_ZERO)\n+\t\t\tcontinue;\n+\n+\t\tcommit_list_insert(commits->list[i], &list);\n+\n+\t\twhile (list) {\n+\t\t\tstruct commit *current = list->item;\n+\t\t\tstruct commit_list *parent;\n+\t\t\tint all_parents_computed = 1;\n+\n+\t\t\ttimestamp_t max_timestamp = current->date;\n+\t\t\tuint32_t max_generation = 0;\n+\n+\t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n+\t\t\t\tif (parent->item->generation == GENERATION_NUMBER_INFINITY ||\n+\t\t\t\t    parent->item->generation == GENERATION_NUMBER_ZERO) {\n+\t\t\t\t\tall_parents_computed = 0;\n+\t\t\t\t\tcommit_list_insert(parent->item, &list);\n+\t\t\t\t\tbreak;\n+\n+\t\t\t\t} else {\n+\t\t\t\t\tstruct generation pg;\n+\t\t\t\t\ttimestamp_t pt;\n+\t\t\t\t\tget_generation_version_from_commit(parent->item, 5, &pg);\n+\n+\t\t\t\t\tpt = pg.value1 + pg.date;\n+\n+\t\t\t\t\tif (pt > max_timestamp)\n+\t\t\t\t\t\tmax_timestamp = pt + 1;\n+\t\t\t\t\tif (pg.value1 > max_generation)\n+\t\t\t\t\t\tmax_generation = pg.value1;\n+\t\t\t\t}\n+\t\t\t}\n \n-                        if (all_parents_computed) {\n+\t\t\tif (all_parents_computed) {\n \t\t\t\tcurrent->generation = (uint32_t)(max_timestamp - current->date) + 1;\n-                                pop_commit(&list);\n+\t\t\t\tif (current->generation < max_generation + 1)\n+\t\t\t\t\tcurrent->generation = max_generation + 1;\n+\t\t\t\tpop_commit(&list);\n \n-                                if (current->generation > GENERATION_NUMBER_MAX)\n-                                        die(_(\"generation number gap is too high!\"));\n-                        }\n-                }\n-        }\n+\t\t\t\tif (current->generation > GENERATION_NUMBER_MAX)\n+\t\t\t\t\tdie(_(\"generation number gap is too high!\"));\n+\t\t\t}\n+\t\t}\n+\t}\n }\n \n+\n static void compute_generation_numbers(struct packed_commit_list *commits,\n \t\t\t\t       int generation_version)\n {\n@@ -1038,6 +1099,9 @@ static void compute_generation_numbers(struct packed_commit_list *commits,\n \tcase 4:\n \t\t/* compute at write time */\n \t\treturn;\n+\tcase 5:\n+\t\tcompute_generation_numbers_5(commits);\n+\t\treturn;\n \t}\n }\n \n-- \n2.23.0.windows.1\n"},{"id":"382548","messageId":"8fba9eb7-934f-9b4e-f898-bab099b95ede@gmail.com","threadId":"51119","inReplyTo":"86o8ziatb2.fsf_-_@gmail.com","subject":"Re: [RFC/PATCH] commit-graph: generation v5 (backward compatible date ceiling)","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-09-18T12:26:41Z","receivedAt":"2019-09-18T12:26:45Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/18/2019 4:43 AM, Jakub Narebski wrote:\n> Derrick Stolee <stolee@gmail.com> writes:\n>> On 6/25/2019 3:51 AM, Jakub Narebski wrote:\n>>> Jakub Narebski <jnareb@gmail.com> writes:\n>>>> Derrick Stolee <stolee@gmail.com> writes:\n> [...]\n>>>> O.K., so the \"generation number v2 (legacy)\" would be incremental and\n>>>> backward-compatibile in use (though not in generation and validation).\n> [...]\n>>>> Do you have benchmark for this \"monotonically offset corrected commit\n>>>> date\" generation number in https://github.com/derrickstolee/git/commits/reach-perf\n>>>> and https://github.com/derrickstolee/gen-test ?\n>>>\n>>> I guess this will have to wait...\n>>\n>> I have not had time to revisit this topic and re-run performance\n>> numbers, sorry.\n> \n> I have created pull requests against `reach-perf` branch of\n> derrickstolee/git repository[1], and companion pull request against\n> gen-test repository[2] with proposed prototype of backward-compatible\n> corrected commit date (with monotonic offsets).\n> \n> Could you please run the tests for this generation number v5?\n\nI'll try to get to this, but it may take a few days.\n\n> I was not\n> able to do so.  It was my first time trying to compile Git on MS\n> Windows, and while there were no problems compiling `master` (well,\n> except for compilation taking a long time), I was unable to do it for\n> `reach-perf` branch because of independent of change compilation errors.\n\nI don't think I tested this on Windows. I do most of my performance tests\nin Linux, especially when presenting numbers to the mailing list. The\ngen-test repo has a bunch of shell scripts that I used for testing in\nthat environment.\n\nThanks,\n-Stolee\n"}]}