TT Lab
はじめる
学ぶ 学習パス コース

デバッグ実戦

いつから壊れたか — 64版を6回で絞る

TT Labで続きを見る

目標

良い・悪い・判定不能を判定する機械の判定器を作り、それでビルド履歴64個と入力データ4096行を、それぞれ半分ずつ切って境界を探します。判定不能を避けて通る道と、境界を全数で検証する道まで付け、逐次探索だったら何回だったかも一緒に記録します。

なぜ重要なのか

「先週までは動いたんですが」と「昨日のファイルでだけ落ちるんです」は、同じ形の問題です。境界が1つあり、前後で分かれます。先頭から1つずつ見ると64回と4096回ですが、半分ずつ切れば6回と12回です。 この差を生むのはツールではなく判定器です。人が画面を見て判断する手順が混ざると、10回も繰り返せず、5回目あたりで自分がどちらを良いと言ったのか忘れます。 難しいのは、半分に切るコードではなく境界条件です。起動しないビルドを悪と数えると犯人が手前へ押され、断片からヘッダー行を外すとすべての断片が失敗して1行目を指し、途中で直ってまた壊れた履歴では、答え自体が間違います。 採点ツールは、提出された文面を信じません。採点ツールが作った履歴とデータを一時ディレクトリに用意し、あなたのツールを実際に実行して、境界が合っているかと、何回で見つけたかを一緒に測ります。境界は実行するたびに別の位置にあるので、値を暗記して入れることはできません。

ステップ

  1. /root/bisect/gen_history.pyを作成して実行し、ビルド履歴64個と、/root/bisect/ref.csv、/root/bisect/rows.csv、/root/bisect/loader.pyを作ってください。
  2. /root/bisect/judge.pyを作成して、ビルド1つをgood・bad・unknownに判定させてください。終了コードはそれぞれ0、1、125です。
  3. /root/bisect/bisect_run.pyで履歴を半分ずつ切り、最初に悪くなったビルドを探して、/root/bisect/bisect_result.jsonに残してください。候補63個は6回で終わります。
  4. bisect_run.pyが判定不能に出会ったら、隣のビルドへずれてもう一度尋ねるようにし、区間がまるごと判定不能なら、1つのビルドを指名しないようにしてください。
  5. /root/bisect/row_bisect.pyで、ローダーを落とす行を探して、/root/bisect/row_result.jsonに残してください。断片には、ヘッダー行を必ず付けます。
  6. /root/bisect/probe_count.jsonに、逐次探索と二分探索の最悪の回数、そして実際にかかった回数を並べて書いてください。
  7. /root/bisect/verify_bisect.pyで境界を全数検証し、/root/bisect/verify_result.jsonを作ってください。単調でない履歴に出会ったら、反例を名前で書く必要があります。
  8. /root/bisect/summary.jsonを作り、/root/bisect/bisect_report.mdに4つの節で報告してください。

参考

ビルド履歴と新しい入力を手に入れる

/root/bisect/gen_history.pyを作成して実行し、ビルド履歴64個(/root/bisect/hist/r00からr63まで)と、/root/bisect/ref.csv(300行)、/root/bisect/rows.csv(4096行)、/root/bisect/loader.pyを作ってください。

現場で手に入れるのはコードではなくデータです。このスクリプトをそのまま保存して実行すれば構いません。最後の行に出るexpectの値(ref.csvの正しい合計)は、後のステップで使い続けるので、控えておいてください。

良いと悪いを機械に判定させる

/root/bisect/judge.pyを作成して、ビルド1つをgood・bad・unknownのいずれか1語で判定させてください。終了コードはそれぞれ0・1・125で、起動しないビルドは悪ではなく判定不能です。

判定器は、そのビルドのpipeline.pyを実際に実行して、totalの値を期待値と比べるプログラムです。3つの分岐をはっきりさせてください。動いて値が合えばgood、動くのに値が違えばbad、そもそも動かないかtotalが見つからなければunknownです。125は、git bisect runがスキップとして読む値です。

