MoonBench（月衡）

MoonBench（月衡）是一个面向 MoonBit 开源生态的 benchmark 工具库，提供纳秒级计时、统计分析、性能回归对比、算法复杂度基准，以及一个开箱即用的静态 Web Dashboard。

适用场景：算法库性能验证 · CI 回归防护 · 教学代码耗时演示 · 数据结构对比基准

核心能力

模块	功能
`Duration` / `Stopwatch`	纳秒级时长类型、确定性秒表，支持跨后端移植和测试注入
`Samples` / `Stats`	多次样本存储 + min/max/mean/median/p95/p99/stddev/MAD/RSD 统计
`BenchmarkRunner`	注册 `() -> Unit` 工作负载，自动 warmup / measure / batch 执行
`CalibrationPolicy`	probe 自动选 batch size，防止短 workload 被计时噪声淹没
`BenchmarkLifecycle`	suite / case / measurement 三层 hooks（setup / teardown / before / after）
`Comparison` / `RegressionRule`	baseline 与 candidate 对比，输出 pass / warn / fail CI gate
`TrendReport`	多次运行的趋势分析，识别 improved / regressed / flat
`BenchmarkArtifact`	输出 Markdown / CSV / JSON 发布产物
`algo/`	17 个经典 CS 算法实现，通过 monotonic 后端真实测量（warmup=5 / measure=20），附理论时空复杂度标注
Web Dashboard	纯静态 UI：suite health、均值图、样本曲线、算法复杂度徽章，中英双语

算法复杂度基准（`algo/` 包）

内置 17 个经典算法的 MoonBit 实现。algo_benchmark_runner() 将每个 bench_* 工作负载注册为可测量任务，run() 使用 monotonic 后端在真实时钟下对每个算法 执行 warmup 5 次、测量 20 次（不是回放写死的耗时），输出含 algo_meta 的 JSON，Web UI 按类别分组展示彩色复杂度徽章。

类别	算法	时间	空间
排序	冒泡排序 / 插入排序	O(n²)	O(1)
排序	快速排序 / 归并排序 / 堆排序	O(n log n)	O(log n)~O(n)
搜索	线性搜索	O(n)	O(1)
搜索	二分搜索	O(log n)	O(1)
字符串	朴素匹配	O(nm)	O(1)
字符串	KMP	O(n+m)	O(m)
图	BFS / DFS	O(V+E)	O(V)
图	Dijkstra	O(V²)	O(V)
动态规划	Fibonacci 迭代 / memoized	O(n)	O(1) / O(n)
动态规划	LCS	O(mn)	O(mn)
数值	向量点积	O(n)	O(1)
数值	矩阵乘	O(n³)	O(n²)

安装与接入

作为依赖加入你自己的 MoonBit 项目：

# 从 mooncakes.io 拉取（发布后）
moon add chengyanli/moonbench

# 或直接依赖本仓库某个版本
moon add chengyanli/moonbench@0.1.0

在需要使用的 包目录 的 moon.pkg（旧格式 moon.pkg.json）里声明 import，并起一个别名：

import {
  "chengyanli/moonbench/src" @bench,
  "chengyanli/moonbench/algo"
}

然后即可在代码里通过别名调用：

let suite = @bench.BenchmarkRunner::new("my suite")
  .add("my/workload", fn() { /* ... */ })
  .run()
println(suite.to_report().render_markdown())

// 复用内置的 17 个算法基准
let algo = @algo.algo_smoke_suite()

src 是统计 / Runner / 回归 / 报告核心库；algo 是可选的经典算法基准包。只需要计时与统计时，import src 一个包即可。

快速开始（本仓库）

moon check --target all
moon test --target all
moon run cli          # 真实测量 + 回归 gate（healthy 退出码 0）
moon run cli -- --demo-regression   # 注入退化，gate 判定失败并以非 0 退出码退出
moon run webui        # 运行算法 benchmark 并输出 JSON

