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 时，运行器会调用同一个算法，并把最小输入写入失败事件。

找出切换实现的位置

在多个规模上比较两个实现，为每个规模打上标签，并寻找一次干净的转变：

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 当作交叉点。 它不是；偏好发生了翻转。

后续步骤