{"thread":{"id":"62800","subject":"[bug] \"git bisect old v3.0\" takes 21 mins on Linux repo","startedAt":"2025-01-13T22:11:10Z","lastAt":"2025-01-17T16:51:00Z","messageCount":10,"participants":["Askar Safin","D. Ben Knoble","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"510457","messageId":"19461b87a5c.5a2ea74016716.8214238482389812984@zohomail.com","threadId":"62800","inReplyTo":null,"subject":"[bug] \"git bisect old v3.0\" takes 21 mins on Linux repo","fromName":"Askar Safin","fromEmail":"safinaskar@zohomail.com","sentAt":"2025-01-13T22:11:07Z","receivedAt":"2025-01-13T22:11:10Z","isPatch":false,"sender":{"key":"safinaskar@zohomail.com","avatar":null},"body":"Hi. This is bug report. \"git bisect\" is unacceptable slow on Linux repo.\n\nSteps to reproduce:\n\n===\nd-user@comp:/tmp/t$ git clone git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git\nCloning into 'linux'...\nremote: Enumerating objects: 13079335, done.\nremote: Counting objects: 100% (153/153), done.\nremote: Compressing objects: 100% (108/108), done.\nremote: Total 13079335 (delta 84), reused 70 (delta 45), pack-reused 13079182\nReceiving objects: 100% (13079335/13079335), 5.18 GiB | 13.72 MiB/s, done.\nResolving deltas: 100% (10454171/10454171), done.\nUpdating files: 100% (87234/87234), done.\nd-user@comp:/tmp/t$ cd linux\nd-user@comp:/tmp/t/linux$ git bisect start\nstatus: waiting for both good and bad commits\nd-user@comp:/tmp/t/linux$ git bisect new v6.13-rc7\nstatus: waiting for good commit(s), bad commit known\nd-user@comp:/tmp/t/linux$ time -p git bisect old v3.0\nBisecting: 535608 revisions left to test after this (roughly 19 steps)\n[62606c224d72a98c35d21a849f95cccf95b0a252] Merge branch 'linus' of git://git.kernel.org/pub/scm/linux/kernel/git/herbert/crypto-2.6\nreal 1293.32\nuser 1291.70\nsys 1.41\n===\n\n1293.32 s (21 mins) is unacceptably slow. During \"git bisect\" execution process \"git bisect--helper\" occupies 100 % of CPU in \"htop\" output. (This means that \"git bisect--helper\" is not parallel program, overwise it would occupy significantly more than 100 %).\n\nSo, please, make \"git bisect\" faster. (Maybe it makes sence to make it parallel?)\n\nMy OS is Debian 12 Bookworm. Output of \"uname -a\" is \"Linux comp 6.1.0-28-amd64 #1 SMP PREEMPT_DYNAMIC Debian 6.1.119-1 (2024-11-22) x86_64 GNU/Linux\".\n\nMy git version is 2.39.5.\n\nThe above test was performed on tmpfs on real hardware without any kind of virtualization.\n\nI will try to perform the same test with latest git version and will report my findings in the next mail (hopefully today).\n\n--\nAskar Safin\nhttps://types.pl/@safinaskar\n\n"},{"id":"510462","messageId":"20250113231649.644012-1-safinaskar@zohomail.com","threadId":"62800","inReplyTo":"19461b87a5c.5a2ea74016716.8214238482389812984@zohomail.com","subject":"Re: [bug] \"git bisect old v3.0\" takes 21 mins on Linux repo","fromName":"Askar Safin","fromEmail":"safinaskar@zohomail.com","sentAt":"2025-01-13T23:16:49Z","receivedAt":"2025-01-13T23:17:20Z","isPatch":false,"sender":{"key":"safinaskar@zohomail.com","avatar":null},"body":"The same thing happens with git 2.47.1.\n\nIt seems \"git bisect\" didn't change much from 2.47.1, so I think\nthere is no sense to test more versions (but I can if you ask)\n"},{"id":"510546","messageId":"CALnO6CAzN1oeT4tMjJ1Qm4dW0xdVkVKHJ39oJTX8R8E614FH6g@mail.gmail.com","threadId":"62800","inReplyTo":"19461b87a5c.5a2ea74016716.8214238482389812984@zohomail.com","subject":"Re: [bug] \"git bisect old v3.0\" takes 21 mins on Linux repo","fromName":"D. Ben Knoble","fromEmail":"ben.knoble@gmail.com","sentAt":"2025-01-14T22:21:20Z","receivedAt":"2025-01-14T22:21:33Z","isPatch":false,"sender":{"key":"ben.knoble@gmail.com","avatar":"https://avatars.githubusercontent.com/u/22802209?v=4"},"body":"On Mon, Jan 13, 2025 at 5:11 PM Askar Safin wrote:\n>\n> Hi. This is bug report. \"git bisect\" is unacceptable slow on Linux repo.\n\nThat may be a bit inflammatory ;)\n\n>\n> Steps to reproduce:\n>\n> ===\n> d-user@comp:/tmp/t$ git clone git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git\n> Cloning into 'linux'...\n> remote: Enumerating objects: 13079335, done.\n> remote: Counting objects: 100% (153/153), done.\n> remote: Compressing objects: 100% (108/108), done.\n> remote: Total 13079335 (delta 84), reused 70 (delta 45), pack-reused 13079182\n> Receiving objects: 100% (13079335/13079335), 5.18 GiB | 13.72 MiB/s, done.\n> Resolving deltas: 100% (10454171/10454171), done.\n> Updating files: 100% (87234/87234), done.\n> d-user@comp:/tmp/t$ cd linux\n> d-user@comp:/tmp/t/linux$ git bisect start\n> status: waiting for both good and bad commits\n> d-user@comp:/tmp/t/linux$ git bisect new v6.13-rc7\n> status: waiting for good commit(s), bad commit known\n> d-user@comp:/tmp/t/linux$ time -p git bisect old v3.0\n> Bisecting: 535608 revisions left to test after this (roughly 19 steps)\n> [62606c224d72a98c35d21a849f95cccf95b0a252] Merge branch 'linus' of git://git.kernel.org/pub/scm/linux/kernel/git/herbert/crypto-2.6\n> real 1293.32\n> user 1291.70\n> sys 1.41\n> ===\n\nFWIW:\n\n$ time git rev-list --count v3.0...v6.13-rc7\n1070175\ngit rev-list --count v3.0...v6.13-rc7 13,57s user 1,41s system 96%\ncpu 15,466 total\n\nThat's a large number of revisions to bisect. Further,\n\n# --force needed because my filesystem is case-insensitive :eyeroll:\n$ time git checkout [--force] 62606c224d72a98c35d21a849f95cccf95b0a252\ngit checkout --force 62606c224d72a98c35d21a849f95cccf95b0a252 7,94s\nuser 18,54s system 96% cpu 27,360 total\n\nUsing pathspecs or a smaller commit range should help speed up the\nstart. (On a recent git, the helper is gone, so I'm not sure where the\ntime is spent—but I do notice that `git bisect start v6.13-rc7 v3.0`\nis slow enough that I've killed it rather than wait.)\n\n-- \nD. Ben Knoble\n"},{"id":"510684","messageId":"20250116105246.GF773990@coredump.intra.peff.net","threadId":"62800","inReplyTo":"CALnO6CAzN1oeT4tMjJ1Qm4dW0xdVkVKHJ39oJTX8R8E614FH6g@mail.gmail.com","subject":"Re: [bug] \"git bisect old v3.0\" takes 21 mins on Linux repo","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-01-16T10:52:46Z","receivedAt":"2025-01-16T10:52:47Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 14, 2025 at 05:21:20PM -0500, D. Ben Knoble wrote:\n\n> FWIW:\n> \n> $ time git rev-list --count v3.0...v6.13-rc7\n> 1070175\n> git rev-list --count v3.0...v6.13-rc7 13,57s user 1,41s system 96%\n> cpu 15,466 total\n> \n> That's a large number of revisions to bisect. Further,\n\nYeah. I'm not very familiar with the bisect code, but it looks like it's\nquadratic. In do_find_bisection(), we have a big list of commits, and we\niterate like this:\n\n for (p = list; p; p = p->next) {\n if (p->item->object.flags & UNINTERESTING)\n continue;\n if (weight(p) != -2)\n continue;\n if (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)\n BUG(\"shouldn't be calling count-distance in fp mode\");\n weight_set(p, count_distance(p));\n clear_distance(list);\n\n /* Does it happen to be at half-way? */\n if (!(bisect_flags & FIND_BISECTION_ALL) &&\n approx_halfway(p, nr))\n return p;\n counted++;\n }\n\nThat clear_distance() call likewise iterates through the list to clear\nthe COUNTED flags from each. I guess we might be able to traverse down\nfrom the tip of the commit we're operating on, clearing flags there.\nSince that's how the flags are set in count_distance().\n\nI suspect it's still quadratic, though, because count_distance() is\ntraversing separately for each (and in the worst case everything is\nreachable from it). But it might still improve things in practice.\n\n-Peff\n"},{"id":"510693","messageId":"20250116125313.GA2301268@coredump.intra.peff.net","threadId":"62800","inReplyTo":"20250116105246.GF773990@coredump.intra.peff.net","subject":"Re: [bug] \"git bisect old v3.0\" takes 21 mins on Linux repo","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-01-16T12:53:13Z","receivedAt":"2025-01-16T12:53:15Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 16, 2025 at 05:52:46AM -0500, Jeff King wrote:\n\n> That clear_distance() call likewise iterates through the list to clear\n> the COUNTED flags from each. I guess we might be able to traverse down\n> from the tip of the commit we're operating on, clearing flags there.\n> Since that's how the flags are set in count_distance().\n> \n> I suspect it's still quadratic, though, because count_distance() is\n> traversing separately for each (and in the worst case everything is\n> reachable from it). But it might still improve things in practice.\n\nApparently I'm good at suspecting. Here's a patch to make\nclear_distance() walk the same commits as count_distance(), including\nthe string-of-pearls recursion avoidance:\n\ndiff --git a/bisect.c b/bisect.c\nindex 1a9069c9ad..ecf656316b 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -69,12 +69,28 @@ static int count_distance(struct commit_list *entry)\n \treturn nr;\n }\n \n-static void clear_distance(struct commit_list *list)\n+static void clear_distance(struct commit_list *entry)\n {\n-\twhile (list) {\n-\t\tstruct commit *commit = list->item;\n+\twhile (entry) {\n+\t\tstruct commit *commit = entry->item;\n+\t\tstruct commit_list *p;\n+\n+\t\tif (commit->object.flags & UNINTERESTING)\n+\t\t\tbreak;\n+\t\tif (!(commit->object.flags & COUNTED))\n+\t\t\tbreak;\n+\n \t\tcommit->object.flags &= ~COUNTED;\n-\t\tlist = list->next;\n+\n+\t\tp = commit->parents;\n+\t\tentry = p;\n+\t\tif (p) {\n+\t\t\tp = p->next;\n+\t\t\twhile (p) {\n+\t\t\t\tclear_distance(p);\n+\t\t\t\tp = p->next;\n+\t\t\t}\n+\t\t}\n \t}\n }\n \n@@ -338,7 +354,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\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-\t\tclear_distance(list);\n+\t\tclear_distance(p);\n \n \t\t/* Does it happen to be at half-way? */\n \t\tif (!(bisect_flags & FIND_BISECTION_ALL) &&\n\nIt cuts Askar's case on my machine from 16m51s to 9m34s. So a big\nimprovement but still...not great.\n\nI suspect that the whole bisection count algorithm needs to be rewritten\nto all run in a single traversal. I guess if you iterate over the\ncommits in reverse-topo order, you should be able to just compute each\ndistance as \"d(commit) = 1; d(commit) += d(p) for parents(commit)\". But\nit's not a problem I've thought a lot about, so I'm probably missing\nsome subtlety.\n\nAt any rate, an easier way to time this is:\n\n git rev-list --bisect v3.0..v6.13-rc7\n\nwhich is the expensive part of what git-bisect is doing under the hood.\n\n-Peff\n"},{"id":"510699","messageId":"20250116135227.GA2323616@coredump.intra.peff.net","threadId":"62800","inReplyTo":"20250116125313.GA2301268@coredump.intra.peff.net","subject":"Re: [bug] \"git bisect old v3.0\" takes 21 mins on Linux repo","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-01-16T13:52:27Z","receivedAt":"2025-01-16T13:52:28Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 16, 2025 at 07:53:13AM -0500, Jeff King wrote:\n\n> I suspect that the whole bisection count algorithm needs to be rewritten\n> to all run in a single traversal. I guess if you iterate over the\n> commits in reverse-topo order, you should be able to just compute each\n> distance as \"d(commit) = 1; d(commit) += d(p) for parents(commit)\". But\n> it's not a problem I've thought a lot about, so I'm probably missing\n> some subtlety.\n\nOh nevermind, that won't work, as it double-counts commits that are\nreachable from each parent. Still, it feels like there ought to be a way\nto compute it with a single traversal.\n\nI think this is similar to the reachability bitmap computation, which\ncomputes a bitmap for each commit (and then the weight of each commit is\nthe number of set bits, but we've removed the duplicates). We do that in\na single traversal these days, but it's pretty complex and heavyweight.\n\nSo I think there's room for improvement here, but it sounds non-trivial.\n\n-Peff\n"},{"id":"510715","messageId":"xmqqo706u2z0.fsf@gitster.g","threadId":"62800","inReplyTo":"20250116135227.GA2323616@coredump.intra.peff.net","subject":"Re: [bug] \"git bisect old v3.0\" takes 21 mins on Linux repo","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-01-16T16:40:19Z","receivedAt":"2025-01-16T16:40:22Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Oh nevermind, that won't work, as it double-counts commits that are\n> reachable from each parent. Still, it feels like there ought to be a way\n> to compute it with a single traversal.\n\nIt is somewhat embarrassing and amusing at the same time that the\n\"This is a truly stupid algorithm, but it's only used for bisection,\nand we just don't care enough.\" comment Linus wrote long time ago is\nstill with us. Many men tried, they did not die but failed.\n\n> I think this is similar to the reachability bitmap computation, which\n> computes a bitmap for each commit (and then the weight of each commit is\n> the number of set bits, but we've removed the duplicates). We do that in\n> a single traversal these days, but it's pretty complex and heavyweight.\n\nThe original algorithm was done way before any of the recent\nauxiliary data structures were invented. There may be approaches we\nhaven't tried and can now try to improve bisection, expoliting newer\nthings like reachability bitmaps.\n"},{"id":"510754","messageId":"19472bf2353.2c31e5fd10001.1997220058832133228@zohomail.com","threadId":"62800","inReplyTo":"xmqqo706u2z0.fsf@gitster.g","subject":"Re: [bug] \"git bisect old v3.0\" takes 21 mins on Linux repo","fromName":"Askar Safin","fromEmail":"safinaskar@zohomail.com","sentAt":"2025-01-17T05:31:56Z","receivedAt":"2025-01-17T05:32:04Z","isPatch":false,"sender":{"key":"safinaskar@zohomail.com","avatar":null},"body":"I think \"git bisect\" is very important part of git.\n\nLinux's \"submitting-patches\" contains this text:\n> When dividing your change into a series of patches, take special care to ensure that the kernel builds and runs properly after each patch in the series. Developers using git bisect to track down a problem can end up splitting your patch series at any point; they will not thank you if you introduce bugs in the middle.\n\n( https://docs.kernel.org/process/submitting-patches.html )\n\nSo, as you can see, existance of \"git bisect\" is rationale for contributor guidelines!\n\nContributor rules written the way they are because of \"git bisect\"!!!\n\n--\nAskar Safin\nhttps://types.pl/@safinaskar\n\n"},{"id":"510806","messageId":"20250117131404.GD2893666@coredump.intra.peff.net","threadId":"62800","inReplyTo":"19472bf2353.2c31e5fd10001.1997220058832133228@zohomail.com","subject":"Re: [bug] \"git bisect old v3.0\" takes 21 mins on Linux repo","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-01-17T13:14:04Z","receivedAt":"2025-01-17T13:14:06Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 17, 2025 at 09:31:56AM +0400, Askar Safin wrote:\n\n> I think \"git bisect\" is very important part of git.\n\nMe too. But that doesn't make it any easier to figure out a more\noptimized algorithm. ;)\n\nIn the meantime, here are some other options:\n\n 1. You can manually pick a commit that is around the midpoint of\n history and try it. That will quickly reduce the search space to\n something more manageable. E.g., maybe try v4.0 and v5.0 and use\n those as your initial good/bad starting points (depending on the\n result). Those might not be the exact halfway point, but it's good\n enough to get started.\n\n 2. In a branchy history like linux.git, you can make the problem space\n much smaller by looking only at the history along the first parent.\n E.g.:\n\n git bisect start --first-parent\n git bisect good v3.0\n git bisect bad v6.13-rc7\n\n That runs in about 7 seconds for me. It will probably give you a\n merge commit rather than the exact culprit along the second-parent\n history. But with that merge commit, you can start a new, much\n smaller bisection with it as the \"bad\" and its first-parent as the\n \"good\".\n\nBoth of those are trading a bit of accuracy in finding the exact\nmidpoint in the early steps. It's perhaps another possible option for\ngit-bisect itself: if we see a very large number of commits, we could\ntry to approximate rather than finding the exact answer. In most\nhistories I'd expect that taking the midpoint of a linearized topo-order\nwould get you a pretty reasonable outcome. E.g.:\n\n total=$(git rev-list --count v3.0..v6.13-rc7)\n git rev-list --topo-order v3.0..v6.13-rc7 |\n tail -n +$((total / 2)) | head -n 1\n\nruns in about 2s on my machine. The commit it finds, ed194d136769,\nis pretty close to the middle:\n\n $ git rev-list --count v3.0..ed194d136769\n 526863\n $ git rev-list --count ed194d136769..v6.13-rc7\n 543312\n\n-Peff\n"},{"id":"510816","messageId":"xmqqv7udmlji.fsf@gitster.g","threadId":"62800","inReplyTo":"20250117131404.GD2893666@coredump.intra.peff.net","subject":"Re: [bug] \"git bisect old v3.0\" takes 21 mins on Linux repo","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-01-17T16:50:57Z","receivedAt":"2025-01-17T16:51:00Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Both of those are trading a bit of accuracy in finding the exact\n> midpoint in the early steps. It's perhaps another possible option for\n> git-bisect itself: if we see a very large number of commits, we could\n> try to approximate rather than finding the exact answer.\n\nAnother thing the user may (but \"bisect\" itself cannot) try is to\nuse a path-limited bisection (that is, if you know your breakage is\ninside one subsytem, you only check commits that touch the area).\n\n> In most\n> histories I'd expect that taking the midpoint of a linearized topo-order\n> would get you a pretty reasonable outcome. E.g.:\n>\n> total=$(git rev-list --count v3.0..v6.13-rc7)\n> git rev-list --topo-order v3.0..v6.13-rc7 |\n> tail -n +$((total / 2)) | head -n 1\n>\n> runs in about 2s on my machine. The commit it finds, ed194d136769,\n> is pretty close to the middle:\n>\n> $ git rev-list --count v3.0..ed194d136769\n> 526863\n> $ git rev-list --count ed194d136769..v6.13-rc7\n> 543312\n\nInteresting thought.\n\nWhen I did the \"single strand of pearls\" optimization, I recall I\npunted and said \"we need to count the weight for all merges the\nhonest way\".\n\nOne thing we may want to try is *not* to do the count_distance() for\nall merges. For example, if we have 1000 commits in the range,\nfirst you pick a merge M among them and count how many commits in\nthe range it can reach. Let's say it reachs 400 commits.\n\nWe are trying to find a commit that can reach as close to 500\ncommits, and we know any ancestor of M would reach fewer than 400\ncommits, so we know the score they will get would be worse than M\nwithout running count_distance() on them. We should be able to\nexploit this to optimize, shouldn't we? In order to count the\nnumber for M, count_distance() must have traversed all the ancestor\ncommits of M before coming up with its answer, so by the time we see\nM's score (1000/2 - 400) and realize that it is the best one we have\nseen so far that we aim to improve, we know that the score for all\nthe commits we have seen during that traversal cannot be better than\nM's, no?\n\nIf M can reach 700 commits (instead of 400), the argument goes the\nother way---anything that can reach M can reach even more, so they\ncannot be any closer to the middle than M. Knowing what can reach\nM, however, needs something like reachability bitmap, though.\n\n"}]}