The README doesn’t explain what algorithm bisect-find uses to try to find the older “good” commit. I consider that necessary knowledge to decide whether the tool is worth using: if the tool scanned backwards one commit at a time, deciding whether each commit is good might be slower than searching for a good commit manually. Thankfully, from the code, the tool seems somewhat smarter than that:
let jump = (4 + log.bad_count + log.skip_count).saturating_pow(2);
saturating_pow is an overflow-safe way of calling pow, which “raises self to the power of exp”. So the formula for jump is equivalent to (4 + commits_marked_bad + commits_marked_skip)².
Each time you identify a commit as bad or skipped during bisect-find, the tool checks out the jumpth ancestor of the last identified bad commit. It finds this commit using the ~ operator.
After calling git bisect-find bad for the first time, you will have marked one commit as bad and none as skipped, so jump will start at 25. If the 25th most recent commit isn’t the good commit you are looking for, the program will look 36 commits back, then 49 commits back, and so on.
From reading the code, I think if you reach the beginning of the commit’s history without finding a good commit, this tool will exit with an error, even if there are commits it jumped over that you might have marked good.
That blog post introduces the tool better than the README does. However, it’s wrong about the behavior of the published code:
It just jumps back twice as far each time (following first parents).
git_bisect_next.rs, which currently jumps back quadratically as I described above, has never been changed since the repo’s initial commit on 2024-03-17. That blog post was published on 2024-04-19 (its publication date of 2024-05-19 is erroneous). I think the author is describing the development version on their computer, and they forgot to git push.
Yes you are right. I think I probably just had a little brain fart when writing the code. I don’t think I meant to switch from exponential to quadratic. I think I’ll update the code to be actually exponential but I’ll think about it a bit first to be sure that I didn’t make that decision for a good reason.
The README doesn’t explain what algorithm
bisect-finduses to try to find the older “good” commit. I consider that necessary knowledge to decide whether the tool is worth using: if the tool scanned backwards one commit at a time, deciding whether each commit is good might be slower than searching for a good commit manually. Thankfully, from the code, the tool seems somewhat smarter than that:saturating_powis an overflow-safe way of callingpow, which “raises self to the power ofexp”. So the formula forjumpis equivalent to (4 + commits_marked_bad + commits_marked_skip)².Each time you identify a commit as bad or skipped during
bisect-find, the tool checks out thejumpth ancestor of the last identified bad commit. It finds this commit using the~operator.After calling
git bisect-find badfor the first time, you will have marked one commit as bad and none as skipped, sojumpwill start at 25. If the 25th most recent commit isn’t the good commit you are looking for, the program will look 36 commits back, then 49 commits back, and so on.From reading the code, I think if you reach the beginning of the commit’s history without finding a good commit, this tool will exit with an error, even if there are commits it jumped over that you might have marked good.
The blog post explains it better than the README https://kevincox.ca/2024/05/19/git-bisect-find/
That blog post introduces the tool better than the README does. However, it’s wrong about the behavior of the published code:
git_bisect_next.rs, which currently jumps back quadratically as I described above, has never been changed since the repo’s initial commit on 2024-03-17. That blog post was published on 2024-04-19 (its publication date of 2024-05-19 is erroneous). I think the author is describing the development version on their computer, and they forgot togit push.Yes you are right. I think I probably just had a little brain fart when writing the code. I don’t think I meant to switch from exponential to quadratic. I think I’ll update the code to be actually exponential but I’ll think about it a bit first to be sure that I didn’t make that decision for a good reason.