7 ms·

Git Bisect-Find

50 points by nalgeon 3y ago

vagab0nd 3y ago
"2024/05/19", "Posted in 30 days" Premature announcement?
- kevincox 3y ago
  Oops, just typoed the date. I probably won't be able to fix that until tomorrow.
  - kevincox 3y ago
    Now fixed.
vladf 3y ago
Ah! Finally a real world use for egg drop (with eggs and floors both equal to num commits since init, but maybe fewer eggs for those less patient).
- explodes 3y ago
  That was the first thing that came to my mind! Though I cannot find the original, well-written article I read some years ago, this link covers the problem for those interested: https://www.geeksforgeeks.org/egg-dropping-puzzle-dp-11/ https://www.geeksforgeeks.org/egg-dropping-puzzle-dp-11/
- kevincox 3y ago
  I see how the problem maps onto this. It seems like the main issue in the original problem is that you have a fixed number of eggs. But for git bisect-find there are unlimited eggs, but we want to use as few as possible. It is also quite different because there is a bias that most targets are probably sooner. If you have a 10 year old repo it is more likely that an obvious bug is in the last month than the first month. (Otherwise the optimal would always just be to test the first commit and then assuming that it is good just bisect from there).
  - kevincox 2y ago
    * I don't see how.
KTibow 3y ago
> Obviously jumping right to the first commit would reduce the number of git bisect-find steps. But would result in more git bisect. Putting in a number of months/years ago to start from would be a good middle ground.
- kevincox 3y ago
  Yeah. I've been considering something like `git bisect-find start 14d` as people often have some sort of notion for how long something was likely to fly under the radar. If it is an obvious bug maybe a few days, if it is subtle maybe start by jumping back a month.
thealistra 3y ago
Do people really use bisect in their professional life? Can you sensibly use it without an enforcement of every PR being squashed, as otherwise you have not working, half baked commits all the time while bisecting? And you can’t compile, not even saying about stating if your bug is still reproducible or not.
- saghm 3y ago
  Yeah, I've used it a bunch. No project I've ever worked on has made it a practice to merge not working, half-baked commits at all. Squashing before merging like you mention has been pretty much universal on the codebases I've worked on; if it's not done on a given PR, it's usually because of an explicit rebase to split things up manually in a way that wouldn't break this.
- univerio 3y ago
  Yes! But for me it's very rare (< 1/yr) and I'm like a kid in a toy store every time I get to bust it out. My employer uses squash commits so that's not a problem for us, but you're right that commits far enough back will be unlikely to be in a buildable state.
- CJefferson 3y ago
  It depends on your type of software. I use it all the time for mathematical software. I have an input I keep around, which checks "is the program, very basically, doing what it should?", which is compatible with all previous versions. I use that when to 'git bisect skip' commits which don't build, or if when built aren't functioning at all. It's not 100% perfect, but works well for me.
- smcameron 3y ago
  > PR being squashed, as otherwise you have not working, half baked commits squashing PRs is not the only way to avoid broken half-baked commits. Use something like stgit and it's easy to create a stream of 100s of commits that all work and make sense without squashing any commits together. I used git bisect yesterday.
  - 3y ago
sltkr 3y ago
For the algorithmically inclined, this is basically exponential search: https://en.wikipedia.org/wiki/Exponential_search https://en.wikipedia.org/wiki/Exponential_search
yarg 3y ago
I scripted something similar at an old workplace; Basically you'd pass a command to the script and it would track down the last commit that did not fail the command. It'd search HEAD~4, HEAD~8, HEAD~16... until it found a good commit, then bisect. The problem that I found is that bugs that have already been fixed still triggered in the past, and the only solution that I found to that was to branch the first buggy commit, apply a fix and squash and then rebase on top of that. Not the best practice, but it saved me a lot of time.
sjburt 3y ago
if you don't know what commit is good, just go way way way back. Go back 10,000 commits instead of 1,000. The magic of bisection search is that opening your search window by 10x only adds 3 (well, 3.332) extra bisections.
- JohnKemeny 3y ago
  The actual way to do it is to go back in exponentially larger steps until you reach a good commit. 1, 2, 4, 8, ... Then you already know that the bad commit is between 2^{k-1}st and 2^{k}th commit.
YoshiRulz 3y ago
> I do wonder if jumping back by twice as much is optimal. Some time ago, the idea came to me of weighting commits by diff size (as in LOC added + LOC removed, no thought to binary files), and using that to pick the halfway point for bisection. I'm not familiar with Git internals so I left it there. But I imagine that, while it wouldn't make a huge difference in either case, it would benefit your tool more than it would a regular bisect.
- deleted 3y ago
  [deleted]
- kevincox 3y ago
  I've also pondered about custom functions to rank each commit. Maybe you can mark some sub-directory of the repo as 8x more likely to cause trouble than others and that would effect the split point decision. For example if this seems like a UI bug mark the frontend/ directory as extra suspicious. But don't completely rule out the backend as it may be triggering the frontend bug.
