Source tools/benchmark_estimator_variance.py
#!/usr/bin/env python3"""Measure estimator variance and sampling time with the compiled Lean runtime.Build with `cd lean && lake build sampling-bench`, then run this script withPython and matplotlib. Use --resume after interruption or --plot-only toregenerate summaries and figures from the saved per-replicate measurements."""from __future__ import annotationsimport argparsefrom collections import defaultdictimport csvfrom datetime import datetime, timezoneimport hashlibimport jsonimport mathfrom pathlib import Pathimport platformimport statisticsimport structimport subprocessimport sysROOT = Path(__file__).resolve().parents[1]MODELS = ("branching", "hmm", "load")SIZES = (1000, 3000, 10000, 30000, 100000)def sha256(path):    return hashlib.sha256(path.read_bytes()).hexdigest()def command_output(args):    result = subprocess.run(args, cwd=ROOT, text=True, capture_output=True, check=True)    return result.stdout.strip()def git_commit():    try:        return command_output(["git", "rev-parse", "HEAD"])    except (OSError, subprocess.CalledProcessError):        return Nonedef machine():    result = {"system": platform.platform(), "architecture": platform.machine()}    if platform.system() == "Darwin":        for name, key in (("cpu", "machdep.cpu.brand_string"),                          ("memory_bytes", "hw.memsize"), ("model", "hw.model")):            result[name] = command_output(["sysctl", "-n", key])    return resultdef trials(models, sizes, replicates):    seed = 0    for model in models:        for size in sizes:            for replicate in range(replicates):                subjects = ("source", "determinized")                if replicate % 2:                    subjects = subjects[::-1]                for subject in subjects:                    yield {"benchmark": model, "samples": size, "replicate": replicate,                           "subject": subject, "seed": seed}                seed += sizedef key(row):    return tuple(row[name] for name in ("benchmark", "samples", "replicate", "subject"))def decode_float(bits):    return struct.unpack("!d", int(bits).to_bytes(8, "big"))[0]def validate_measurement(measured, samples):    if measured["failed"] or measured["first_failure"]:        raise ValueError(f'{measured["failed"]}/{samples} executions failed: '                         f'{measured["first_failure"]}')    if measured["requested"] != samples or \            measured["returned"] + measured["rejected"] != samples:        raise ValueError("incomplete execution counts")    if measured["returned"] < 2 or measured["sampling_ns"] <= 0:        raise ValueError("insufficient returned values or invalid elapsed time")    mean = decode_float(measured["mean_bits"])    m2 = decode_float(measured["m2_bits"])    if not math.isfinite(mean) or not math.isfinite(m2) or m2 < 0:        raise ValueError("non-finite or invalid moments")    return {**measured, "estimate": mean, "output_variance": m2 / measured["returned"],            "sampling_seconds": measured["sampling_ns"] / 1e9}def summarize(rows):    groups = defaultdict(list)    for row in rows:        if row["status"] != "completed":            raise ValueError(f"cannot summarize failed trial {key(row)}")        groups[row["benchmark"], row["samples"], row["subject"]].append(row)    result = []    for (model, size, subject), group in sorted(groups.items()):        estimates = [row["estimate"] for row in group]        elapsed = [row["sampling_seconds"] for row in group]        variance = statistics.variance(estimates)        result.append({            "benchmark": model, "samples": size, "subject": subject,            "replicates": len(group),            "mean_returned": statistics.mean(row["returned"] for row in group),            "mean_rejected": statistics.mean(row["rejected"] for row in group),            "mean_estimate": statistics.mean(estimates),            "estimator_variance": variance,            "estimator_variance_se": variance * math.sqrt(2 / (len(group) - 1)),            "plug_in_estimator_variance": statistics.mean(                row["output_variance"] / (row["returned"] - 1) for row in group),            "mean_sampling_seconds": statistics.mean(elapsed),            "sampling_seconds_stdev": statistics.stdev(elapsed),        })    return resultdef plots(summary, output):    import matplotlib    matplotlib.use("Agg")    import matplotlib.pyplot as plt    plt.rcParams.update({"font.size": 11, "axes.labelsize": 11, "legend.fontsize": 10})    for model in sorted({row["benchmark"] for row in summary}):        fig, ax = plt.subplots(figsize=(3.2, 2.8), layout="constrained")        for subject, label, marker, color in (            ("source", "Source", "o", "#2463a6"),            ("determinized", "Determinized", "s", "#d56a28"),        ):            rows = [row for row in summary                    if row["benchmark"] == model and row["subject"] == subject]            ax.errorbar([row["mean_sampling_seconds"] for row in rows],                        [row["estimator_variance"] for row in rows],                        yerr=[row["estimator_variance_se"] for row in rows],                        marker=marker, color=color, linewidth=1.5, markersize=4,                        capsize=3, label=label)        ax.set(xscale="log", yscale="log", xlabel="Sampling time (s)",               ylabel=r"$\mathrm{Var}(\hat{\mu}_N)$")        ax.grid(True, which="major", alpha=.25)        ax.legend()        fig.savefig(output / f"{model}.png", dpi=220)        plt.close(fig)def save_summary(rows, output):    summary = summarize(rows)    with (output / "summary.csv").open("w", newline="") as stream:        writer = csv.DictWriter(stream, fieldnames=list(summary[0]), lineterminator="\n")        writer.writeheader()        writer.writerows(summary)    plots(summary, output)def main():    parser = argparse.ArgumentParser(description=__doc__)    parser.add_argument("--binary", type=Path,                        default=ROOT / "lean/.lake/build/bin/sampling-bench")    parser.add_argument("--output", type=Path, default=ROOT / "results/estimator-variance")    parser.add_argument("--models", nargs="+", choices=MODELS, default=MODELS)    parser.add_argument("--sizes", nargs="+", type=int, default=SIZES)    parser.add_argument("--replicates", type=int, default=50)    parser.add_argument("--fuel", type=int, default=100000)    parser.add_argument("--warmup", type=int, default=1000)    parser.add_argument("--timeout", type=float, default=180)    parser.add_argument("--resume", action="store_true")    parser.add_argument("--plot-only", action="store_true")    args = parser.parse_args()    if args.replicates < 2 or min(args.sizes) < 2 or args.fuel < 1 or \            args.warmup < 0 or args.timeout <= 0:        parser.error("need at least two replicates/samples, positive fuel/timeout, nonnegative warmup")    output = args.output.resolve()    output.mkdir(parents=True, exist_ok=True)    runs_path = output / "runs.jsonl"    metadata_path = output / "experiment.json"    if args.plot_only:        rows = [json.loads(line) for line in runs_path.read_text().splitlines()]        metadata = json.loads(metadata_path.read_text())        if metadata["status"] != "completed":            raise ValueError("experiment is incomplete")        save_summary(rows, output)        return 0    config = {        "models": list(args.models), "sizes": list(args.sizes), "replicates": args.replicates,        "fuel": args.fuel, "warmup": args.warmup, "timeout_seconds": args.timeout,        "seed_policy": "Disjoint consecutive seed blocks per replicate and size; paired subjects.",        "subject_order": "Alternate source-first and determinized-first by replicate.",        "timing": "Runtime loop and online moments only; excludes parsing, determinization, warmup, output.",        "variance_se": "Normal approximation: sample variance * sqrt(2 / (replicates - 1)).",        "binary_sha256": sha256(args.binary),        "model_sha256": {model: sha256(ROOT / "benchmarks/approx" / f"{model}.det")                         for model in args.models},        "harness_sha256": sha256(ROOT / "lean/SamplingBench.lean"),        "runner_sha256": sha256(Path(__file__)),    }    expected = list(trials(args.models, args.sizes, args.replicates))    if args.resume:        metadata = json.loads(metadata_path.read_text())        if metadata["configuration"] != config or metadata["machine"] != machine():            raise ValueError("resume configuration or machine differs from saved experiment")        rows = [json.loads(line) for line in runs_path.read_text().splitlines()]        if any(row["status"] != "completed" for row in rows):            raise ValueError("saved experiment contains a failed trial; rerun into a new directory")    else:        if runs_path.exists():            raise ValueError(f"{runs_path} exists; use --resume or choose another output directory")        metadata = {            "started_at": datetime.now(timezone.utc).isoformat(), "machine": machine(),            "configuration": config, "git_commit": git_commit(),            "command": sys.argv, "binary": str(args.binary.resolve()),            "lean_toolchain": (ROOT / "lean/lean-toolchain").read_text().strip(),            "python": sys.version, "status": "running",        }        rows = []    completed = {key(row) for row in rows}    if len(completed) != len(rows) or not completed <= {key(row) for row in expected}:        raise ValueError("unexpected or duplicate trials in saved experiment")    metadata["status"] = "running"    metadata_path.write_text(json.dumps(metadata, indent=2) + "\n")    with runs_path.open("a") as stream:        for trial in expected:            if key(trial) in completed:                continue            command = [str(args.binary.resolve()),                       str(ROOT / "benchmarks/approx" / f'{trial["benchmark"]}.det'),                       trial["subject"], str(trial["samples"]), str(trial["seed"]),                       str(args.fuel), str(args.warmup)]            row = {**trial, "status": "failed"}            try:                process = subprocess.run(command, capture_output=True, text=True,                                         timeout=args.timeout, check=False)                row.update({"returncode": process.returncode, "stderr": process.stderr.strip()})                if process.stdout.strip():                    row.update(json.loads(process.stdout))                else:                    raise ValueError(f"sampler exited {process.returncode} without measurements: "                                     f"{process.stderr.strip()}")                row.update(validate_measurement(row, trial["samples"]))                if process.returncode:                    raise ValueError(f"sampler exited {process.returncode}: {process.stderr.strip()}")                row["status"] = "completed"            except Exception as error:                row["error"] = str(error)                stream.write(json.dumps(row, allow_nan=False) + "\n")                stream.flush()                metadata.update(status="failed", error=str(error), failed_trial=trial)                metadata_path.write_text(json.dumps(metadata, indent=2) + "\n")                print(f"ERROR: {key(trial)}: {error}", file=sys.stderr, flush=True)                return 1            stream.write(json.dumps(row, allow_nan=False) + "\n")            stream.flush()            rows.append(row)            if len(rows) % 10 == 0:                print(f'{len(rows)}/{len(expected)} trials: {trial["benchmark"]} '                      f'N={trial["samples"]} replicate={trial["replicate"] + 1}', flush=True)    metadata.update(status="completed", finished_at=datetime.now(timezone.utc).isoformat(),                    completed_trials=len(rows),                    requested_executions=sum(row["requested"] for row in rows),                    rejected_executions=sum(row["rejected"] for row in rows),                    failed_executions=sum(row["failed"] for row in rows))    metadata_path.write_text(json.dumps(metadata, indent=2) + "\n")    save_summary(rows, output)    return 0if __name__ == "__main__":    raise SystemExit(main())