Conao3 Notes

Lean 4で時間のかかっている証明とtacticの位置を1コマンドで出すLeanwakeを作った

Lean 4のプロジェクトで、時間のかかっている証明を1コマンドで上から順に出すCLI、Leanwakeを作りました。証明ごとにかかった時間と全体に占める割合に加えて、その証明の中で時間を使っているtacticの位置も出します。

法令の期間と税額の計算をLeanで証明しているlean-ritsuryoで試してみたところ、893コマンドのうち10個の宣言がelaborationの時間の64%を使っていました。その中には、時間の99.9%を24行目の omega が使っている定理もありました。

tacticごとの時間を取る計測は証明そのものを遅くするので、順位と時間はそれを取らずに測り、一覧に載る宣言だけを測り直して内訳を出しています。

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

時間のかかっている証明を出す

Lakeのプロジェクトのディレクトリで list-hotspots を実行します。ここではlean-ritsuryoのコミット d79c7f5 で上位5件を出してみます。

git clone https://github.com/conao3/lean-ritsuryo
cd lean-ritsuryo
git checkout d79c7f5
nix run github:conao3/rust-leanwake -- profile list-hotspots \
  --project-dir . --jobs 4 --limit 5 --output table
61.82 s in 893 commands and 54 files; the 5 listed take 52.7%
Seconds  Share  Location                             Declaration                                           Heartbeats  Inside
   8.84  14.3%  Ritsuryo/Tax/Proofs/Penalty.lean:14  Ritsuryo.Tax.Penalty.pen1_no_return_tiers              118149453  omega 24:59-24:64 x4 99.9%
   7.84  12.7%  Ritsuryo/Tax/Proofs/Income.lean:39   Ritsuryo.Tax.Income.quickCents_bounds                  110910269  split 42:52-42:57 x194 69.6%
   6.13   9.9%  Ritsuryo/Holiday/Check.lean:46       Ritsuryo.Holiday.checkAll                               28404434  decide 50:2-50:16 x1 99.9%
   5.57   9.0%  Ritsuryo/Tax/Inheritance.lean:79     Ritsuryo.Tax.Inheritance.taxCentsSpec_eq_quickCents     64381705  omega 86:12-86:17 x8 95.6%
   4.19   6.8%  Ritsuryo/Tax/Income.lean:68          Ritsuryo.Tax.Income.incomeTaxCentsSpec_eq_quickCents    35550693  omega 76:12-76:17 x7 94.6%

先頭の行は測ったコマンド全体のelaborationにかかった時間で、その下に宣言が時間の長い順に並びます。各行は左から、かかった時間、全体に占める割合、ファイルと行、宣言の名前、heartbeat、宣言の中でいちばん時間を使っているtacticです。

heartbeatはLeanがelaborationの途中で数えている小さなメモリ割り当ての回数で、maxHeartbeatsの上限と同じカウンタです。

ビルド済みのプロジェクトではこの実行に4コアで70秒かかり、cloneした直後からだと依存のビルドを含めて102秒でした。同じプロジェクトの lake build は48秒です。

img

--limit を付けないと上位10件が出ます。この図は別の回の上位10件で、893コマンドのうちこの10個が全体の64%を使っていました。

内訳の読み方

1番目の pen1_no_return_tiers は無申告加算税の額についての定理で、右端に omega 24:59-24:64 x4 99.9% と出ています。

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

これはファイルの24行目の59桁目から64桁目にある omega を指していて、4回動いてこの定理の時間の99.9%を使っています。 <;> で分かれた4つのゴールのそれぞれで omega が動くので4回になります。

2番目の quickCents_bounds では、 repeat' split の split が194回動いて69.6%を使っていました。

theorem quickCents_bounds (x y : Nat) (h : x ≤ y) :
    quickCents x + 5 * (y - x) ≤ quickCents y ∧ quickCents y ≤ quickCents x + 45 * (y - x) := by
  refine ⟨?_, ?_⟩ <;> unfold quickCents <;> repeat' split
  all_goals omega

