Luna Flow
日本語

experiment のチュートリアル

このチュートリアルでは、ベンチマークの正しさのためのツールを扱います。許容誤差付きのオラクル、実装間の関係による検査、失敗を小さくするシュリンカー、そしてどのサイズで実装を切り替えるべきかを教えてくれるクロスオーバー分析です。どの例も完全なテストです。

クイックスタート

moon add Luna-Flow/mare_mark@0.3.0
import {
  "Luna-Flow/mare_mark/model",
  "Luna-Flow/mare_mark/experiment",
}
test "is the fast sum right?" {
  let oracle = @experiment.ReferenceOracle::equal(
    "exact-sum",
    (xs : Array[Int]) => xs.fold(init=0, (a, b) => a + b),
    (expected : Int, actual : Int) => expected == actual,
  )
  let input = [1, 2, 3, 4]
  let verdict = @experiment.validate_reference(oracle, input, 0, Value(10), Value(10), "fast-sum", "4")
  inspect(verdict.status is Valid, content="true")
}

日常的な作業

浮動小数点の結果を許容誤差付きで比較する

結合順序を変えた和は、左から右への和と最後の数ビットが異なります。等価性を要求する代わりに相対誤差を受け入れます:

test "relative tolerance" {
  let close = (expected : Double, actual : Double) => {
    (expected - actual).abs() <= 1.0e-12 * expected.abs().max(1.0)
  }
  let oracle = @experiment.ReferenceOracle::equal("sum", (xs : Array[Double]) => xs.fold(init=0.0, (a, b) => a + b), close)
  let xs = [0.1, 0.2, 0.3]
  let pairwise = xs[0] + (xs[1] + xs[2])
  let verdict = @experiment.validate_reference(oracle, xs, 0, Value(0.1 + 0.2 + 0.3), Value(pairwise), "pairwise", "3")
  inspect(verdict.status is Valid, content="true")
}

実装同士を照らし合わせて検査する

信頼できる参照がない場合は、実装同士が一致することを検査します:

test "implementations must agree" {
  let agree : @experiment.RelationalOracle[Int, Int] = @experiment.RelationalOracle::new("agree", (_, _, _, left, _, right) => {
    match (left, right) {
      (Value(a), Value(b)) => if a == b { Valid } else { Invalid("results differ") }
      _ => Invalid("missing result")
    }
  })
  let spec : @experiment.OracleSpec[Int, Int, Int, Unit] = Relational(agree)
  guard spec is Relational(oracle) else { fail("unexpected spec") }
  inspect((oracle.validate_pair)(5, 0, "loop", Value(10), "formula", Value(10)) is Valid, content="true")
}

OracleSpec を @runner.BenchSpec::advanced に渡してください。ランナーは実装のすべてのペアを検査します。

失敗を小さくする

あるリスト関数は、負の数を含むすべてのリストで失敗します。要素を取り除くことで、失敗する入力を縮小します:

test "shrink a list" {
  let shrinker = @experiment.Shrinker::new(
    (xs : Array[Int]) => Array::makei(xs.length(), i => {
      let smaller = xs.copy()
      smaller.remove(i) |> ignore
      smaller
    }),
    xs => xs.length().to_string(),
  )
  let failing = [3, 8, -2, 7, 1]
  let (minimal, _) = @experiment.shrink(failing, shrinker, xs => xs.any(x => x < 0))
  debug_inspect(minimal, content="[-2]")
}

BenchSpec が shrinker を持つ場合、ランナーは同じアルゴリズムを呼び出し、最小入力を失敗イベントに書き込みます。

実装を切り替える位置を見つける

2 つの実装をいくつかのサイズで比較し、各サイズにラベルを付けて、きれいな遷移が 1 つだけあるかを探します:

test "crossover between two algorithms" {
  let sizes = [8, 32, 128, 512, 2048]
  let relative_delta_of_insertion_vs_merge = [-35.0, -12.0, 1.0, 18.0, 60.0]
  let labels = relative_delta_of_insertion_vs_merge.map(r => @experiment.comparator_label(r, 5.0))
  debug_inspect(labels, content="[\"A\", \"A\", \"Unknown\", \"B\", \"B\"]")
  let domain = @experiment.ScaleDomain::new(sizes, (a, b) => a.compare(b), n => n.to_string())
  let result = @experiment.crossover_from_labels(domain, labels)
  inspect(result is NoCrossover(_, _), content="true")
  let sharper = [-35.0, -12.0, -6.0, 18.0, 60.0].map(r => @experiment.comparator_label(r, 5.0))
  guard @experiment.crossover_from_labels(domain, sharper) is Found(boundary, _, _) else { fail("none") }
  inspect(boundary.at_or_above, content="512")
}

最初の系列では A と B の領域の間に Unknown があります。分析はその隙間のどこに境界があるかを推測せず、クロスオーバーなしと報告します。隙間をより細かく計測するか、ポリシーを自分で決めてください。

さらに先へ

  • Found の境界を @model.DeploymentPolicy::Piecewise に変換します。model のチュートリアルを参照してください。
  • ReferenceAndRelational で参照オラクルと関係オラクルを組み合わせます。
  • experiment の設計で、縮小が停止し失敗を保つことを証明しています。

よくある落とし穴

  • ソートされていないスケール。 crossover_from_labels は与えられた順序を使います。
  • 浮動小数点の結果に等価性を使う。 アルゴリズムの誤差上界に合った許容誤差を使ってください。
  • 入力を大きくするシュリンカー。 候補はより小さくなければなりません。そうでないと進展なしに予算を使い果たします。
  • NonMonotonic をクロスオーバーと読む。 そうではありません。優位性が反転しているのです。

次のステップ