Conao3 Notes

Lean 4の証明を15%遅くした1行をCIで検出するLeanwakeを作った

Lean 4のプロジェクトで、宣言ごとのelaborationのコストを記録して比べるCLI、Leanwakeを作りました。変更の前と後でそれぞれ記録を取って比べ、遅くなった宣言があれば終了コード254で終わります。

コストの単位には、Leanがelaborationの途中で数えているheartbeatを使っています。たとえばある定理の証明で simp only を simp に変える1行の変更では、heartbeatが34,153から39,416に15%増えて、Leanwakeはこの定理を遅くなったと判定しました。

simp only は挙げた補題だけを使いますが、 simp は @[simp] の付いた補題も使うので、heartbeatが増えています。

試しに別の定理を、マシンに負荷をかけないときとかけたときに8回ずつ記録してみたところ、経過時間の平均は11 msから36 msに延びたのに、heartbeatは16回とも113,455でした。なのでほかのジョブと計算機を分け合うCIでも、1回ずつの記録を比べて宣言ごとの増加を検出できます。

リポジトリはconao3/rust-leanwakeで、ライセンスはApache-2.0です。この記事の結果はLean 4.35.0とLeanwake 0.1.0で動かしたものです。

遅くなった宣言の検出

次の Demo.lean を持つLakeのプロジェクトで試してみます。

def sumTo : Nat → Nat
  | 0 => 0
  | n + 1 => n + 1 + sumTo n

theorem sumTo_hundred : sumTo 100 = 5050 := by
  decide

theorem length_append_swap (xs ys : List Nat) :
    (xs ++ ys).length = (ys ++ xs).length := by
  simp only [List.length_append, Nat.add_comm]

theorem two_mul_le (a b : Nat) (h : a ≤ b) : 2 * a ≤ 2 * b := by
  omega

record-profile でプロジェクトのファイルをelaborateしてコマンドごとのheartbeatをJSONに記録し、 list-commands でその記録をheartbeatの多い順に並べます。

nix run github:conao3/rust-leanwake -- profile record-profile \
  --project-dir . --output-file base.json
nix run github:conao3/rust-leanwake -- profile list-commands \
  --profile file://base.json --output table | column -t
Heartbeats  ElapsedNs  Path       Key                 HasErrors
113455      10222978   Demo.lean  two_mul_le          false
78802       9144612    Demo.lean  sumTo_hundred       false
56178       70466931   Demo.lean  sumTo               false
34153       3484413    Demo.lean  length_append_swap  false

次に、 length_append_swap の simp only を simp に変えてみます。

-  simp only [List.length_append, Nat.add_comm]
+  simp [Nat.add_comm]

変更後の記録を取って compare-profiles で2つを比べます。

nix run github:conao3/rust-leanwake -- profile record-profile \
  --project-dir . --output-file head.json
nix run github:conao3/rust-leanwake -- profile compare-profiles \
  --base-profile file://base.json --head-profile file://head.json \
  --output table
Regressed: 1  Improved: 0  Unchanged: 3  Added: 0  Removed: 0
Heartbeats: 282588 -> 287947; thresholds: > 1000 heartbeats and > 1%
Status	BaseHeartbeats	HeadHeartbeats	DeltaHeartbeats	Path	Key
regressed	34153	39416	5263	Demo.lean	length_append_swap

length_append_swap のheartbeatは34,153から39,416に15%増えていて、終了コードは254になるので、CIのジョブはここで失敗します。ちなみにこの定理のelaborationにかかった時間は、変更前が3.5 ms、変更後が4.1 msでした。

コマンドはファイルのパスと宣言の名前の組で突き合わせていて、片方の記録にしかないコマンドは追加または削除として数えます。遅くなったと判定するのは増分が1,000 heartbeatと1%の両方を超えたコマンドで、このしきい値は --absolute-threshold-heartbeats と --relative-threshold-percent で変えられます。

heartbeatで測る理由

heartbeatはLeanがelaborationの途中で数えている小さなメモリ割り当ての回数で、maxHeartbeatsの上限と同じカウンタです (上限の1単位が1,000 heartbeatにあたります)。

img

この図は先ほどの two_mul_le を2つの条件で8回ずつ記録した値です。前半の8回はLeanwakeを4つのコアに固定しただけで、後半の8回では同じ4つのコアで計算を続けるプロセスを4つ動かしてみたところ、経過時間は前半が10.3〜12.9 ms、後半が21.1〜56.5 msになりました。それでもheartbeatは16回とも113,455で変わりません。経過時間で1%の増加を判定しようとすると測定を繰り返して平均を取ることになりますが、heartbeatなら1回の記録で比べられます。