deleted 3y ago
[deleted]

Git Bisect-Find

50 points by nalgeon 3y ago

vagab0nd 3y ago

"2024/05/19", "Posted in 30 days" Premature announcement?

kevincox 3y ago
Oops, just typoed the date. I probably won't be able to fix that until tomorrow.
- kevincox 3y ago
  Now fixed.

vladf 3y ago

Ah! Finally a real world use for egg drop (with eggs and floors both equal to num commits since init, but maybe fewer eggs for those less patient).

explodes 3y ago
That was the first thing that came to my mind! Though I cannot find the original, well-written article I read some years ago, this link covers the problem for those interested: https://www.geeksforgeeks.org/egg-dropping-puzzle-dp-11/ https://www.geeksforgeeks.org/egg-dropping-puzzle-dp-11/
kevincox 3y ago
I see how the problem maps onto this. It seems like the main issue in the original problem is that you have a fixed number of eggs. But for git bisect-find there are unlimited eggs, but we want to use as few as possible. It is also quite different because there is a bias that most targets are probably sooner. If you have a 10 year old repo it is more likely that an obvious bug is in the last month than the first month. (Otherwise the optimal would always just be to test the first commit and then assuming that it is good just bisect from there).
- kevincox 2y ago
  * I don't see how.

KTibow 3y ago

> Obviously jumping right to the first commit would reduce the number of git bisect-find steps. But would result in more git bisect. Putting in a number of months/years ago to start from would be a good middle ground.

kevincox 3y ago
Yeah. I've been considering something like `git bisect-find start 14d` as people often have some sort of notion for how long something was likely to fly under the radar. If it is an obvious bug maybe a few days, if it is subtle maybe start by jumping back a month.

thealistra 3y ago

Do people really use bisect in their professional life? Can you sensibly use it without an enforcement of every PR being squashed, as otherwise you have not working, half baked commits all the time while bisecting? And you can’t compile, not even saying about stating if your bug is still reproducible or not.

saghm 3y ago
Yeah, I've used it a bunch. No project I've ever worked on has made it a practice to merge not working, half-baked commits at all. Squashing before merging like you mention has been pretty much universal on the codebases I've worked on; if it's not done on a given PR, it's usually because of an explicit rebase to split things up manually in a way that wouldn't break this.
univerio 3y ago
Yes! But for me it's very rare (< 1/yr) and I'm like a kid in a toy store every time I get to bust it out. My employer uses squash commits so that's not a problem for us, but you're right that commits far enough back will be unlikely to be in a buildable state.
CJefferson 3y ago
It depends on your type of software. I use it all the time for mathematical software. I have an input I keep around, which checks "is the program, very basically, doing what it should?", which is compatible with all previous versions. I use that when to 'git bisect skip' commits which don't build, or if when built aren't functioning at all. It's not 100% perfect, but works well for me.
smcameron 3y ago
> PR being squashed, as otherwise you have not working, half baked commits squashing PRs is not the only way to avoid broken half-baked commits. Use something like stgit and it's easy to create a stream of 100s of commits that all work and make sense without squashing any commits together. I used git bisect yesterday.
- 3y ago

sltkr 3y ago

For the algorithmically inclined, this is basically exponential search: https://en.wikipedia.org/wiki/Exponential_search https://en.wikipedia.org/wiki/Exponential_search

yarg 3y ago

I scripted something similar at an old workplace; Basically you'd pass a command to the script and it would track down the last commit that did not fail the command. It'd search HEAD~4, HEAD~8, HEAD~16... until it found a good commit, then bisect. The problem that I found is that bugs that have already been fixed still triggered in the past, and the only solution that I found to that was to branch the first buggy commit, apply a fix and squash and then rebase on top of that. Not the best practice, but it saved me a lot of time.

sjburt 3y ago

if you don't know what commit is good, just go way way way back. Go back 10,000 commits instead of 1,000. The magic of bisection search is that opening your search window by 10x only adds 3 (well, 3.332) extra bisections.

JohnKemeny 3y ago
The actual way to do it is to go back in exponentially larger steps until you reach a good commit. 1, 2, 4, 8, ... Then you already know that the bad commit is between 2^{k-1}st and 2^{k}th commit.

YoshiRulz 3y ago

> I do wonder if jumping back by twice as much is optimal. Some time ago, the idea came to me of weighting commits by diff size (as in LOC added + LOC removed, no thought to binary files), and using that to pick the halfway point for bisection. I'm not familiar with Git internals so I left it there. But I imagine that, while it wouldn't make a huge difference in either case, it would benefit your tool more than it would a regular bisect.

deleted 3y ago
[deleted]
kevincox 3y ago
I've also pondered about custom functions to rank each commit. Maybe you can mark some sub-directory of the repo as 8x more likely to cause trouble than others and that would effect the split point decision. For example if this seems like a UI bug mark the frontend/ directory as extra suspicious. But don't completely rule out the backend as it may be triggering the frontend bug.

deleted 3y ago

[deleted]