This has been an essential tool for me over the years as a working "data scientist".
Let's say you've been working on an "algorithm", which is a combination of cleverly-crafted SQL to fetch the right data, some ad-hoc data processing code in Python, getting predictions from a model, and some additional mathy stuff to translate the model prediction into something useful. You probably built it interactively in a REPL or notebook environment. You might have some ad-hoc assertions scattered across your scripts, but nothing resembling a test suite.
That's just how things go, and if you did it differently you'd probably never get your work done. But now you have a problem: you have what you believe is a mostly-working/mostly-correct implementation, which you built incrementally and interactively, but now needs to be put into production. Without any real tests, your script has immediately become "legacy code": https://understandlegacycode.com/blog/what-is-legacy-code-is.... If things went well, you had time to extract some common utility functions and write unit tests for them, but you probably don't have more than that.
So now what do you do? You want to refactor it into testable units, so you can build out a proper test suite. But you can't refactor code without tests, lest you risk breaking something. You did extensive manual checking and validation of your outputs, but you can't keep doing that over and over.
In this case, the best option that I've found is to do pretty much what Fowler is advocating for here. Extract a set of known inputs that don't take too long to run through the algorithm, and save their known-valid (or known-close-enough-to-valid) outputs. Then, piece by piece, start refactoring, re-running at each stage. If the outputs differ by more than floating-point roundoff error, you've either found a bug in your original implementation, or you introduced a bug in your refactor. Once you're sure that your refactor is OK, you can "lock in" the changes by adding new tests for the refactored sections. Repeat until satisfied, or out of time.
I worked somewhere that had very complicated price calculations. The complexity came from all sorts of options like pricing schemes, taxes, etc. Many were optional and there were all sorts of interdependencies. It returned an object with lots of pricing details. It really, really sucked to change or debug and there were 0 tests.
I added some tests like you described. Some known price inputs and configuration options and the observed return value from a presumed good state. It didn't verify anything was correct, but it did catch “drift.” The expected object would be updated when changing the calculations, if the difference conformed to expectations based off the changes.
I got some pushback because the tests werent testing correctness but it was trivial to implement and it did catch cases where we changed something and something else that should have been unrelated changed as well. A shit test for even shittier code I guess.
A think such "does the behaviour change" tests are fine. Like, you could not travel back in time and force doing docs and tests on the original sinners.
Seems like you’re describing snapshot testing, whereas the article talks about bisecting.
Bisecting is useful when you find a bug which your test suite did not, and which may have been introduced a long while ago. So you search for the first offender between the last known-good commit and the most recent, usually with an automated test that reproduces the bug, and which should be introduced in the suite to prevent it from happening again in the future.
A snapshot test is basically a “let me know if this unit stops giving this output for this specific input”. And sometimes the fix is to acknowledge that this new output is now the correct version by overwriting it to the snapshot.
DiffDebugging is not a term I have ever heard of before, but I guess it's something I do on a regular basis. The code used to work, it doesn't now, WTF has changed?
Right, this is the common sense approach for identifying the cause of a regression. Not sure what people do other than this unless it's a very simple codebase
My thought is in a complex system the cause of the regression is not usually near the point of failure, so debugging can become unmanageable without the upfront effort of identifying a small set of changes that might be responsible, so you have some more places to set your breakpoints.
A more generic term is "delta debugging", which has been around for a while. git bisect is one example of a tool which does it, another is Zeller's DD tool
https://www.st.cs.uni-saarland.de/dd/
It's also possible to do this is a Bayesian fashion.
My guess would be that you don't always use the middle of the interval, but choose knowledge of the history to guide your choice of the tested revisions.
e. g. recently I was debugging a problem, after two halvings, I saw there's a big refactoring in the remaining interval, so I picked the revision before/after.
> I originally posted this page on 2004-06-01... Diff debugging isn't a term that's caught on much in the industry, but I haven't seen a another term generally used to describe it.
I can't speak to 2004, but these days "bisect" is the standard term in my circles (even when we're not actually using git and its bisect command).
It would be interesting to know whether git was the first to associate that word with this activity... especially given it's atrocious naming of everything else :P
Bisecting an interval has been in use in mathematics quite some time before the existence of Git. Bolzano proved (his version of) the intermediate value theorem in 1817, but it has been used in calculations for _way_ longer.
A well known very large successful trillion dollar company emphasizes this heavily and it’s called identifying Cause By, regressions are categorized before a build is submitted, in the current build, or in previous builds. It’s extremely important to identify cause by (commit) in order to either revert or fix.
Sounds interesting. Could you elaborate, I don't quite understand it. You test for regression errors before commit? But why commit with known regression errors?
As a previous comment said, this sounds like a generalization of regression testing. This article seems to focus on the small scale and omits a couple points relevant to larger scale systems:
- data dependencies cause regressions, so you. need some way to factor this in
- production changes cause regressions
- debugging at the source code level can be laborious past a certain point
The way I approached doing this at another (maybe same) T$ compnay was tooling that could take anything observable -- e.g. logs, program traces, signals from services, service definitions, data, stack traces from debuggers for side-by-side running -- convert it to a normal form (e.g. protobuf or JSON) and then diff that to look for regressions.
Martin, small commits interrupt flow, contain intermediary trains of thought that aren’t relevant, and decompose the entirety of the feature in to unrecognizable pieces removing all wholistic meaning.
sorta. this really varies strongly from person to person and i wouldn't generalize. but you can construct small commits after you're done with your work.
> contain intermediary trains of thought that aren't relevant
no. delete these, they should not be present in the final history.
Note that when (other people's, surely, not yours) bad git history with unrelatedly-broken commits everywhere means you can't bisect, you can use bisect --first-parent to travel down only the first-parent history (which should be just merges to master) rather than having to laboriously figure out whether it's "bad" or "skip" this time.
If you're unfortunate enough to have an impoverished "linear history", you're stuck figuring out whether it's "bad" or "skip", sorry.
The usual definition of “linear history” is equivalent to what you see with “git log --first-parent”. Linear history doesn’t mean that people share every “wip” commit from their private feature branch with everyone else.
With linear history you squash everything into a single, working commit which is applied to the tip of the shared branch. The rationale is that each change is like a published piece of writing: it will have been through multiple drafts and final versions as well as being edited and peer reviewed, but ultimately the only thing any of your peers care about is the finished work. None of the incomplete, broken, or unreviewed intermediate versions belong in the shared history and they can be thrown away.
Two counter points to this. First, the code review discussion is often recorded forever but in a social tool that’s kept separate from the code itself.
Second, if you end up being as famous for your code as Austen, Thackeray, Shakespeare or Da Vinci were for their literature then your “work in progress” commits and v0 drafts are very valuable and worth keeping. The amount of people this could apply to is not a large number.
Very well put. This is the work flow which has worked best for me over different teams.
An opposite which I could accept is asking people to carefully rebase their drafts, but I see it as a higher effort with a bigger risk of screwing up, with a dose of bikeshedding an additional topic, the commit history: "why do you split in 5 commits when 2 would be enough?"
I guess you can keep the drafts if you don't delete feature branches. But I don't see it as extremely useful, unless it's a very talented individual AND very methodical with his commit history.
The culture of rebasing and squashing is the enemy of DiffDebugging. When you squash, you make your deltas very big and less useful. When you rebase, you generally lose your deltas completely, because a rewritten history consists of commits nobody generally tried out.
Unless we're talking about different workflows, squashing works great.
In my team, we merge squash our PRs, having a guideline that they should be a small increment. Here's what happrns:
- when you checkout a commit, you are guaranteed to have a version that was reviewed by a person and validated by ci/cd
- most commits have chsnegs with substance, instead of "log", "debug", etc
Without squash, a person can push 3 commits to a feature branch, ci/cd says the last commit is OK, it gets merged, and you may get 2 commits that don't compile or cause a very basic runtime error due to some typo or whatever.
(not that it could not be solved with due diligence, but that comes with higher effort too)
How do you assure working commits and avoid noise without either squash or rebase?
> a rewritten history consists of commits nobody generally tried out
I find the exact opposite to be true.
When you merge 20 commits from a branch, you add to the history a bunch of unfinished-state checkpoints, which may not even compile individually, and that may make the search longer than it should. Also, those intermediate commits probably never were deployed as individual units.
In a merge-squashed main branch all commits:
* were reviewed as a single unit, but may have originated from multi-commit branches
* are guaranteed to have passed the test suite
* by definition, are at a ready-to-deploy state, even if they contain feature-flagged components
These are much easier to bisect through. And their changeset shouldn’t be any larger than any regularly-merged branches. It’s the same unit of work, merged differently.
If the PR is too large, then you’re probably lumping too much stuff together, which also leads to slower and worse code review cycles.
Many working programmers don't know / use this technique. I bet it was even less used 20 years ago, it took a while till people realized what a revision history could be used for.
Even if people know / use it intuitively, there's a value to describe it more formally and give it a name.
> 20 years ago, at least in my circles, it was ubiquitous.
In my circles, it's not ubiquitous even today.
> BTW sccs was 1972
Many projects didn't use a reasonable versioning system until 10 or 20 years ago.
Before decentralized versioning system, this technique was highly impractical - in one SVN project I worked on, checkout of a branch / revision took ~30 minutes.
CVS tracks commit on individual file basis, checking a global state of the project at a particular timestamp wasn't that trivial / necessarily correct.
I have done poorly thought out versions of this. Reading this will make me a better programmer. I didn’t know much about git bisect. Will play around with it.
It’s magical to experience a short but sweet tip and you just _know_ that (programming) life got a bit easier. Good bang for buck blog post! A few minutes well spent.
The delta debugging paper[1] pointed out that the bug (change set) must satisfy certain properties (Definition 6-8) for the divide and conquer technique to work.
42 comments
[ 3.1 ms ] story [ 95.8 ms ] threadLet's say you've been working on an "algorithm", which is a combination of cleverly-crafted SQL to fetch the right data, some ad-hoc data processing code in Python, getting predictions from a model, and some additional mathy stuff to translate the model prediction into something useful. You probably built it interactively in a REPL or notebook environment. You might have some ad-hoc assertions scattered across your scripts, but nothing resembling a test suite.
That's just how things go, and if you did it differently you'd probably never get your work done. But now you have a problem: you have what you believe is a mostly-working/mostly-correct implementation, which you built incrementally and interactively, but now needs to be put into production. Without any real tests, your script has immediately become "legacy code": https://understandlegacycode.com/blog/what-is-legacy-code-is.... If things went well, you had time to extract some common utility functions and write unit tests for them, but you probably don't have more than that.
So now what do you do? You want to refactor it into testable units, so you can build out a proper test suite. But you can't refactor code without tests, lest you risk breaking something. You did extensive manual checking and validation of your outputs, but you can't keep doing that over and over.
In this case, the best option that I've found is to do pretty much what Fowler is advocating for here. Extract a set of known inputs that don't take too long to run through the algorithm, and save their known-valid (or known-close-enough-to-valid) outputs. Then, piece by piece, start refactoring, re-running at each stage. If the outputs differ by more than floating-point roundoff error, you've either found a bug in your original implementation, or you introduced a bug in your refactor. Once you're sure that your refactor is OK, you can "lock in" the changes by adding new tests for the refactored sections. Repeat until satisfied, or out of time.
I added some tests like you described. Some known price inputs and configuration options and the observed return value from a presumed good state. It didn't verify anything was correct, but it did catch “drift.” The expected object would be updated when changing the calculations, if the difference conformed to expectations based off the changes.
I got some pushback because the tests werent testing correctness but it was trivial to implement and it did catch cases where we changed something and something else that should have been unrelated changed as well. A shit test for even shittier code I guess.
Bisecting is useful when you find a bug which your test suite did not, and which may have been introduced a long while ago. So you search for the first offender between the last known-good commit and the most recent, usually with an automated test that reproduces the bug, and which should be introduced in the suite to prevent it from happening again in the future.
A snapshot test is basically a “let me know if this unit stops giving this output for this specific input”. And sometimes the fix is to acknowledge that this new output is now the correct version by overwriting it to the snapshot.
- reading the affected code - reproducing the problem step by step with a debugger
Which I guess works for all kinds of problems and not just for regressions, therefore people are more used to it?
It's also possible to do this is a Bayesian fashion.
e. g. recently I was debugging a problem, after two halvings, I saw there's a big refactoring in the remaining interval, so I picked the revision before/after.
https://github.com/ealdwulf/bbchop
But it seems likely that heuristically picking a multiple of times to run the test produces similar results
I can't speak to 2004, but these days "bisect" is the standard term in my circles (even when we're not actually using git and its bisect command).
It would be interesting to know whether git was the first to associate that word with this activity... especially given it's atrocious naming of everything else :P
Could be useful but parent mentions a megacorp, so maybe it's just some bureaucracy or ball-breaking.
- data dependencies cause regressions, so you. need some way to factor this in - production changes cause regressions - debugging at the source code level can be laborious past a certain point
The way I approached doing this at another (maybe same) T$ compnay was tooling that could take anything observable -- e.g. logs, program traces, signals from services, service definitions, data, stack traces from debuggers for side-by-side running -- convert it to a normal form (e.g. protobuf or JSON) and then diff that to look for regressions.
Stop doing it.
When you're looking for a smoking gun commit, you want it as small as possible, otherwise it'll take longer to fix.
sorta. this really varies strongly from person to person and i wouldn't generalize. but you can construct small commits after you're done with your work.
> contain intermediary trains of thought that aren't relevant
no. delete these, they should not be present in the final history.
> decompose the [...]
i don't know what this is supposed to mean.
If you're unfortunate enough to have an impoverished "linear history", you're stuck figuring out whether it's "bad" or "skip", sorry.
With linear history you squash everything into a single, working commit which is applied to the tip of the shared branch. The rationale is that each change is like a published piece of writing: it will have been through multiple drafts and final versions as well as being edited and peer reviewed, but ultimately the only thing any of your peers care about is the finished work. None of the incomplete, broken, or unreviewed intermediate versions belong in the shared history and they can be thrown away.
Two counter points to this. First, the code review discussion is often recorded forever but in a social tool that’s kept separate from the code itself.
Second, if you end up being as famous for your code as Austen, Thackeray, Shakespeare or Da Vinci were for their literature then your “work in progress” commits and v0 drafts are very valuable and worth keeping. The amount of people this could apply to is not a large number.
An opposite which I could accept is asking people to carefully rebase their drafts, but I see it as a higher effort with a bigger risk of screwing up, with a dose of bikeshedding an additional topic, the commit history: "why do you split in 5 commits when 2 would be enough?"
I guess you can keep the drafts if you don't delete feature branches. But I don't see it as extremely useful, unless it's a very talented individual AND very methodical with his commit history.
In my team, we merge squash our PRs, having a guideline that they should be a small increment. Here's what happrns:
- when you checkout a commit, you are guaranteed to have a version that was reviewed by a person and validated by ci/cd - most commits have chsnegs with substance, instead of "log", "debug", etc
Without squash, a person can push 3 commits to a feature branch, ci/cd says the last commit is OK, it gets merged, and you may get 2 commits that don't compile or cause a very basic runtime error due to some typo or whatever.
(not that it could not be solved with due diligence, but that comes with higher effort too)
How do you assure working commits and avoid noise without either squash or rebase?
I find the exact opposite to be true.
When you merge 20 commits from a branch, you add to the history a bunch of unfinished-state checkpoints, which may not even compile individually, and that may make the search longer than it should. Also, those intermediate commits probably never were deployed as individual units.
In a merge-squashed main branch all commits:
* were reviewed as a single unit, but may have originated from multi-commit branches
* are guaranteed to have passed the test suite
* by definition, are at a ready-to-deploy state, even if they contain feature-flagged components
These are much easier to bisect through. And their changeset shouldn’t be any larger than any regularly-merged branches. It’s the same unit of work, merged differently.
If the PR is too large, then you’re probably lumping too much stuff together, which also leads to slower and worse code review cycles.
(To be fair I think the first time I heard it explicitly from a teacher was Jr high shop class)
Edit: at what age do people usually learn to play 20 questions?
Even if people know / use it intuitively, there's a value to describe it more formally and give it a name.
(BTW sccs was 1972; no doubt it had predecessors. Before disks were large enough to hold multiple versions of a source tree we kept them on tape)
In my circles, it's not ubiquitous even today.
> BTW sccs was 1972
Many projects didn't use a reasonable versioning system until 10 or 20 years ago.
Before decentralized versioning system, this technique was highly impractical - in one SVN project I worked on, checkout of a branch / revision took ~30 minutes.
CVS tracks commit on individual file basis, checking a global state of the project at a particular timestamp wasn't that trivial / necessarily correct.
It’s magical to experience a short but sweet tip and you just _know_ that (programming) life got a bit easier. Good bang for buck blog post! A few minutes well spent.
[1] Yesterday, my program worked. Today, it does not. Why? PDF link: https://www.cs.purdue.edu/homes/xyzhang/spring07/Papers/p253...