{"thread":{"id":"62981","subject":"first bisection step takes quite a while","startedAt":"2025-02-20T14:36:01Z","lastAt":"2025-02-24T17:27:29Z","messageCount":12,"participants":["Uwe Kleine-König","D. Ben Knoble","Junio C Hamano","Christian Couder"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"512770","messageId":"arrp2ye3kid76pwghguu5z4jkpv7xsskzdsjunbfkgmwejgby5@qh4phxwzenyp","threadId":"62981","inReplyTo":null,"subject":"first bisection step takes quite a while","fromName":"Uwe Kleine-König","fromEmail":"u.kleine-koenig@baylibre.com","sentAt":"2025-02-20T14:35:56Z","receivedAt":"2025-02-20T14:36:01Z","isPatch":false,"sender":{"key":"u.kleine-koenig@baylibre.com","avatar":null},"body":"Hello,\n\ntoday I did a bisection in the kernel repository:\n\n\tlinux$ git version\n\tgit version 2.47.1\n\n\tlinux$ time git bisect start 09fbf3d502050282bf47ab3babe1d4ed54dd1fd8 96d8eab5d0a1a9741a4cae1b3c125d75d1aabedf\n\tBisecting: 572238 revisions left to test after this (roughly 19 steps)\n\t[eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging\n\n\treal\t18m41.374s\n\tuser\t27m18.306s\n\tsys\t1m0.565s\n\nI was surprised that it took that long to find and checkout the first\nrevision to check. (That is on a 4 x Intel(R) Core(TM) i5-6440HQ CPU @\n2.60GHz, 16 GiB RAM with a Samsung SSD. On a different machine (56 x\nIntel(R) Xeon(R) CPU E5-2660 v4 @ 2.00GHz, 256 GiB RAM and (I think a\nspinning hard disk)) it took nearly an hour.\n\nI think this isn't my first bisection over that many commits, but I\ncannot remember that the first step ever took so long.\n\nIs my expectation (and maybe memory) wrong, or is this a regression?\n\nBest regards\nUwe\n"},{"id":"512780","messageId":"CALnO6CACJTKasKT9rX9w4_r9q0DPOPZhGnHt8f65oo6Q=8NxEg@mail.gmail.com","threadId":"62981","inReplyTo":"arrp2ye3kid76pwghguu5z4jkpv7xsskzdsjunbfkgmwejgby5@qh4phxwzenyp","subject":"Re: first bisection step takes quite a while","fromName":"D. Ben Knoble","fromEmail":"ben.knoble@gmail.com","sentAt":"2025-02-20T18:44:47Z","receivedAt":"2025-02-20T18:44:59Z","isPatch":false,"sender":{"key":"ben.knoble@gmail.com","avatar":"https://avatars.githubusercontent.com/u/22802209?v=4"},"body":"On Thu, Feb 20, 2025 at 9:38 AM Uwe Kleine-König\n<u.kleine-koenig@baylibre.com> wrote:\n>\n> Hello,\n>\n> today I did a bisection in the kernel repository:\n>\n>         linux$ git version\n>         git version 2.47.1\n>\n>         linux$ time git bisect start 09fbf3d502050282bf47ab3babe1d4ed54dd1fd8 96d8eab5d0a1a9741a4cae1b3c125d75d1aabedf\n>         Bisecting: 572238 revisions left to test after this (roughly 19 steps)\n>         [eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging\n>\n>         real    18m41.374s\n>         user    27m18.306s\n>         sys     1m0.565s\n>\n> I was surprised that it took that long to find and checkout the first\n> revision to check. (That is on a 4 x Intel(R) Core(TM) i5-6440HQ CPU @\n> 2.60GHz, 16 GiB RAM with a Samsung SSD. On a different machine (56 x\n> Intel(R) Xeon(R) CPU E5-2660 v4 @ 2.00GHz, 256 GiB RAM and (I think a\n> spinning hard disk)) it took nearly an hour.\n\nRelated thread:\nhttps://lore.kernel.org/git/19461b87a5c.5a2ea74016716.8214238482389812984@zohomail.com/\n\n\n\n-- \nD. Ben Knoble\n"},{"id":"512783","messageId":"xmqqikp4ctoh.fsf@gitster.g","threadId":"62981","inReplyTo":"CALnO6CACJTKasKT9rX9w4_r9q0DPOPZhGnHt8f65oo6Q=8NxEg@mail.gmail.com","subject":"Re: first bisection step takes quite a while","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-20T19:17:18Z","receivedAt":"2025-02-20T19:17:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"D. Ben Knoble\" <ben.knoble@gmail.com> writes:\n\n> On Thu, Feb 20, 2025 at 9:38 AM Uwe Kleine-König\n> <u.kleine-koenig@baylibre.com> wrote:\n>>\n>> Hello,\n>>\n>> today I did a bisection in the kernel repository:\n>>\n>>         linux$ git version\n>>         git version 2.47.1\n>>\n>>         linux$ time git bisect start 09fbf3d502050282bf47ab3babe1d4ed54dd1fd8 96d8eab5d0a1a9741a4cae1b3c125d75d1aabedf\n>>         Bisecting: 572238 revisions left to test after this (roughly 19 steps)\n>>         [eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging\n>>\n>>         real    18m41.374s\n>>         user    27m18.306s\n>>         sys     1m0.565s\n>>\n>> I was surprised that it took that long to find and checkout the first\n>> revision to check. (That is on a 4 x Intel(R) Core(TM) i5-6440HQ CPU @\n>> 2.60GHz, 16 GiB RAM with a Samsung SSD. On a different machine (56 x\n>> Intel(R) Xeon(R) CPU E5-2660 v4 @ 2.00GHz, 256 GiB RAM and (I think a\n>> spinning hard disk)) it took nearly an hour.\n>\n> Related thread:\n> https://lore.kernel.org/git/19461b87a5c.5a2ea74016716.8214238482389812984@zohomail.com/\n\nIndeed.  I haven't had a chance to dig any deeper in the area of the\ncode since that discussion, but the ideas raised in the messages\nnear the tail end of the thread may be worth exploring.\n\nTHanks for the link.\n"},{"id":"512787","messageId":"xmqqa5agcbx6.fsf@gitster.g","threadId":"62981","inReplyTo":"xmqqikp4ctoh.fsf@gitster.g","subject":"Re: first bisection step takes quite a while","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-21T01:40:53Z","receivedAt":"2025-02-21T01:40:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> \"D. Ben Knoble\" <ben.knoble@gmail.com> writes:\n>\n>> On Thu, Feb 20, 2025 at 9:38 AM Uwe Kleine-König\n>> <u.kleine-koenig@baylibre.com> wrote:\n>>>\n>>> Hello,\n>>>\n>>> today I did a bisection in the kernel repository:\n>>>\n>>>         linux$ git version\n>>>         git version 2.47.1\n>>>\n>>>         linux$ time git bisect start 09fbf3d502050282bf47ab3babe1d4ed54dd1fd8 96d8eab5d0a1a9741a4cae1b3c125d75d1aabedf\n>>>         Bisecting: 572238 revisions left to test after this (roughly 19 steps)\n>>>         [eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging\n>>>\n>>>         real    18m41.374s\n>>>         user    27m18.306s\n>>>         sys     1m0.565s\n>>>\n>>> I was surprised that it took that long to find and checkout the first\n>>> revision to check. (That is on a 4 x Intel(R) Core(TM) i5-6440HQ CPU @\n>>> 2.60GHz, 16 GiB RAM with a Samsung SSD. On a different machine (56 x\n>>> Intel(R) Xeon(R) CPU E5-2660 v4 @ 2.00GHz, 256 GiB RAM and (I think a\n>>> spinning hard disk)) it took nearly an hour.\n>>\n>> Related thread:\n>> https://lore.kernel.org/git/19461b87a5c.5a2ea74016716.8214238482389812984@zohomail.com/\n>\n> Indeed.  I haven't had a chance to dig any deeper in the area of the\n> code since that discussion, but the ideas raised in the messages\n> near the tail end of the thread may be worth exploring.\n>\n> THanks for the link.\n\nSo, here is something that _could_ be the beginning of a patch, but\njust to illustrate what I tried.\n\n * In do_find_bisection(), we try each commit on the incoming commit\n   list (which is sorted the way rev-list emits, probably reversed)\n   and count how many commits in the set each merge commit can reach\n   (which is called \"weight\") in the \"honest and stupid\" way.  I try\n   to collect these merges in a linear array, and try from the\n   middle to older and newer.  As the loop to compute weight for\n   merges have an early-exit clause that says \"oh, this is good\n   enough\", this may improve our odds to find a good enough merge\n   early.\n\n * The \"this is good enough\" logic currently allows us to be within\n   0.1% of the real halfway point.  Until the candidate set becomes\n   small enough, we could loosen the criteria to allow larger, say\n   3%, slack.  This code is written but not enabled (with \"0 &&\").\n\n * After computing the weight for a merge in \"honest and stupid\"\n   way, we know what other commits in the set it can reach.  If the\n   weight we computed is way smaller than the half the number of\n   commits in the set, that means these commits we can reach from\n   the merge we are looking at would score even lower.  We could\n   mark them as not-viable before clearing the list to check next\n   merge with \"honest and stupid\" way.  Again, this code is written\n   but not enabled.\n\nSo, in short, I have three ideas, and with the first one (that\nis the most straightforward and least error prone) alone, it seems\nthat we gain significant speedup.\n\nThe current code took ~20 minutes for me and its result is\n\n$ git bisect start --no-checkout 09fbf3d5020 96d8eab5d0a1\nBisecting: 581164 revisions left to test after this (roughly 19 steps)\n[2c71ab4bb465c79a4687cc2fd5012e470aebdb1f] Merge branch 'for-upstre...\n\nThere are 1144459 commits in the range, and the point chosen by\nbisection can reach 563294 of them.  563294*2 == 1126588, so we are\n1144459 - 1126588 = 17871 commits away from the theoretical halfway.\n\nWith the \"let's try from the midway merges\" approach without\nchanging anything else, I get a different commit (because the\noriginal algorithm is taking \"good enough\" early exit), and it took\nabout 30 seconds.\n\n$ git bisect start --no-checkout 09fbf3d5020 96d8eab5d0a1\nBisecting: 572238 revisions left to test after this (roughly 19 steps)\n[eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-...\n\nThe size of the original range is the same, of course, 1144459\ncommits, and the point chosen by bisection reaches 572220 of them.\nSince 572220*2 = 1144440, we are 1144459 - 1144440 = 19 commits from\nthe theoretical halfway.\n\nMy current thinking is that the heuristics #1 (which is enabled in\nmy experiment and in the following patch) is good enough, #2\n(loosening the \"good enough\" threshold) is probably not very\neffective, and #3 (discard ones that are closer to the good end than\na merge that is known to be not viable) might be interesting to\npursue further but probably tricky to get right.\n\nComments?\n\n\n bisect.c | 89 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------\n 1 file changed, 81 insertions(+), 8 deletions(-)\n\ndiff --git c/bisect.c w/bisect.c\nindex 7a3c77c6d8..eae8e97958 100644\n--- c/bisect.c\n+++ w/bisect.c\n@@ -23,6 +23,7 @@\n #include \"object-store-ll.h\"\n #include \"path.h\"\n #include \"dir.h\"\n+#include \"trace2.h\"\n \n static struct oid_array good_revs;\n static struct oid_array skipped_revs;\n@@ -132,8 +133,10 @@ static inline int approx_halfway(struct commit_list *p, int nr)\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 * While we have really large number of commits, we'll\n+\t\t * loosen our target to hit within 3% of the harfway.\n \t\t */\n-\t\tif (abs(diff) < nr / 1024)\n+\t\tif ((0 && 10000 < nr && abs(diff) < nr / 64) || abs(diff) < nr / 1024)\n \t\t\treturn 1;\n \t\treturn 0;\n \t}\n@@ -282,11 +285,15 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t\t\t     int nr, int *weights,\n \t\t\t\t\t     unsigned bisect_flags)\n {\n-\tint n, counted;\n+\tint n, counted, num_merges;\n \tstruct commit_list *p;\n+\tstruct commit_list **merge; /* ugh */\n \n+\tnum_merges = 0;\n \tcounted = 0;\n+\tnum_merges = 0;\n \n+\ttrace2_region_enter(\"bisect\", \"do_find_bisection_0\", the_repository);\n \tfor (n = 0, p = list; p; p = p->next) {\n \t\tstruct commit *commit = p->item;\n \t\tunsigned commit_flags = commit->object.flags;\n@@ -309,16 +316,30 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\tweight_set(p, -1);\n \t\t\tbreak;\n \t\tdefault:\n+\t\t\tnum_merges++;\n \t\t\tweight_set(p, -2);\n \t\t\tbreak;\n \t\t}\n \t}\n+\ttrace2_region_leave(\"bisect\", \"do_find_bisection_0\", the_repository);\n \n \tshow_list(\"bisection 2 initialize\", counted, nr, list);\n \n+\t/*\n+\t * Collect merges into an array.\n+\t */\n+\tCALLOC_ARRAY(merge, num_merges);\n+\tfor (n = 0, p = list; p; p = p->next) {\n+\t\tif (weight(p) != -2)\n+\t\t\tcontinue;\n+\t\tmerge[n++] = p;\n+\t}\n+\tif (num_merges != n)\n+\t\tBUG(\"Whoa!\");\n+\n \t/*\n \t * If you have only one parent in the resulting set\n-\t * then you can reach one commit more than that parent\n+\t * then you can reach one commit more than your parent\n \t * can reach.  So we do not have to run the expensive\n \t * count_distance() for single strand of pearls.\n \t *\n@@ -330,25 +351,73 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t * So we will first count distance of merges the usual\n \t * way, and then fill the blanks using cheaper algorithm.\n \t */\n-\tfor (p = list; p; p = p->next) {\n-\t\tif (p->item->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n+\ttrace2_region_enter(\"bisect\", \"do_find_bisection_1\", the_repository);\n+\n+\t/*\n+\t * Use the element of a list from its midpoint.\n+\t * (num_merges == 1) mid = 0; ix = 0\n+\t * (num_merges == 2) mid = 0; ix = 0, 1\n+\t * (num_merges == 3) mid = 1; ix = 1, 2, 0\n+\t * (num_merges == 4) mid = 1; ix = 1, 2, 0, 3\n+\t * (num_merges == 5) mid = 2; ix = 2, 3, 1, 4, 0\n+\t * (num_merges == 6) mid = 2; ix = 2, 3, 1, 4, 0, 5\n+\t */\n+\tfor (n = 0; n < num_merges; n++) {\n+\t\tstruct commit_list *p;\n+\t\tint ix = (num_merges - 1) / 2;\n+\n+\t\tif (n % 2)\n+\t\t\tix += (n + 1) / 2;\n+\t\telse\n+\t\t\tix -= n / 2;\n+\n+\t\tp = merge[ix];\n \t\tif (weight(p) != -2)\n \t\t\tcontinue;\n \t\tif (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)\n \t\t\tBUG(\"shouldn't be calling count-distance in fp mode\");\n \t\tweight_set(p, count_distance(p));\n+\n+#if 0\n+\t\t/* \n+\t\t * If the current merge can reach way fewer than half\n+\t\t * the commits in the graph, any of its ancestors can\n+\t\t * reach even fewer commits, which means they will not\n+\t\t * make better half-way candidate than this one.\n+\t\t *\n+\t\t * Just as a slack, let's cut at 3/8 not exactly 1/2.\n+\t\t */\n+\t\tif (weight(p) * 8 < nr * 3) {\n+\t\t\tfor (struct commit_list *q = list; q; q = q->next) {\n+\t\t\t\tif (q->item->object.flags & UNINTERESTING)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tif (!(q->item->object.flags & COUNTED))\n+\t\t\t\t\tcontinue;\n+\t\t\t\tif (weight(q) != -2)\n+\t\t\t\t\tcontinue;\n+\t\t\t\t/* mark it as not a viable candidate */\n+\t\t\t\tweight_set(q, 1);\n+\t\t\t}\n+\t\t}\n+#endif\n \t\tclear_distance(list);\n \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    approx_halfway(p, nr)) {\n+\t\t\ttrace2_data_string(\"bisect\", the_repository, \"early-exit\", \"do_find_bisection_1\");\n+\t\t\ttrace2_region_leave(\"bisect\", \"do_find_bisection_1\", the_repository);\n+\t\t\tfree(merge);\n \t\t\treturn p;\n+\t\t}\n \t\tcounted++;\n \t}\n+\ttrace2_region_leave(\"bisect\", \"do_find_bisection_1\", the_repository);\n+\tfree(merge);\n \n \tshow_list(\"bisection 2 count_distance\", counted, nr, list);\n \n+\ttrace2_region_enter(\"bisect\", \"do_find_bisection_2\", the_repository);\n \twhile (counted < nr) {\n \t\tfor (p = list; p; p = p->next) {\n \t\t\tstruct commit_list *q;\n@@ -384,10 +453,14 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \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    approx_halfway(p, nr)) {\n+\t\t\ttrace2_data_string(\"bisect\", the_repository, \"early-exit\", \"do_find_bisection_2\");\n+\t\t\t\ttrace2_region_leave(\"bisect\", \"do_find_bisection_2\", the_repository);\n \t\t\t\treturn p;\n+\t\t\t}\n \t\t}\n \t}\n+\ttrace2_region_leave(\"bisect\", \"do_find_bisection_2\", the_repository);\n \n \tshow_list(\"bisection 2 counted all\", counted, nr, list);\n \n"},{"id":"512814","messageId":"CAP8UFD3XVgJCc2Qa3wWZA54fg38jcpyiDtQOPNc8UQT9uL3vWg@mail.gmail.com","threadId":"62981","inReplyTo":"xmqqa5agcbx6.fsf@gitster.g","subject":"Re: first bisection step takes quite a while","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2025-02-21T09:15:09Z","receivedAt":"2025-02-21T09:15:24Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Fri, Feb 21, 2025 at 2:41 AM Junio C Hamano <gitster@pobox.com> wrote:\n\n> So, here is something that _could_ be the beginning of a patch, but\n> just to illustrate what I tried.\n>\n>  * In do_find_bisection(), we try each commit on the incoming commit\n>    list (which is sorted the way rev-list emits, probably reversed)\n>    and count how many commits in the set each merge commit can reach\n>    (which is called \"weight\") in the \"honest and stupid\" way.  I try\n>    to collect these merges in a linear array, and try from the\n>    middle to older and newer.  As the loop to compute weight for\n>    merges have an early-exit clause that says \"oh, this is good\n>    enough\", this may improve our odds to find a good enough merge\n>    early.\n\nYeah, it seems to me that in practice this is a bit like bisecting on\nthe first parents first. It would be nice if we had added an option to\nbisect on the first parents first, so that we could compare your\nimprovement and that option.\n\n>  * The \"this is good enough\" logic currently allows us to be within\n>    0.1% of the real halfway point.  Until the candidate set becomes\n>    small enough, we could loosen the criteria to allow larger, say\n>    3%, slack.  This code is written but not enabled (with \"0 &&\").\n\nIf we want to do this, I think we could loosen the criteria even if\nthe candidate set is small. Weights are integers so when the number of\ncandidates is around 33 or less, a 3% criteria will mean an exact\nmatch. Then the last 5 steps or so (as 2^5 = 32) would still be\nperformed in the same way (with an exact match).\n\n>  * After computing the weight for a merge in \"honest and stupid\"\n>    way, we know what other commits in the set it can reach.  If the\n>    weight we computed is way smaller than the half the number of\n>    commits in the set, that means these commits we can reach from\n>    the merge we are looking at would score even lower.  We could\n>    mark them as not-viable before clearing the list to check next\n>    merge with \"honest and stupid\" way.  Again, this code is written\n>    but not enabled.\n>\n> So, in short, I have three ideas, and with the first one (that\n> is the most straightforward and least error prone) alone, it seems\n> that we gain significant speedup.\n>\n> The current code took ~20 minutes for me and its result is\n>\n> $ git bisect start --no-checkout 09fbf3d5020 96d8eab5d0a1\n> Bisecting: 581164 revisions left to test after this (roughly 19 steps)\n> [2c71ab4bb465c79a4687cc2fd5012e470aebdb1f] Merge branch 'for-upstre...\n>\n> There are 1144459 commits in the range, and the point chosen by\n> bisection can reach 563294 of them.  563294*2 == 1126588, so we are\n> 1144459 - 1126588 = 17871 commits away from the theoretical halfway.\n>\n> With the \"let's try from the midway merges\" approach without\n> changing anything else, I get a different commit (because the\n> original algorithm is taking \"good enough\" early exit), and it took\n> about 30 seconds.\n>\n> $ git bisect start --no-checkout 09fbf3d5020 96d8eab5d0a1\n> Bisecting: 572238 revisions left to test after this (roughly 19 steps)\n> [eafdca4d7010a0e019aaaace3dd71b432a69b54c] Merge tag 'staging-4.18-...\n>\n> The size of the original range is the same, of course, 1144459\n> commits, and the point chosen by bisection reaches 572220 of them.\n> Since 572220*2 = 1144440, we are 1144459 - 1144440 = 19 commits from\n> the theoretical halfway.\n>\n> My current thinking is that the heuristics #1 (which is enabled in\n> my experiment and in the following patch) is good enough, #2\n> (loosening the \"good enough\" threshold) is probably not very\n> effective, and #3 (discard ones that are closer to the good end than\n> a merge that is known to be not viable) might be interesting to\n> pursue further but probably tricky to get right.\n\nI agree that #1 is probably good enough.\n\nAbout #2, I think it could be worth implementing as an option if it is\neffective in some cases, but the criteria should be loosened even if\nthe candidate set is small. The amount of code to implement it is very\nsmall and it's possible that, for some users, having to sometimes\nperform one more step of testing is not a big deal, compared to\nbisecting speed.\n\nAbout #3, I think that implementing an option to bisect on the first\nparents first is likely more useful than implementing it.\n\nThanks.\n"},{"id":"512815","messageId":"4hx5uvjy7mzntb5zp6o4dg3ut44i46bthyfuera3lnbpbcvrey@kbo3ejype7ae","threadId":"62981","inReplyTo":"xmqqa5agcbx6.fsf@gitster.g","subject":"Re: first bisection step takes quite a while","fromName":"Uwe Kleine-König","fromEmail":"u.kleine-koenig@baylibre.com","sentAt":"2025-02-21T09:28:24Z","receivedAt":"2025-02-21T09:28:27Z","isPatch":false,"sender":{"key":"u.kleine-koenig@baylibre.com","avatar":null},"body":"Hello Junio,\n\nOn Thu, Feb 20, 2025 at 05:40:53PM -0800, Junio C Hamano wrote:\n> Comments?\n\nIt's long time ago that I looked into the git source code and I guess\nmany things have changed since then.\n\nAnyhow, here comes my thought about how finding a bisection point could\nwork.\n\nPick the middle commit of `git rev-list --topo-order $bad ^$allgood`.\nLets assume this are 10000 commits. Check the weight of commit[5000].\nDepending on how much the weight is off from 5000 make a bigger or a\nsmaller step up or down to find the next commit to check. So a scaled\nbisection on the topo-order commit list. I think that doesn't\nnecessarily finds a best bisection point, but I havn't thought about\nthat a lot.\n\nBest regards\nUwe\n"},{"id":"512836","messageId":"xmqqo6yvb40a.fsf@gitster.g","threadId":"62981","inReplyTo":"4hx5uvjy7mzntb5zp6o4dg3ut44i46bthyfuera3lnbpbcvrey@kbo3ejype7ae","subject":"Re: first bisection step takes quite a while","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-21T17:29:25Z","receivedAt":"2025-02-21T17:29:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Uwe Kleine-König <u.kleine-koenig@baylibre.com> writes:\n\n> Hello Junio,\n>\n> On Thu, Feb 20, 2025 at 05:40:53PM -0800, Junio C Hamano wrote:\n>> Comments?\n>\n> It's long time ago that I looked into the git source code and I guess\n> many things have changed since then.\n\n;-)  Apparently not much has changed around this area.  I was amazed\nhow things haven't changed around the code since I wrote it in 2007\nwith \"the clever trick\" to improve what Linus called \"truly stupid\"\nalgorithm.  No, I didn't improve the stupid algorithm.  The clever\ntrick was to reduce the need to call it.\n\n> Anyhow, here comes my thought about how finding a bisection point could\n> work.\n>\n> Pick the middle commit of `git rev-list --topo-order $bad ^$allgood`.\n> Lets assume this are 10000 commits. Check the weight of commit[5000].\n> Depending on how much the weight is off from 5000 make a bigger or a\n> smaller step up or down to find the next commit to check. So a scaled\n> bisection on the topo-order commit list. I think that doesn't\n> necessarily finds a best bisection point, but I havn't thought about\n> that a lot.\n\nSince the name of the game is to find \"a\" good enough point in the\nearlier part of a huge bisection session, that certainly is good way\nto think about the problem space.  The commit[] array you have may\nnot be a linear single-strand-of-pearls history, and a naïve\nbisection would not work well in such a case, so we have to be a bit\nmore careful here.\n\nThe code I touched in the illustration needs to either find a merge\ncommit that is really good enough and leave early, or if there is no\nsuch merge commit, compute how many other commits in the range each\nand every merge commit in the range that can be the ancestor of \nthe best non-merge commit on a single-strand-of-pearls history.\n\nThanks.\n\n"},{"id":"512837","messageId":"xmqqcyfbb35h.fsf@gitster.g","threadId":"62981","inReplyTo":"CAP8UFD3XVgJCc2Qa3wWZA54fg38jcpyiDtQOPNc8UQT9uL3vWg@mail.gmail.com","subject":"Re: first bisection step takes quite a while","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-21T17:47:54Z","receivedAt":"2025-02-21T17:47:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder <christian.couder@gmail.com> writes:\n\n> Yeah, it seems to me that in practice this is a bit like bisecting on\n> the first parents first. It would be nice if we had added an option to\n> bisect on the first parents first, so that we could compare your\n> improvement and that option.\n\nUnless you are talking about something entirely different, I am\nafraid you are confused.  We added first-parent bisection in mid\n2020.\n\nAnd the first-parent bisection does make things easy, by making it\ntotally unnecessary to call the \"truly stupid\" count_distance() at\nall.  We can pretend as if we have a single-strand-of-pearls, give\nthe \"good\" end of the history \"1\" as its weight, its direct\ndescendant (and there is only one direct descendant when we are\ndoing first-parent bisection, since there always is only one active\n\"bad\" end of the range in our bisection session) \"2\" as its weight,\nand so on.  The commit that gets N/2 weight is the midway and we\nneed O(N) computation.\n\nUnfortunatly Uwe's original problem description was not about\nfirst-parent bisection being slow.\n\n>>  * The \"this is good enough\" logic currently allows us to be within\n>>    0.1% of the real halfway point.  Until the candidate set becomes\n>>    small enough, we could loosen the criteria to allow larger, say\n>>    3%, slack.  This code is written but not enabled (with \"0 &&\").\n>\n> If we want to do this, I think we could loosen the criteria even if\n> the candidate set is small. Weights are integers so when the number of\n> candidates is around 33 or less, a 3% criteria will mean an exact\n> match. Then the last 5 steps or so (as 2^5 = 32) would still be\n> performed in the same way (with an exact match).\n\nThe above follows the same reasoning why we chose \"division by 1024\"\nin the first place.  The illustration patch postulates that we could\nbe way more aggressive than 0.1% while the set is large by dividing\n64, without wanting to loosen the criteria near the end of the\nbisection session when the remaining set is reasonably small like\n1000 commits.  So we cannot rely on integer division truncating.\n\n>>  * After computing the weight for a merge in \"honest and stupid\"\n>>    way, we know what other commits in the set it can reach.  If the\n>>    weight we computed is way smaller than the half the number of\n>>    commits in the set, that means these commits we can reach from\n>>    the merge we are looking at would score even lower.  We could\n>>    mark them as not-viable before clearing the list to check next\n>>    merge with \"honest and stupid\" way.  Again, this code is written\n>>    but not enabled.\n>> ...\n\n> About #2, I think it could be worth implementing as an option if it is\n> effective in some cases, but the criteria should be loosened even if\n> the candidate set is small. The amount of code to implement it is very\n> small and it's possible that, for some users, having to sometimes\n> perform one more step of testing is not a big deal, compared to\n> bisecting speed.\n\nThe reason why I think #2 would not be effective is quite different,\nbut I'd not go into that, as your conclusion is the same ;-)\n\n> About #3, I think that implementing an option to bisect on the first\n> parents first is likely more useful than implementing it.\n\nSorry, but is very much orthogonal to the issue at hand.  We already\nhave the first-parent bisection.\n\nThe last optimization is all about how to reduce needless calls to\ncount_distance() by rejecting merge commits that can never be an\nancestor that a single-strand-of-pearls history from a non-merge\ncommit with the best \"score\" could reach.  And it is relevant only\nif we want to improve performance of non-first-parent bisection.\n\nThanks.\n\n"},{"id":"512855","messageId":"CAP8UFD3EpwK3edfBfqRWmcncRFG--Q-yHR=K1wZnDHJs56ZipA@mail.gmail.com","threadId":"62981","inReplyTo":"xmqqcyfbb35h.fsf@gitster.g","subject":"Re: first bisection step takes quite a while","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2025-02-21T20:24:59Z","receivedAt":"2025-02-21T20:25:13Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Fri, Feb 21, 2025 at 6:47 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Christian Couder <christian.couder@gmail.com> writes:\n>\n> > Yeah, it seems to me that in practice this is a bit like bisecting on\n> > the first parents first. It would be nice if we had added an option to\n> > bisect on the first parents first, so that we could compare your\n> > improvement and that option.\n>\n> Unless you are talking about something entirely different, I am\n> afraid you are confused.  We added first-parent bisection in mid\n> 2020.\n\nYeah, I know that. But I don't think there is a mode which performs\nfirst-parent bisection first and then continues bisecting normally (so\nnot only on the first parents). That's why I called it an option that\ndoes \"first parents first\" and not just \"first parent\".\n\n> And the first-parent bisection does make things easy, by making it\n> totally unnecessary to call the \"truly stupid\" count_distance() at\n> all.  We can pretend as if we have a single-strand-of-pearls, give\n> the \"good\" end of the history \"1\" as its weight, its direct\n> descendant (and there is only one direct descendant when we are\n> doing first-parent bisection, since there always is only one active\n> \"bad\" end of the range in our bisection session) \"2\" as its weight,\n> and so on.  The commit that gets N/2 weight is the midway and we\n> need O(N) computation.\n\nYeah, that's why a mode that does first parent bisection and then\ncontinues to bisect normally would likely perform well. Because when\nfirst-parent bisection is done, then hopefully the set of commits to\nbisect has been reduced enough that further bisection is fast.\n\n> Unfortunatly Uwe's original problem description was not about\n> first-parent bisection being slow.\n>\n> >>  * The \"this is good enough\" logic currently allows us to be within\n> >>    0.1% of the real halfway point.  Until the candidate set becomes\n> >>    small enough, we could loosen the criteria to allow larger, say\n> >>    3%, slack.  This code is written but not enabled (with \"0 &&\").\n> >\n> > If we want to do this, I think we could loosen the criteria even if\n> > the candidate set is small. Weights are integers so when the number of\n> > candidates is around 33 or less, a 3% criteria will mean an exact\n> > match. Then the last 5 steps or so (as 2^5 = 32) would still be\n> > performed in the same way (with an exact match).\n>\n> The above follows the same reasoning why we chose \"division by 1024\"\n> in the first place.  The illustration patch postulates that we could\n> be way more aggressive than 0.1% while the set is large by dividing\n> 64, without wanting to loosen the criteria near the end of the\n> bisection session when the remaining set is reasonably small like\n> 1000 commits.  So we cannot rely on integer division truncating.\n\nThe code you posted above uses 10000 as the threshold, not 1000:\n\n10000 < nr && abs(diff) < nr / 64) || abs(diff) < nr / 1024)\n\n10000 is between 2^14 and 2^13. This means that the last 13 to 14\nbisection steps likely don't benefit from the \"way more aggressive\"\ncriteria of 3% vs 0.1%. I know that the last steps are the fastest as\nthere are fewer commits to take into account, but still it seems to me\nthat we could make all the steps (except the last 5 or so because then\nthe criteria change likely doesn't change anything) benefit.\n\nYou say that we cannot rely on integer division truncation, but when\ncomparing integers, we could be careful enough so that there is no\ndifference between comparing them to a truncated number versus\ncomparing them to the same number not truncated. So I think we could\nbe able to rely on integer division.\n\nSo maybe just something like:\n\ncriteria = user_priority_is_bisect_speed ? 64 : 1024;\nif (abs(diff) <= nr / criteria)\n     return 1;\n\nThanks for working on this.\n"},{"id":"512866","messageId":"CAP8UFD0xsZWDnH9kLJ4eWfzq4nvAm+qMHcdbZSf0d4-yPG9+5g@mail.gmail.com","threadId":"62981","inReplyTo":"CAP8UFD3EpwK3edfBfqRWmcncRFG--Q-yHR=K1wZnDHJs56ZipA@mail.gmail.com","subject":"Re: first bisection step takes quite a while","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2025-02-21T23:06:56Z","receivedAt":"2025-02-21T23:07:11Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Fri, Feb 21, 2025 at 9:24 PM Christian Couder\n<christian.couder@gmail.com> wrote:\n>\n> On Fri, Feb 21, 2025 at 6:47 PM Junio C Hamano <gitster@pobox.com> wrote:\n\n> > >>  * The \"this is good enough\" logic currently allows us to be within\n> > >>    0.1% of the real halfway point.  Until the candidate set becomes\n> > >>    small enough, we could loosen the criteria to allow larger, say\n> > >>    3%, slack.  This code is written but not enabled (with \"0 &&\").\n> >\n> > The above follows the same reasoning why we chose \"division by 1024\"\n> > in the first place.  The illustration patch postulates that we could\n> > be way more aggressive than 0.1% while the set is large by dividing\n> > 64, without wanting to loosen the criteria near the end of the\n> > bisection session when the remaining set is reasonably small like\n> > 1000 commits.  So we cannot rely on integer division truncating.\n>\n> The code you posted above uses 10000 as the threshold, not 1000:\n>\n> 10000 < nr && abs(diff) < nr / 64) || abs(diff) < nr / 1024)\n\nAlso if \"division by 1024\" means within 0.1% of the real halfway\npoint, then division by 64 means 0.1 * 1024 / 64 = 1.6 % not 3%.\n"},{"id":"512869","messageId":"xmqqldty912l.fsf@gitster.g","threadId":"62981","inReplyTo":"CAP8UFD0xsZWDnH9kLJ4eWfzq4nvAm+qMHcdbZSf0d4-yPG9+5g@mail.gmail.com","subject":"Re: first bisection step takes quite a while","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-22T02:15:46Z","receivedAt":"2025-02-22T02:15:49Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder <christian.couder@gmail.com> writes:\n\n> On Fri, Feb 21, 2025 at 9:24 PM Christian Couder\n> <christian.couder@gmail.com> wrote:\n>>\n>> On Fri, Feb 21, 2025 at 6:47 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n>> > >>  * The \"this is good enough\" logic currently allows us to be within\n>> > >>    0.1% of the real halfway point.  Until the candidate set becomes\n>> > >>    small enough, we could loosen the criteria to allow larger, say\n>> > >>    3%, slack.  This code is written but not enabled (with \"0 &&\").\n>> >\n>> > The above follows the same reasoning why we chose \"division by 1024\"\n>> > in the first place.  The illustration patch postulates that we could\n>> > be way more aggressive than 0.1% while the set is large by dividing\n>> > 64, without wanting to loosen the criteria near the end of the\n>> > bisection session when the remaining set is reasonably small like\n>> > 1000 commits.  So we cannot rely on integer division truncating.\n>>\n>> The code you posted above uses 10000 as the threshold, not 1000:\n>>\n>> 10000 < nr && abs(diff) < nr / 64) || abs(diff) < nr / 1024)\n>\n> Also if \"division by 1024\" means within 0.1% of the real halfway\n> point, then division by 64 means 0.1 * 1024 / 64 = 1.6 % not 3%.\n\nHeh, I suck at arithmetic (but that is why I have you guys around\nfor correction ;-).\n\nThe current code makes sure that we do not punt with an inexact\nresult below nr for which nr/1024 is truncated away.  The overly\nloose cutoff that uses nr/64 needs to stop kicking in way before\nthat happens to make sure we do not affect correctness with the\nchange to optimize, and that is the only reason why 10000 was\narbitrary chosen.  The threashold could have been set at 5000, or\n100000.\n\nExact numbers do not matter as much as the real issue, i.e.,\nlimiting the possible damage to correctness from the change near the\nend of a bisect session.\n\nThanks.\n\n"},{"id":"512922","messageId":"CALnO6CCoD8iRENU+OkCAkKGhiHPVtACZMojAsJbo8=cDYLC_eQ@mail.gmail.com","threadId":"62981","inReplyTo":"CAP8UFD3EpwK3edfBfqRWmcncRFG--Q-yHR=K1wZnDHJs56ZipA@mail.gmail.com","subject":"Re: first bisection step takes quite a while","fromName":"D. Ben Knoble","fromEmail":"ben.knoble@gmail.com","sentAt":"2025-02-24T17:27:15Z","receivedAt":"2025-02-24T17:27:29Z","isPatch":false,"sender":{"key":"ben.knoble@gmail.com","avatar":"https://avatars.githubusercontent.com/u/22802209?v=4"},"body":"On Fri, Feb 21, 2025 at 3:25 PM Christian Couder\n<christian.couder@gmail.com> wrote:\n>\n> On Fri, Feb 21, 2025 at 6:47 PM Junio C Hamano <gitster@pobox.com> wrote:\n> >\n> > Christian Couder <christian.couder@gmail.com> writes:\n> >\n> > > Yeah, it seems to me that in practice this is a bit like bisecting on\n> > > the first parents first. It would be nice if we had added an option to\n> > > bisect on the first parents first, so that we could compare your\n> > > improvement and that option.\n> >\n> > Unless you are talking about something entirely different, I am\n> > afraid you are confused.  We added first-parent bisection in mid\n> > 2020.\n>\n> Yeah, I know that. But I don't think there is a mode which performs\n> first-parent bisection first and then continues bisecting normally (so\n> not only on the first parents). That's why I called it an option that\n> does \"first parents first\" and not just \"first parent\".\n\nThis was also how I read your original reply, and I think it would be\na nice addition. It automates something I've done a few times when\nbisecting in large repos where the good reference is far away in terms\nof commits, and where automated build+test (bisect run) can be slow.\n\nEssentially\n1. bisect with --first-parent to find a bad merge M\n2. bisect between M^1 and M^@ (maybe this is the set M^-2, if I'm\nreading \"git help revisions\" correctly?)\n\nwith the idea that (1) is fast but coarse (but also helps skip\nunrelated, potentially bad commits in the merge parents) and (2) is\nfine-grained but still fast because the set of commits is hopefully\nsmall.\n\n(Most readers know the previous justification, I expect, but I figured\nI would spell it out.)\n\n> Thanks for working on this.\n\nSeconded!\n\n-- \nD. Ben Knoble\n"}]}