3番目の checkAll は decide +kernel の1回が99.9%です。tacticを持たない定義や項で書いた証明では、tacticの代わりに addDecl や Meta.whnf のような、Leanの内部の処理の名前が出ます。

既定の出力はJSONで、宣言ごとに時間を使っているtacticをすべて持っているので jq で絞り込めます。

2回に分けて測る理由

img

tacticごとの時間はLeanのtrace.profilerで取るのですが、traceを取ると証明そのものが遅くなります。pen1_no_return_tiers のあるファイルだけを交互に測ってみたところ、traceなしでは8.3〜9.3秒、すべてのtraceを取ると24.0〜24.2秒でした。

そこでLeanwakeは順位と時間をtraceなしの計測から取り、一覧に載る宣言だけをtraceつきで測り直しています。内訳には測り直したときの割合だけを使うので、表の時間にtraceの分は入りません。

内訳の要らないときは --detail none を付けると測り直しを省けて、lean-ritsuryoでは41秒で終わります。

また lean コマンドと言語サーバーは既定でelaborationを複数のスレッドで進めますが、Leanwakeは Elab.async を false にして、証明もそのコマンドの中で同期でelaborateして測っています。

時間とheartbeat

同じコミットで続けて2回実行したところ、合計は65.7秒と61.8秒で、上位4件の並びは変わりましたが、上位5件の顔ぶれは同じでした。かかる時間はマシンの負荷で変わるので、時間と並べて割合を出しています。

heartbeatの順は時間の順と合わず、上の表でも checkAll は2,840万heartbeatで6.13秒かかっていて、6,438万heartbeatの taxCentsSpec_eq_quickCents の5.57秒より長くなっています。なので並べる単位は時間にしました。

変更の前後を比べる

証明を直したあとに速くなったかを確かめるときは、 record-profile で変更の前と後を記録して compare-profiles で比べます。比較にはheartbeatを使います。

img

この図はある定理を2つの条件で8回ずつ記録した値で、同じ4つのコアに負荷をかけると経過時間の平均は10 msから22 msに延びましたが、heartbeatは16回とも113,455でした。なので1回ずつの記録を比べるだけで、宣言ごとの増減が分かります。

たとえば4つの宣言を持つ Demo.lean で、次の定理の simp を simp only に変えてみます。

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

変更の前に base.json 、変更の後に head.json を記録して、2つを比べます。

nix run github:conao3/rust-leanwake -- profile record-profile \
  --project-dir . --output-file base.json
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: 0  Improved: 1  Unchanged: 3  Added: 0  Removed: 0
Heartbeats: 287947 -> 282588; thresholds: > 1000 heartbeats and > 1%
Status	BaseHeartbeats	HeadHeartbeats	DeltaHeartbeats	Path	Key
improved	39416	34153	-5263	Demo.lean	length_append_swap

この定理のheartbeatは39,416から34,153に13%減りました。simp は @[simp] の付いた補題も使いますが、 simp only は挙げた補題だけを使うので、heartbeatが減っています。

速くなった、遅くなったと判定するのは、差が1,000 heartbeatと1%の両方を超えたコマンドです。実際のプロジェクトでは同じコミットを2回記録しても一部のコマンドのheartbeatが少し動きます。lean-ritsuryoでは893コマンドのうち19個に最大31の差があったので、しきい値はこの差より大きく取ってあります。

遅くなった宣言があると終了コードが254になるのでCIにも組み込めて、ワークフローの例はREADMEにあります。

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つ以上あるときだけです。

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

確かめられないこと

内訳の割合は回によって動き、 quickCents_bounds の split は4回の実行で69.6%から82.6%でした。

測る単位はトップレベルのコマンドなので、複数の宣言を定義するコマンドはまとめて1つの値になります。対応しているのはLean 4.35.0で、Mathlibでは測っていません。

宣言とtacticの時間はlean-source-profilerとleanprofでも測れて、Lakeのビルドのジョブごとの時間はlakeprofで測れます。Lean本体とMathlibはコミットごとの性能をRadarで計測しています。