本地预览 Web Dashboard：

python3 -m http.server 4173 --directory webui
# 访问 http://127.0.0.1:4173/

使用示例

基础：Samples + BenchmarkSuite

let baseline = Samples::new("baseline")
  .add(Duration::from_micros(120L))
  .add(Duration::from_micros(118L))

let candidate = Samples::new("candidate")
  .add(Duration::from_micros(92L))
  .add(Duration::from_micros(90L))

let suite = BenchmarkSuite::new("demo")
  .with_config(BenchmarkConfig::default().with_measure_runs(4))
  .add_samples(baseline)
  .add_samples(candidate)
  .finish()

println(suite.to_report().render_markdown())

Runner：注册真实工作负载

let suite = BenchmarkRunner::new("my suite")
  .with_config(BenchmarkConfig::default().with_warmup_runs(3).with_measure_runs(10))
  .add_task(BenchmarkTask::new("array/sort/int-10k", fn() {
    // 你的 MoonBit 工作负载
  }).with_batch_size(32))
  .run()

println(suite.to_report().render_markdown())

run() 使用 monotonic backend 真实计时；测试场景可用 MeasurementBackend::scripted 注入确定性耗时。

全链路：Runner + Gate + Artifact

let result = BenchmarkWorkflow::new("run-001", "candidate", runner)
  .with_backend(MeasurementBackend::monotonic())
  .with_gate_policy(GatePolicy::default())
  .run()

println(result.artifact().render_markdown())

性能回归闭环（CI 可失败）

cli/main.mbt 演示了一个真实的回归 gate：先用 monotonic 后端测量 baseline 与 candidate，再按名字配对比较，超过预算就以非 0 退出码退出，从而让 CI 直接失败。

let baseline = HistoricalRun::from_suite("baseline", "baseline", baseline_runner.run())
let candidate = HistoricalRun::from_suite("candidate", "candidate", candidate_runner.run())

let policy = GatePolicy::new(0, 0, RegressionRule::new(100.0)) // warn > 50%, fail > 100%
let gate = policy.check_history(
  candidate.compare_against(baseline, policy.regression_rule().warning_slowdown_percent()),
)
if !gate.passed() {
  abort(gate.summary()) // 非 0 退出码 → CI 失败
}

moon run cli                      # PASS，退出码 0
moon run cli -- --demo-regression # 把 candidate 换成 O(n²) 冒泡排序 → FAIL，退出码非 0

阈值（warn > 50% / fail > 100%）远高于实测的同代码噪声（≤ ~30%），却远低于真实算法退化（quicksort → bubble 慢 30 倍以上），因此 gate 在 CI 中稳定不误报，同时能抓住真实回归。

项目结构

moonbench/
  src/                     ← 核心库（统计、Runner、回归、报告等）
    algo_meta.mbt          ← ComplexityTag 枚举 + benchmark 名称→复杂度映射
    model.mbt              ← 19 种 benchmark 模型（13 通用 + 6 algo）
    web_data.mbt           ← render_web_json（含 algo_meta 字段）
    ...
  algo/                    ← 算法复杂度基准包
    sort.mbt               ← 冒泡 / 插入 / 快速 / 归并 / 堆排序
    search.mbt             ← 线性 / 二分搜索
    string_match.mbt       ← 朴素 / KMP
    graph.mbt              ← BFS / DFS / Dijkstra
    dp.mbt                 ← Fibonacci × 2 / LCS
    numeric.mbt            ← 点积 / 矩阵乘
    suite.mbt              ← algo_benchmark_runner / algo_smoke_suite（真实测量 warmup=5, measure=20）
  webui/                   ← 静态 Dashboard
    index.html / app.js / styles.css
    main.mbt               ← 运行算法 benchmark 并输出 JSON
  cli/                     ← CLI 入口（真实测量 + 性能回归 gate）
  deploy/                  ← Nginx + Dockerfile
  docs/                    ← 设计文档、部署指南、申报书