履歴を半分ずつ切って境界を探す

/root/bisect/bisect_run.pyで最初に悪くなったビルドを探してください。結果は、/root/bisect/bisect_result.jsonに残してください。first_bad・last_good・probe_count・probes・undecidedを含める必要があり、候補63個に対して60回を超えて尋ねているなら、それは二分探索ではありません。

既知の良い位置loと既知の悪い位置hiを置き、間が1つになるまで真ん中を尋ねて、片側を引き寄せます。両端を先に確認して初めて、前提が成り立つかがわかります。尋ねたビルド名を順に集めておけば、probesとprobe_countがそのまま出ます。

起動しないビルドを避けて通る

bisect_run.pyが判定不能に出会ったら、隣のビルドへ1つずつずれて、もう一度尋ねるようにし、ずれたビルドの名前をundecidedに集めてください。区間がまるごと判定不能なら、1つのビルドを指名せず、last_goodとfirst_badで残りの区間を報告する必要があります。

判定不能を悪に丸めると、境界が手前へ押されて、無実のビルドが犯人になります。真ん中が判定不能なら、その位置をあきらめて、mid-1、mid+1、mid-2のように左右へ1つずつ広げながら、判定できる隣を探します。区間の中に判定できるビルドが1つもなければ、その区間が答えです。絞り込んだことも成果です。

ローダーを落とす行を探す

/root/bisect/row_bisect.pyで、/root/bisect/rows.csvのどの行がローダーを止めるのかを探し、/root/bisect/row_result.jsonにbad_row・probe_count・rowsとして残してください。bad_rowは、ヘッダー行を除いた、1から数える行番号です。

履歴と原理は同じです。先頭からm行までだけを入れた断片を作ってローダーに食わせ、失敗したら犯人はその中にいます。断片には、ヘッダー行を必ず付けてください。外すと、後ろの断片が最初のデータ行を列名として読んで、すべての断片が失敗します。4096行なら、12回で十分です。

何回で終わったかを数える

/root/bisect/probe_count.jsonに、history・rows・millionの3項目を書いてください。各項目はcandidates・sequential_worst・bisect_worstを含み、historyとrowsは、実際にかかった回数measuredも含みます。millionのcandidatesは1000000です。

逐次探索の最悪は候補数そのままで、二分探索の最悪はlog2(候補数)を切り上げた値です。履歴の候補数は、ビルド数から1を引いた値です。最初のビルドは良いと見なして始めるからです。measuredは、前のステップが残したJSONのprobe_countをそのまま持ってきます。

境界が本当に境界かを全数で確認する

/root/bisect/verify_bisect.pyで境界の前後を全数調査し、/root/bisect/verify_result.jsonにboundary_bad・prev_good・monotone・contradictions・checkedを残してください。境界の後ろに良いビルドがあるか、境界の前に悪いビルドがあれば、その名前をcontradictionsに書く必要があります。

探索は対数ですが、検証は線形です。すべてのビルドを1回ずつ実行してgood・bad・unknownを付け、境界の後ろのgoodと境界の前のbadを集めれば、それが単調が崩れている証拠です。判定不能は反例ではありません。別に数えます。

2つの境界を1枚で報告する

/root/bisect/summary.jsonにrevisions・first_bad・last_good・unknown・history_probes・rows・bad_row・row_probes・sequential_total・bisect_totalを書き、/root/bisect/bisect_report.mdに## 무엇이 깨졌나、## 어떻게 좁혔나、## 몇 번 만에、## 남은 위험(韓国語の見出しは、順に「何が壊れたか」「どう絞り込んだか」「何回で」「残るリスク」という意味です)の4つの節で報告してください。

sequential_totalは2つの逐次探索の最悪の合計で、bisect_totalは実際にかかった2つの回数の合計です。報告書には、最初に悪くなったビルドの名前と犯人の行番号、そして2つの数字の両方を書いてください。顧客が買うのは結論ではなく手順です。