TT Lab
Get started
Learn Learning paths Courses

Debugging in Practice

When did it break — narrowing 64 builds in six probes

Continue in TT Lab

Goal

You build a machine judge that separates good, bad, and cannot judge, and use it to find the boundary by halving a build history of 64 builds and an input data set of 4096 rows. You also add a way to step aside from cannot-judge and a way to verify the boundary exhaustively, and record how many probes a sequential search would have taken.

Why it matters

"It worked until last week" and "it only dies on yesterday's file" are problems of the same shape. There is one boundary, and the front and back differ. Looking one by one from the front takes 64 and 4096 probes, but halving takes six and twelve. What makes this difference is not a tool but the judge. If a procedure where a person looks at the screen and decides gets mixed in, you cannot repeat it ten times, and by about the fifth you forget which side you called good. The hard part is not the code that cuts in half but the boundary conditions. If you count a build that does not start as bad, the culprit is pushed forward; if you strip the header from a chunk, every chunk fails and points to row 1; and on a history that was fixed midway and broke again, the answer itself is wrong. The grader does not trust your wording. It sets up the history and data it built in a temporary directory, actually runs your tools, and measures both whether the boundary is right and how many probes it took. The boundary is at a different place each run, so you cannot memorize the value and plug it in.

Steps

  1. Create and run /root/bisect/gen_history.py to create the 64-build history along with /root/bisect/ref.csv, /root/bisect/rows.csv, and /root/bisect/loader.py.
  2. Create /root/bisect/judge.py so that it classifies a build as good, bad, or unknown. The exit codes are 0, 1, and 125 respectively.
  3. Use /root/bisect/bisect_run.py to halve the history, find the first build that went bad, and leave it in /root/bisect/bisect_result.json. With 63 candidates, it ends in six probes.
  4. Make bisect_run.py step aside to a neighboring build and ask again when it meets cannot-judge, and make it not point at a single build if the whole interval cannot be judged.
  5. Use /root/bisect/row_bisect.py to find the row that kills the loader and leave it in /root/bisect/row_result.json. Always attach the header to chunks.
  6. In /root/bisect/probe_count.json, write side by side the worst-case counts of sequential search and binary search, and the count actually used.
  7. Use /root/bisect/verify_bisect.py to verify the boundary exhaustively and create /root/bisect/verify_result.json. If you meet a non-monotonic history, you must write the counterexample by name.
  8. Report in /root/bisect/summary.json and /root/bisect/bisect_report.md in four sections.

Notes

Get the build history and the new input in hand

Create and run /root/bisect/gen_history.py to create a 64-build history (/root/bisect/hist/r00 through r63) along with /root/bisect/ref.csv (300 rows), /root/bisect/rows.csv (4096 rows), and /root/bisect/loader.py.

What you hold in your hands in the field is not code but data. Just save this script as it is and run it. The expect value that appears on the last line (the correct total for ref.csv) is used throughout the later steps, so write it down.

Make a machine tell good from bad

Create /root/bisect/judge.py so that it judges one build with one word among good, bad, and unknown. The exit codes are 0, 1, and 125 respectively, and a build that does not start is not bad but cannot-judge.

The judge is a program that actually runs that build's pipeline.py and compares the total value with the expected value. Make the three branches clear — if it runs and the value is right, it is good; if it runs but the value differs, it is bad; if it cannot run at all or no total can be found, it is unknown. 125 is the value git bisect run reads as skip.

Halve the history to find the boundary

Use /root/bisect/bisect_run.py to find the first build that went bad and leave the result in /root/bisect/bisect_result.json. It must contain first_bad, last_good, probe_count, probes, and undecided, and if you ask about 63 candidates more than 60 times, that is not binary search.

Keep a known good position lo and a known bad position hi, and ask about the middle, pulling one side in, until only one step remains between them. You must check both ends first to know whether the premise holds. If you collect the names of the builds you asked about in order, probes and probe_count come out for free.

Step aside from builds that do not start

Make bisect_run.py step aside to a neighboring build one step at a time and ask again when it meets cannot-judge, and collect the names of the builds it stepped aside from in undecided. If the whole interval cannot be judged, do not point at a single build; you must report the remaining interval with last_good and first_bad.

If you fold cannot-judge into bad, the boundary is pushed forward and an innocent build becomes the culprit. If the middle cannot be judged, give up that position and widen one step at a time to the left and right, as in mid-1, mid+1, mid-2, looking for a neighbor that can be judged. If there is not a single judgeable build in the interval, that interval is the answer — having narrowed it is also a result.

Find the row that kills the loader

Use /root/bisect/row_bisect.py to find which row of /root/bisect/rows.csv stops the loader, and leave it in /root/bisect/row_result.json as bad_row, probe_count, and rows. bad_row is the row number counted from 1, excluding the header.

The principle is the same as for the history. Make a chunk containing only the first m rows, feed it to the loader, and if it fails, the culprit is inside. Always attach the header to chunks — if you strip it, the latter chunk reads the first data row as column names and every chunk fails. With 4096 rows, twelve probes are enough.

Count how many probes it took

In /root/bisect/probe_count.json, write three items: history, rows, and million. Each item contains candidates, sequential_worst, and bisect_worst, and history and rows also contain measured, the count actually used. The candidates of million is 1000000.

The worst case of sequential search is the number of candidates as is, and the worst case of binary search is log2(number of candidates) rounded up. The number of candidates for the history is the number of builds minus one — because you start by assuming the first build is good. For measured, take the probe_count of the JSON left by the earlier step as is.

Verify exhaustively that the boundary really is a boundary

Use /root/bisect/verify_bisect.py to examine everything before and after the boundary exhaustively and leave boundary_bad, prev_good, monotone, contradictions, and checked in /root/bisect/verify_result.json. If there is a good build after the boundary or a bad build before it, you must write its name in contradictions.

The search is logarithmic, but verification is linear. Run every build once and label it good, bad, or unknown, and if you collect the goods after the boundary and the bads before the boundary, that is the evidence that monotonicity is broken. Cannot-judge is not a counterexample — count it separately.

Report the two boundaries on one page

In /root/bisect/summary.json, write revisions, first_bad, last_good, unknown, history_probes, rows, bad_row, row_probes, sequential_total, and bisect_total, and in /root/bisect/bisect_report.md, report in four sections: ## 무엇이 깨졌나 ## 어떻게 좁혔나 ## 몇 번 만에 ## 남은 위험 (in order, these mean: what broke, how it was narrowed, in how many probes, and the remaining risk).

sequential_total is the sum of the two sequential worst cases, and bisect_total is the sum of the two counts actually used. In the report, write the name of the first build that went bad and the culprit row number, along with both numbers. What the customer buys is not the conclusion but the procedure.