{"thread":{"id":"54484","subject":"[PATCH] bisect: loosen halfway() check for a large number of commits","startedAt":"2020-10-22T10:38:19Z","lastAt":"2020-11-12T18:23:23Z","messageCount":7,"participants":["SZEDER Gábor","Junio C Hamano","Christian Couder"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"408161","messageId":"20201022103806.26680-1-szeder.dev@gmail.com","threadId":"54484","inReplyTo":null,"subject":"[PATCH] bisect: loosen halfway() check for a large number of commits","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-10-22T10:38:06Z","receivedAt":"2020-10-22T10:38:19Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"'git bisect start ...' and subsequent 'git bisect (good|bad)' commands\ncan take quite a while when the given/remaining revision range between\ngood and bad commits is big and contains a lot of merge commits, e.g.\nin git.git:\n\n  $ git rev-list --count v1.6.0..v2.28.0\n  44284\n  $ time git bisect start v2.28.0 v1.6.0\n  Bisecting: 22141 revisions left to test after this (roughly 15 steps)\n  [e197c21807dacadc8305250baa0b9228819189d4] unable_to_lock_die(): rename function from unable_to_lock_index_die()\n\n  real    0m15.472s\n  user    0m15.220s\n  sys     0m0.255s\n\nThe majority of the runtime is spent in do_find_bisection(), where we\ntry to find a commit as close as possible to the halfway point between\nthe bad and good revisions, i.e. a commit from which the number of\nreachable commits that are in the good-bad range is half the total\nnumber of commits in that range.  So we count how many commits are\nreachable in the good-bad range for each commit in that range, which\nis quick and easy for a linear history, even over 300k commits in a\nlinear range are handled in ~0.3s on my machine.  Alas, handling merge\ncommits is non-trivial and quite expensive as the algorithm used seems\nto be quadratic, causing the long runtime shown above.\n\nInterestingly, look at what a big difference one additional commit\ncan make:\n\n  $ git rev-list --count v1.6.0^..v2.28.0\n  44285\n  $ time git bisect start v2.28.0 v1.6.0^\n  Bisecting: 22142 revisions left to test after this (roughly 15 steps)\n  [565301e41670825ceedf75220f2918ae76831240] Sync with 2.1.2\n\n  real  0m5.848s\n  user  0m5.600s\n  sys   0m0.252s\n\nThe difference is caused by one of the optimizations attempting to cut\ndown the runtime added in 1c4fea3a40 (git-rev-list --bisect:\noptimization, 2007-03-21):\n\n    Another small optimization is whenever we find a half-way commit\n    (that is, a commit that can reach exactly half of the commits),\n    we stop giving counts to remaining commits, as we will not find\n    any better commit than we just found.\n\nIn this second 'git bisect start' command we happen to find a commit\nexactly at the halfway point and can return early, but in the first\ncase there is no such commit, so we can't return early and end up\ncounting the number of reachable commits from all commits in the\ngood-bad range.\n\nHowever, when we have thousands of commits it's not all that important\nto find the _exact_ halfway point, a few commits more or less doesn't\nmake any real difference for the bisection.\n\nSo let's loosen the halfway check to consider commits within about\n0.1% of the exact halfway point as halfway as well.  This will allow\nus to return early on a bigger good-bad range, even when there is no\ncommit exactly at the halfway point, thereby reducing the runtime of\nthe first command above considerably, from ~15s to 4.901s.\nFurthermore, even if there is a commit exactly at the halfway point,\nwe might still stumble upon a commit within that 0.1% range before\nfinding the exact halfway point, allowing us to return a bit earlier,\nslightly reducing the runtime of the second command from 5.848s to\n5.058s.  Note that this change doesn't affect good-bad ranges\ncontaining ~2000 commits or less, because that 0.1% tolerance becomes\nzero due to integer arithmetic; however, if the range is that small\nthen counting the reachable commits for all commits is already fast\nenough anyway.\n\nNaturally, this will likely change which commits get picked at each\nbisection step, and, in turn, might change how many bisection steps\nare necessary to find the first bad commit.  If the number of\nnecessary bisection steps were to increase often, then this change\ncould backfire, because building and testing at each step might take\nmuch longer than the time spared.  OTOH, if the number of steps were\nto decrease, then it would be a double win.\n\nSo I ran some tests to see how often that happens: picked random good\nand bad starting revisions at least 50k commits apart and a random\nfirst bad commit in between in git.git, and used 'git bisect run git\nmerge-base --is-ancestor HEAD $first_bad_commit' to check the number\nof necessary bisection steps.  After repeating all this 1000 times\nboth with and without this patch I found that:\n\n  - 146 cases needed one more bisection step than before, 149 cases\n    needed one less step, while in the remaining 705 cases the number\n    of steps didn't change.  So the number of bisection steps does\n    indeed change in a non-negligible number of cases, but it seems\n    that the average number of steps doesn't change in the long run.\n\n  - The first 'git bisect start' command got over 3x faster in 456\n    cases, so this \"no commit at the exact halfway point\" case seems\n    to be common enough to care about.\n\n[TODO:\n  - Update comments at callsites mentioning \"exact halfway\".\n  - Rename function to approx_halfway(), perhaps?]\n---\n bisect.c | 15 +++++++++++++--\n 1 file changed, 13 insertions(+), 2 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex f5b1368128..1857ce4c75 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -105,6 +105,8 @@ static int count_interesting_parents(struct commit *commit, unsigned bisect_flag\n \n static inline int halfway(struct commit_list *p, int nr)\n {\n+\tint diff;\n+\n \t/*\n \t * Don't short-cut something we are not going to return!\n \t */\n@@ -113,13 +115,22 @@ static inline int halfway(struct commit_list *p, int nr)\n \tif (DEBUG_BISECT)\n \t\treturn 0;\n \t/*\n-\t * 2 and 3 are halfway of 5.\n+\t * For small number of commits 2 and 3 are halfway of 5, and\n \t * 3 is halfway of 6 but 2 and 4 are not.\n \t */\n-\tswitch (2 * weight(p) - nr) {\n+\tdiff = 2 * weight(p) - nr;\n+\tswitch (diff) {\n \tcase -1: case 0: case 1:\n \t\treturn 1;\n \tdefault:\n+\t\t/*\n+\t\t * For large number of commits we are not so strict, it's\n+\t\t * good enough if it's within ~0.1% of the halfway point,\n+\t\t * e.g. 5000 is exactly halfway of 10000, but we consider\n+\t\t * the values [4996, 5004] as halfway as well.\n+\t\t */\n+\t\tif (abs(diff) < nr / 1024)\n+\t\t\treturn 1;\n \t\treturn 0;\n \t}\n }\n-- \n2.29.0.470.g6462f21d4e\n\n"},{"id":"408162","messageId":"20201022104007.GE24813@szeder.dev","threadId":"54484","inReplyTo":"20201022103806.26680-1-szeder.dev@gmail.com","subject":"Re: [PATCH] bisect: loosen halfway() check for a large number of commits","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-10-22T10:40:07Z","receivedAt":"2020-10-22T10:40:12Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"This is only RFC, but forgot to mark it as such in Subject: line,\nsorry.\n\n\nOn Thu, Oct 22, 2020 at 12:38:06PM +0200, SZEDER Gábor wrote:\n> 'git bisect start ...' and subsequent 'git bisect (good|bad)' commands\n> can take quite a while when the given/remaining revision range between\n> good and bad commits is big and contains a lot of merge commits, e.g.\n> in git.git:\n> \n>   $ git rev-list --count v1.6.0..v2.28.0\n>   44284\n>   $ time git bisect start v2.28.0 v1.6.0\n>   Bisecting: 22141 revisions left to test after this (roughly 15 steps)\n>   [e197c21807dacadc8305250baa0b9228819189d4] unable_to_lock_die(): rename function from unable_to_lock_index_die()\n> \n>   real    0m15.472s\n>   user    0m15.220s\n>   sys     0m0.255s\n> \n> The majority of the runtime is spent in do_find_bisection(), where we\n> try to find a commit as close as possible to the halfway point between\n> the bad and good revisions, i.e. a commit from which the number of\n> reachable commits that are in the good-bad range is half the total\n> number of commits in that range.  So we count how many commits are\n> reachable in the good-bad range for each commit in that range, which\n> is quick and easy for a linear history, even over 300k commits in a\n> linear range are handled in ~0.3s on my machine.  Alas, handling merge\n> commits is non-trivial and quite expensive as the algorithm used seems\n> to be quadratic, causing the long runtime shown above.\n> \n> Interestingly, look at what a big difference one additional commit\n> can make:\n> \n>   $ git rev-list --count v1.6.0^..v2.28.0\n>   44285\n>   $ time git bisect start v2.28.0 v1.6.0^\n>   Bisecting: 22142 revisions left to test after this (roughly 15 steps)\n>   [565301e41670825ceedf75220f2918ae76831240] Sync with 2.1.2\n> \n>   real  0m5.848s\n>   user  0m5.600s\n>   sys   0m0.252s\n> \n> The difference is caused by one of the optimizations attempting to cut\n> down the runtime added in 1c4fea3a40 (git-rev-list --bisect:\n> optimization, 2007-03-21):\n> \n>     Another small optimization is whenever we find a half-way commit\n>     (that is, a commit that can reach exactly half of the commits),\n>     we stop giving counts to remaining commits, as we will not find\n>     any better commit than we just found.\n> \n> In this second 'git bisect start' command we happen to find a commit\n> exactly at the halfway point and can return early, but in the first\n> case there is no such commit, so we can't return early and end up\n> counting the number of reachable commits from all commits in the\n> good-bad range.\n> \n> However, when we have thousands of commits it's not all that important\n> to find the _exact_ halfway point, a few commits more or less doesn't\n> make any real difference for the bisection.\n> \n> So let's loosen the halfway check to consider commits within about\n> 0.1% of the exact halfway point as halfway as well.  This will allow\n> us to return early on a bigger good-bad range, even when there is no\n> commit exactly at the halfway point, thereby reducing the runtime of\n> the first command above considerably, from ~15s to 4.901s.\n> Furthermore, even if there is a commit exactly at the halfway point,\n> we might still stumble upon a commit within that 0.1% range before\n> finding the exact halfway point, allowing us to return a bit earlier,\n> slightly reducing the runtime of the second command from 5.848s to\n> 5.058s.  Note that this change doesn't affect good-bad ranges\n> containing ~2000 commits or less, because that 0.1% tolerance becomes\n> zero due to integer arithmetic; however, if the range is that small\n> then counting the reachable commits for all commits is already fast\n> enough anyway.\n> \n> Naturally, this will likely change which commits get picked at each\n> bisection step, and, in turn, might change how many bisection steps\n> are necessary to find the first bad commit.  If the number of\n> necessary bisection steps were to increase often, then this change\n> could backfire, because building and testing at each step might take\n> much longer than the time spared.  OTOH, if the number of steps were\n> to decrease, then it would be a double win.\n> \n> So I ran some tests to see how often that happens: picked random good\n> and bad starting revisions at least 50k commits apart and a random\n> first bad commit in between in git.git, and used 'git bisect run git\n> merge-base --is-ancestor HEAD $first_bad_commit' to check the number\n> of necessary bisection steps.  After repeating all this 1000 times\n> both with and without this patch I found that:\n> \n>   - 146 cases needed one more bisection step than before, 149 cases\n>     needed one less step, while in the remaining 705 cases the number\n>     of steps didn't change.  So the number of bisection steps does\n>     indeed change in a non-negligible number of cases, but it seems\n>     that the average number of steps doesn't change in the long run.\n> \n>   - The first 'git bisect start' command got over 3x faster in 456\n>     cases, so this \"no commit at the exact halfway point\" case seems\n>     to be common enough to care about.\n> \n> [TODO:\n>   - Update comments at callsites mentioning \"exact halfway\".\n>   - Rename function to approx_halfway(), perhaps?]\n> ---\n>  bisect.c | 15 +++++++++++++--\n>  1 file changed, 13 insertions(+), 2 deletions(-)\n> \n> diff --git a/bisect.c b/bisect.c\n> index f5b1368128..1857ce4c75 100644\n> --- a/bisect.c\n> +++ b/bisect.c\n> @@ -105,6 +105,8 @@ static int count_interesting_parents(struct commit *commit, unsigned bisect_flag\n>  \n>  static inline int halfway(struct commit_list *p, int nr)\n>  {\n> +\tint diff;\n> +\n>  \t/*\n>  \t * Don't short-cut something we are not going to return!\n>  \t */\n> @@ -113,13 +115,22 @@ static inline int halfway(struct commit_list *p, int nr)\n>  \tif (DEBUG_BISECT)\n>  \t\treturn 0;\n>  \t/*\n> -\t * 2 and 3 are halfway of 5.\n> +\t * For small number of commits 2 and 3 are halfway of 5, and\n>  \t * 3 is halfway of 6 but 2 and 4 are not.\n>  \t */\n> -\tswitch (2 * weight(p) - nr) {\n> +\tdiff = 2 * weight(p) - nr;\n> +\tswitch (diff) {\n>  \tcase -1: case 0: case 1:\n>  \t\treturn 1;\n>  \tdefault:\n> +\t\t/*\n> +\t\t * For large number of commits we are not so strict, it's\n> +\t\t * good enough if it's within ~0.1% of the halfway point,\n> +\t\t * e.g. 5000 is exactly halfway of 10000, but we consider\n> +\t\t * the values [4996, 5004] as halfway as well.\n> +\t\t */\n> +\t\tif (abs(diff) < nr / 1024)\n> +\t\t\treturn 1;\n>  \t\treturn 0;\n>  \t}\n>  }\n> -- \n> 2.29.0.470.g6462f21d4e\n> \n"},{"id":"408175","messageId":"xmqqv9f2mb61.fsf@gitster.c.googlers.com","threadId":"54484","inReplyTo":"20201022103806.26680-1-szeder.dev@gmail.com","subject":"Re: [PATCH] bisect: loosen halfway() check for a large number of commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-10-22T17:18:46Z","receivedAt":"2020-10-22T17:18:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"SZEDER Gábor <szeder.dev@gmail.com> writes:\n\n> However, when we have thousands of commits it's not all that important\n> to find the _exact_ halfway point, a few commits more or less doesn't\n> make any real difference for the bisection.\n\nCute idea.\n\n> So I ran some tests to see how often that happens: picked random good\n> and bad starting revisions at least 50k commits apart and a random\n> first bad commit in between in git.git, and used 'git bisect run git\n> merge-base --is-ancestor HEAD $first_bad_commit' to check the number\n> of necessary bisection steps.  After repeating all this 1000 times\n> both with and without this patch I found that:\n>\n>   - 146 cases needed one more bisection step than before, 149 cases\n>     needed one less step, while in the remaining 705 cases the number\n>     of steps didn't change.  So the number of bisection steps does\n>     indeed change in a non-negligible number of cases, but it seems\n>     that the average number of steps doesn't change in the long run.\n\nIt somehow is a bit surprising that there are cases that need fewer\nsteps, but I guess that is how rounding-error cuts both ways?\n\n>   - The first 'git bisect start' command got over 3x faster in 456\n>     cases, so this \"no commit at the exact halfway point\" case seems\n>     to be common enough to care about.\n\nIn any case, I like the re-realization that the counting reachable\ncommits in a mergy history is costly (see comments before the\ncount_distance() function that we already knew it from the\nbeginning, though), and the general idea of speeding up the entire\nthing by avoiding the cost we need to pay in the count_distance()\nfunction, which my earlier 1c4fea3a (git-rev-list --bisect:\noptimization, 2007-03-21) also did.\n\n    Side note.  I've been waiting for all these years to see\n    somebody new comes up and makes a fundamental change to\n    count_distance() such that it no longer is costly---alas,\n    that hasn't happened yet.\n\nMildly (only because such a bisection session over a long span is\nrarer) excited to see this RFC completed ;-)\n\n\n\n\n\n"},{"id":"408288","messageId":"CAP8UFD30NZREjE+_WHKyAhkHAi1TjHQo7iXd9xkvHj9stjT=9A@mail.gmail.com","threadId":"54484","inReplyTo":"xmqqv9f2mb61.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] bisect: loosen halfway() check for a large number of commits","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2020-10-24T07:41:27Z","receivedAt":"2020-10-24T07:41:42Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Thu, Oct 22, 2020 at 8:20 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> SZEDER Gábor <szeder.dev@gmail.com> writes:\n>\n> > However, when we have thousands of commits it's not all that important\n> > to find the _exact_ halfway point, a few commits more or less doesn't\n> > make any real difference for the bisection.\n>\n> Cute idea.\n\nI like the idea too.\n\n> > So I ran some tests to see how often that happens: picked random good\n> > and bad starting revisions at least 50k commits apart and a random\n> > first bad commit in between in git.git, and used 'git bisect run git\n> > merge-base --is-ancestor HEAD $first_bad_commit' to check the number\n> > of necessary bisection steps.  After repeating all this 1000 times\n> > both with and without this patch I found that:\n> >\n> >   - 146 cases needed one more bisection step than before, 149 cases\n> >     needed one less step, while in the remaining 705 cases the number\n> >     of steps didn't change.  So the number of bisection steps does\n> >     indeed change in a non-negligible number of cases, but it seems\n> >     that the average number of steps doesn't change in the long run.\n>\n> It somehow is a bit surprising that there are cases that need fewer\n> steps, but I guess that is how rounding-error cuts both ways?\n\nWhen there are 50k commits span between the initial good and bad, I\ndon't expect to see any statistically significant result by trying it\n1k times only. My guess is that you might start seeing something\nsignificant only when the number of tries is a multiple of the span\nbetween the initial good and bad.\n\nThere is some cost on average even if it's small (and gets smaller\nwhen the span increases) of not using the best halfway commit, so the\noverall gain depends on how long it takes (and possibly how much it\ncosts) to run the test script (or maybe to manually test).\nUnfortunately without any hint from the user or without recording how\nlong the test script lasts (which doesn't cover manual testing) we\ncannot know this cost of testing which could change a lot between use\ncases.\n\n> Mildly (only because such a bisection session over a long span is\n> rarer) excited to see this RFC completed ;-)\n\nIn projects like the Linux kernel where there are around 10k commits\nbetween 2 feature releases, such bisections over a long span might\nactually happen quite often.\n"},{"id":"408352","messageId":"20201025180136.GF24813@szeder.dev","threadId":"54484","inReplyTo":"CAP8UFD30NZREjE+_WHKyAhkHAi1TjHQo7iXd9xkvHj9stjT=9A@mail.gmail.com","subject":"Re: [PATCH] bisect: loosen halfway() check for a large number of commits","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-10-25T18:01:36Z","receivedAt":"2020-10-25T18:01:42Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Sat, Oct 24, 2020 at 09:41:27AM +0200, Christian Couder wrote:\n> On Thu, Oct 22, 2020 at 8:20 PM Junio C Hamano <gitster@pobox.com> wrote:\n> >\n> > SZEDER Gábor <szeder.dev@gmail.com> writes:\n> >\n> > > However, when we have thousands of commits it's not all that important\n> > > to find the _exact_ halfway point, a few commits more or less doesn't\n> > > make any real difference for the bisection.\n> >\n> > Cute idea.\n> \n> I like the idea too.\n> \n> > > So I ran some tests to see how often that happens: picked random good\n> > > and bad starting revisions at least 50k commits apart and a random\n> > > first bad commit in between in git.git, and used 'git bisect run git\n> > > merge-base --is-ancestor HEAD $first_bad_commit' to check the number\n> > > of necessary bisection steps.  After repeating all this 1000 times\n> > > both with and without this patch I found that:\n> > >\n> > >   - 146 cases needed one more bisection step than before, 149 cases\n> > >     needed one less step, while in the remaining 705 cases the number\n> > >     of steps didn't change.  So the number of bisection steps does\n> > >     indeed change in a non-negligible number of cases, but it seems\n> > >     that the average number of steps doesn't change in the long run.\n> >\n> > It somehow is a bit surprising that there are cases that need fewer\n> > steps, but I guess that is how rounding-error cuts both ways?\n> \n> When there are 50k commits span between the initial good and bad, I\n> don't expect to see any statistically significant result by trying it\n> 1k times only. My guess is that you might start seeing something\n> significant only when the number of tries is a multiple of the span\n> between the initial good and bad.\n\nWell, perhaps...  but statistically relevant or not, running those\n1000 tests I reported about took over 6.5 hours, so that's all you'll\nget from me :)\n\nBtw, just for curiosity, running just _one_ similar test in linux.git\nwith the good-bad range containing ~830k commits took ~65 minutes, and\nthe runtime of 'git bisect start' went from ~38mins to ~12.\n\n"},{"id":"409768","messageId":"20201112161938.20494-1-szeder.dev@gmail.com","threadId":"54484","inReplyTo":"20201022103806.26680-1-szeder.dev@gmail.com","subject":"[PATCH v2] bisect: loosen halfway() check for a large number of commits","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-11-12T16:19:38Z","receivedAt":"2020-11-12T16:19:59Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"'git bisect start ...' and subsequent 'git bisect (good|bad)' commands\ncan take quite a while when the given/remaining revision range between\ngood and bad commits is big and contains a lot of merge commits, e.g.\nin git.git:\n\n  $ git rev-list --count v1.6.0..v2.28.0\n  44284\n  $ time git bisect start v2.28.0 v1.6.0\n  Bisecting: 22141 revisions left to test after this (roughly 15 steps)\n  [e197c21807dacadc8305250baa0b9228819189d4] unable_to_lock_die(): rename function from unable_to_lock_index_die()\n\n  real    0m15.472s\n  user    0m15.220s\n  sys     0m0.255s\n\nThe majority of the runtime is spent in do_find_bisection(), where we\ntry to find a commit as close as possible to the halfway point between\nthe bad and good revisions, i.e. a commit from which the number of\nreachable commits that are in the good-bad range is half the total\nnumber of commits in that range.  So we count how many commits are\nreachable in the good-bad range for each commit in that range, which\nis quick and easy for a linear history, even over 300k commits in a\nlinear range are handled in ~0.3s on my machine.  Alas, handling merge\ncommits is non-trivial and quite expensive as the algorithm used seems\nto be quadratic, causing the long runtime shown above.\n\nInterestingly, look at what a big difference one additional commit\ncan make:\n\n  $ git rev-list --count v1.6.0^..v2.28.0\n  44285\n  $ time git bisect start v2.28.0 v1.6.0^\n  Bisecting: 22142 revisions left to test after this (roughly 15 steps)\n  [565301e41670825ceedf75220f2918ae76831240] Sync with 2.1.2\n\n  real  0m5.848s\n  user  0m5.600s\n  sys   0m0.252s\n\nThe difference is caused by one of the optimizations attempting to cut\ndown the runtime added in 1c4fea3a40 (git-rev-list --bisect:\noptimization, 2007-03-21):\n\n    Another small optimization is whenever we find a half-way commit\n    (that is, a commit that can reach exactly half of the commits),\n    we stop giving counts to remaining commits, as we will not find\n    any better commit than we just found.\n\nIn this second 'git bisect start' command we happen to find a commit\nexactly at the halfway point and can return early, but in the first\ncase there is no such commit, so we can't return early and end up\ncounting the number of reachable commits from all commits in the\ngood-bad range.\n\nHowever, when we have thousands of commits it's not all that important\nto find the _exact_ halfway point, a few commits more or less doesn't\nmake any real difference for the bisection.\n\nSo let's loosen the check in the halfway() helper to consider commits\nwithin about 0.1% of the exact halfway point as halfway as well, and\nrename the function to approx_halfway() accordingly.  This will allow\nus to return early on a bigger good-bad range, even when there is no\ncommit exactly at the halfway point, thereby reducing the runtime of\nthe first command above considerably, from ~15s to 4.901s.\nFurthermore, even if there is a commit exactly at the halfway point,\nwe might still stumble upon a commit within that 0.1% range before\nfinding the exact halfway point, allowing us to return a bit earlier,\nslightly reducing the runtime of the second command from 5.848s to\n5.058s.  Note that this change doesn't affect good-bad ranges\ncontaining ~2000 commits or less, because that 0.1% tolerance becomes\nzero due to integer arithmetic; however, if the range is that small\nthen counting the reachable commits for all commits is already fast\nenough anyway.\n\nNaturally, this will likely change which commits get picked at each\nbisection step, and, in turn, might change how many bisection steps\nare necessary to find the first bad commit.  If the number of\nnecessary bisection steps were to increase often, then this change\ncould backfire, because building and testing at each step might take\nmuch longer than the time spared.  OTOH, if the number of steps were\nto decrease, then it would be a double win.\n\nSo I ran some tests to see how often that happens: picked random good\nand bad starting revisions at least 50k commits apart and a random\nfirst bad commit in between in git.git, and used 'git bisect run git\nmerge-base --is-ancestor HEAD $first_bad_commit' to check the number\nof necessary bisection steps.  After repeating all this 1000 times\nboth with and without this patch I found that:\n\n  - 146 cases needed one more bisection step than before, 149 cases\n    needed one less step, while in the remaining 705 cases the number\n    of steps didn't change.  So the number of bisection steps does\n    indeed change in a non-negligible number of cases, but it seems\n    that the average number of steps doesn't change in the long run.\n\n  - The first 'git bisect start' command got over 3x faster in 456\n    cases, so this \"no commit at the exact halfway point\" case seems\n    to be common enough to care about.\n\nSigned-off-by: SZEDER Gábor <szeder.dev@gmail.com>\n---\nRange-diff:\n1:  79ae48469f ! 1:  1a2f5135de bisect: loosen halfway() check for a large number of commits\n    @@ Commit message\n         to find the _exact_ halfway point, a few commits more or less doesn't\n         make any real difference for the bisection.\n     \n    -    So let's loosen the halfway check to consider commits within about\n    -    0.1% of the exact halfway point as halfway as well.  This will allow\n    +    So let's loosen the check in the halfway() helper to consider commits\n    +    within about 0.1% of the exact halfway point as halfway as well, and\n    +    rename the function to approx_halfway() accordingly.  This will allow\n         us to return early on a bigger good-bad range, even when there is no\n         commit exactly at the halfway point, thereby reducing the runtime of\n         the first command above considerably, from ~15s to 4.901s.\n    @@ Commit message\n             cases, so this \"no commit at the exact halfway point\" case seems\n             to be common enough to care about.\n     \n    -    [TODO:\n    -      - Update comments at callsites mentioning \"exact halfway\".\n    -      - Rename function to approx_halfway(), perhaps?]\n    +    Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>\n     \n      ## bisect.c ##\n     @@ bisect.c: static int count_interesting_parents(struct commit *commit, unsigned bisect_flag\n    + \treturn count;\n    + }\n      \n    - static inline int halfway(struct commit_list *p, int nr)\n    +-static inline int halfway(struct commit_list *p, int nr)\n    ++static inline int approx_halfway(struct commit_list *p, int nr)\n      {\n     +\tint diff;\n     +\n    @@ bisect.c: static inline int halfway(struct commit_list *p, int nr)\n      \t\treturn 0;\n      \t}\n      }\n    +@@ bisect.c: static struct commit_list *do_find_bisection(struct commit_list *list,\n    + \t\tweight_set(p, count_distance(p));\n    + \t\tclear_distance(list);\n    + \n    +-\t\t/* Does it happen to be at exactly half-way? */\n    +-\t\tif (!(bisect_flags & FIND_BISECTION_ALL) && halfway(p, nr))\n    ++\t\t/* Does it happen to be at half-way? */\n    ++\t\tif (!(bisect_flags & FIND_BISECTION_ALL) &&\n    ++\t\t      approx_halfway(p, nr))\n    + \t\t\treturn p;\n    + \t\tcounted++;\n    + \t}\n    +@@ bisect.c: static struct commit_list *do_find_bisection(struct commit_list *list,\n    + \t\t\telse\n    + \t\t\t\tweight_set(p, weight(q));\n    + \n    +-\t\t\t/* Does it happen to be at exactly half-way? */\n    +-\t\t\tif (!(bisect_flags & FIND_BISECTION_ALL) && halfway(p, nr))\n    ++\t\t\t/* Does it happen to be at half-way? */\n    ++\t\t\tif (!(bisect_flags & FIND_BISECTION_ALL) &&\n    ++\t\t\t      approx_halfway(p, nr))\n    + \t\t\t\treturn p;\n    + \t\t}\n    + \t}\n\n bisect.c | 27 ++++++++++++++++++++-------\n 1 file changed, 20 insertions(+), 7 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex f5b1368128..bedce28cb6 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -103,8 +103,10 @@ static int count_interesting_parents(struct commit *commit, unsigned bisect_flag\n \treturn count;\n }\n \n-static inline int halfway(struct commit_list *p, int nr)\n+static inline int approx_halfway(struct commit_list *p, int nr)\n {\n+\tint diff;\n+\n \t/*\n \t * Don't short-cut something we are not going to return!\n \t */\n@@ -113,13 +115,22 @@ static inline int halfway(struct commit_list *p, int nr)\n \tif (DEBUG_BISECT)\n \t\treturn 0;\n \t/*\n-\t * 2 and 3 are halfway of 5.\n+\t * For small number of commits 2 and 3 are halfway of 5, and\n \t * 3 is halfway of 6 but 2 and 4 are not.\n \t */\n-\tswitch (2 * weight(p) - nr) {\n+\tdiff = 2 * weight(p) - nr;\n+\tswitch (diff) {\n \tcase -1: case 0: case 1:\n \t\treturn 1;\n \tdefault:\n+\t\t/*\n+\t\t * For large number of commits we are not so strict, it's\n+\t\t * good enough if it's within ~0.1% of the halfway point,\n+\t\t * e.g. 5000 is exactly halfway of 10000, but we consider\n+\t\t * the values [4996, 5004] as halfway as well.\n+\t\t */\n+\t\tif (abs(diff) < nr / 1024)\n+\t\t\treturn 1;\n \t\treturn 0;\n \t}\n }\n@@ -321,8 +332,9 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tweight_set(p, count_distance(p));\n \t\tclear_distance(list);\n \n-\t\t/* Does it happen to be at exactly half-way? */\n-\t\tif (!(bisect_flags & FIND_BISECTION_ALL) && halfway(p, nr))\n+\t\t/* Does it happen to be at half-way? */\n+\t\tif (!(bisect_flags & FIND_BISECTION_ALL) &&\n+\t\t      approx_halfway(p, nr))\n \t\t\treturn p;\n \t\tcounted++;\n \t}\n@@ -362,8 +374,9 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\telse\n \t\t\t\tweight_set(p, weight(q));\n \n-\t\t\t/* Does it happen to be at exactly half-way? */\n-\t\t\tif (!(bisect_flags & FIND_BISECTION_ALL) && halfway(p, nr))\n+\t\t\t/* Does it happen to be at half-way? */\n+\t\t\tif (!(bisect_flags & FIND_BISECTION_ALL) &&\n+\t\t\t      approx_halfway(p, nr))\n \t\t\t\treturn p;\n \t\t}\n \t}\n-- \n2.29.2.588.gcd0acd9177\n\n"},{"id":"409780","messageId":"xmqqft5ejuy6.fsf@gitster.c.googlers.com","threadId":"54484","inReplyTo":"20201112161938.20494-1-szeder.dev@gmail.com","subject":"Re: [PATCH v2] bisect: loosen halfway() check for a large number of commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-11-12T18:23:13Z","receivedAt":"2020-11-12T18:23:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"SZEDER Gábor <szeder.dev@gmail.com> writes:\n\n> So let's loosen the check in the halfway() helper to consider commits\n> within about 0.1% of the exact halfway point as halfway as well, and\n> rename the function to approx_halfway() accordingly.  This will allow\n> us to return early on a bigger good-bad range, even when there is no\n> commit exactly at the halfway point, thereby reducing the runtime of\n> the first command above considerably, from ~15s to 4.901s.\n\nThe optimization presented with this change would probably offer\nmore merge commits to be tested than a single-parent commit than the\noriginal algorithm, simply because merges are inspected first before\nsingle-parent commits so have better chance to be picked as \"good\nenough\" among commits with similar goodness.\n\n  Side note: This is merely an observation---I do not know if it is\n  a good thing, a bad thing, or a neutral thing, but it would likely\n  affect the end-user experience.\n\nThe optimization presented here gives probably more than enough\nimprovement, but it just occured to me when writing the entry to\nexplain the topic in the What's cooking report:\n\n     \"git bisect start/next\" in a large span of history spends a lot of\n     time trying to come up with exactly the half-way point; this can be\n     optimized by stopping when we see a commit that is close enough to\n     the half-way point.\n\nThe realization is that the optimization naturally will be affected\nby the order the commits are visited.  If a commit that is close\nenough to the half-way point happens to be visited earlier, it would\nhelp terminate our search early.  And do_find_bisection() search\ncounts all merge commits before any commit on the linear ancestry\nchain can be counted to optimize counting of commits on the linear\nancestry chain, which are expected to exist more than merge commits.\n\nBy sorting the \"list\" to somehow encourage commits near the half-way\nappear early on it, we may raise the likelyhood that we'd find\ngood-enough commit early and terminate, no?  Perhaps sort by the\n(absolute) distance between the committer timestamp of individual\ncommit and its median value, or something?\n\nThanks.\n"}]}