lean コマンドと言語サーバーは既定でelaborationを複数のスレッドで進めるのですが、heartbeatはスレッドごとに数えるので、別のスレッドに回った証明の分はコマンドの値に入りません。たとえば (List.range 1200).length = 1200 を decide +kernel で示す定理は、Leanwakeの記録では475,283 heartbeatですが、同じ定理をLeanのAPIで非同期のまま測ると6,084 heartbeatでした。そこでLeanwakeは Elab.async を false にして、すべてのコマンドを同期でelaborateしています。

ただ実際のプロジェクトでは、同じコミットを2回記録しても一部のコマンドのheartbeatが一致しません。法令の期間と税額の計算をLeanで証明しているlean-ritsuryoは、54ファイル、893コマンドで合計6億5,380万heartbeatあり、これを2回記録すると13コマンドに差があって、差の最大は8 heartbeatでした。leanassayの全ファイルでは差の最大が183です。ほかの宣言を変えたときにも値は少し動き、先ほどの例でも変えていない two_mul_le が113,455から113,551になっていました。既定のしきい値の1,000 heartbeatと1%はこれらの差より大きく取ってあるので、lean-ritsuryoの2回の記録を比べると、893コマンドとも変わらないと判定されます。

heartbeatの多い宣言と内訳

lean-ritsuryoを記録して、heartbeatの多いコマンドを5つ並べてみます。

leanwake profile record-profile --project-dir . --jobs 4 \
  --output-file profile.json
leanwake profile list-commands --profile file://profile.json \
  --limit 5 --output table | column -t
Heartbeats  ElapsedNs   Path                              Key                                                   HasErrors
118149453   8771076702  Ritsuryo/Tax/Proofs/Penalty.lean  Ritsuryo.Tax.Penalty.pen1_no_return_tiers             false
110910269   6867599166  Ritsuryo/Tax/Proofs/Income.lean   Ritsuryo.Tax.Income.quickCents_bounds                 false
64381709    6738770487  Ritsuryo/Tax/Inheritance.lean     Ritsuryo.Tax.Inheritance.taxCentsSpec_eq_quickCents   false
35550697    3996662401  Ritsuryo/Tax/Income.lean          Ritsuryo.Tax.Income.incomeTaxCentsSpec_eq_quickCents  false
28404434    7752174727  Ritsuryo/Holiday/Check.lean       Ritsuryo.Holiday.checkAll                             false

893コマンドのうち、上位3つの定理だけで全体のheartbeatの45%を占めています。記録にかかった時間は、ビルド済みのプロジェクトなら4コアで43〜45秒、ビルド前の状態からだと依存のビルドを含めて88秒で、同じプロジェクトの lake build は48秒でした。

heartbeatがいちばん多い pen1_no_return_tiers は、無申告加算税の額についての次の定理です。

theorem pen1_no_return_tiers (rate tax tax' prior : Nat) (hr : rate = 10 ∨ rate = 15) :
    (tax + prior ≤ 3000000 → noReturnCents rate tax prior = noReturnCentsArt2 rate tax prior) ∧
      (tax ≤ tax' → noReturnCents rate tax prior ≤ noReturnCents rate tax' prior) := by
  unfold noReturnCents noReturnCentsArt2 tieredCents
  rcases hr with rfl | rfl <;> constructor <;> intro h <;> omega

--detail steps を付けるとコマンドの中の内訳も記録するので、 list-steps でこの定理の内訳から omega の行を取り出してみます。

leanwake profile record-profile --project-dir . \
  --paths Ritsuryo/Tax/Proofs/Penalty.lean --detail steps \
  --output-file steps.json
leanwake profile list-steps --profile file://steps.json \
  --path Ritsuryo/Tax/Proofs/Penalty.lean \
  --key Ritsuryo.Tax.Penalty.pen1_no_return_tiers --output table \
  | grep -e Heartbeats -e Tactic.omega | column -t
Heartbeats  Depth  Range        Class            Kind
54184655    20     24:59-24:64  Leanwake.tactic  Lean.Parser.Tactic.omega
54100320    20     24:59-24:64  Leanwake.tactic  Lean.Parser.Tactic.omega
25736830    20     24:59-24:64  Leanwake.tactic  Lean.Parser.Tactic.omega
25574245    20     24:59-24:64  Leanwake.tactic  Lean.Parser.Tactic.omega

24:59-24:64 はファイルの24行目にある omega の位置で、 <;> で分かれた4つのゴールのそれぞれで omega が動いています。2つは約5,400万heartbeat、残りの2つは約2,600万heartbeatで、4つを合わせるとこの定理のheartbeatの99.9%になりました。

なお内訳つきの記録はtraceを取る分だけheartbeatが増え、この定理では1億1,815万が1億5,970万になりました。そのため compare-profiles は、内訳の有無が同じ記録どうしだけを比べるようにしています。

構成

img

LeanwakeはRustで書いたhostとLeanで書いたadapterの2つでできています。hostがLakeに尋ねて対象のファイルを列挙し、ファイルごとにadapterのプロセスを起動すると、adapterは import を読み込んで、コマンドを1つずつelaborateしながらその前後でheartbeatのカウンタを読みます。

記録にはLeanのバージョン、同期か非同期か、内訳の有無も書き込んでおき、この条件が違う2つの記録を渡すと、 compare-profiles は違う項目を示してエラーで終わります。

Leanで証明した比較の規則

遅くなったかどうかは次のLeanの定義で判定していて、ここでは classify_regressed などの補題とほかの定理は省いています。

def grows (base head absolute relative : Nat) : Bool :=
  decide (absolute < head - base ∧ base * relative < (head - base) * 100)

def classify (base head absolute relative : Nat) : Status :=
  if grows base head absolute relative then .regressed
  else if grows head base absolute relative then .improved
  else .unchanged

theorem equal_unchanged (b a r : Nat) : classify b b a r = .unchanged := by
  simp [classify, grows]

theorem regression_monotone {b h h' a r : Nat}
    (hyp : classify b h a r = .regressed) (increase : h ≤ h') :
    classify b h' a r = .regressed := by
  rw [classify_regressed] at hyp ⊢
  simp only [grows, decide_eq_true_eq] at hyp ⊢
  have mul := Nat.mul_le_mul_right 100 (Nat.sub_le_sub_right increase b)
  omega

regression_monotone は、遅くなったと判定された組なら、変更後の値がそれより大きくても遅くなったと判定されることを示しています。ほかにも次の性質を証明しました。

  • 変更前と変更後を入れ替えると、遅くなったと速くなったが入れ替わります。
  • しきい値を上げても、遅くなったと判定される組は増えません。
  • 突き合わせの結果には、変更前と変更後の各コマンドがちょうど1回ずつ現れます。
  • 比較が失敗するのは、遅くなったコマンドが1つ以上あるときだけです。

定理は全部で18件あり、このコードはRustのソースの leanfran::lean! の中に書いています。ビルドのときにLeanが証明を検査してleanfranがRustの関数にするので、hostはJSONを読んでこの関数に渡し、結果を表示するだけです。

CIでの使い方

pull requestのワークフローで、変更前と変更後のコミットをそれぞれ記録して比べます。

name: Elaboration costs
on:
  pull_request:
permissions:
  contents: read
jobs:
  profile:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v7.0.1
        with:
          ref: ${{ github.event.pull_request.base.sha }}
          path: base
      - uses: actions/checkout@v7.0.1
        with:
          ref: ${{ github.event.pull_request.head.sha }}
          path: head
      - uses: cachix/install-nix-action@v31.11.5
      - run: nix build github:conao3/rust-leanwake --out-link leanwake
      - run: >-
          ./leanwake/bin/leanwake profile record-profile
          --project-dir base --jobs 2 --output-file base.json
      - run: >-
          ./leanwake/bin/leanwake profile record-profile
          --project-dir head --jobs 2 --output-file head.json
      - run: >-
          ./leanwake/bin/leanwake profile compare-profiles
          --base-profile file://base.json --head-profile file://head.json
          --output table

Nixのパッケージにはadapterと対応するLeanとLakeが入っていて、エラーのあるファイルも記録に入りますが、その場合の record-profile は終了コード254で終わります。

確かめられないこと

heartbeatは時間の代わりにはならず、lean-ritsuryoの quickCents_bounds は1億1,091万heartbeatで6.9秒なのに、2,840万heartbeatの checkAll はelaborationに7.8秒かかりました。checkAll は decide +kernel でカーネルに表を評価させる定理です。

測る単位はトップレベルのコマンドなので、複数の宣言を定義するコマンドはまとめて1つの値になります。対応しているのはLean 4.35.0で、Leanのバージョンが違う記録どうしは比べられませんし、Mathlibでは測っていません。

宣言ごとのheartbeatを記録して比べるツールにはleanprofもあり、Lakeのビルドのジョブごとの時間はlakeprofで測れます。Lean本体とMathlibはコミットごとの性能をRadarで計測しています。