一句话：用多阶段编程消除 PBT 生成器抽象开销并优化随机源，使找 bug 最高提速 13 倍。
基于属性的测试（PBT）依赖生成器产生随机测试用例，这些生成器通常由嵌入式 DSL 中的组合子构造。生成器速度直接决定 PBT 的有效性，但实测表明主流 PBT 库的生成器性能远未达到可能的上限，主因是组合子风格带来的抽象开销和随机源选择不佳。本文系统刻画并量化了这两类瓶颈，并分别加以解决：为消除抽象开销，提出基于多阶段编程（multi-stage programming）的技术 Allegro，并将其应用于 OCaml 与 Scala 3 的主流生成器库；为量化随机源的影响，开展受控实验，将 OCaml PBT 库中的随机源替换为优化版本。两种改进均严格保持生成器语义不变，因而可进行精确的逐点比较。综合这些改进，PBT 发现 bug 的速度最高提升 13 倍。
Property-based testing (PBT) relies on generators for random test cases, often constructed using embedded domain specific languages, which provide expressive combinators for building and composing generators. The effectiveness of PBT depends critically on the speed of these generators. However, careful measurements show that the generator performance of widely used PBT libraries falls well short of what is possible, due principally to (1) the abstraction overhead of their combinator-heavy style and (2) suboptimal sources of randomness. We characterize, quantify, and address these bottlenecks. To eliminate abstraction overheads, we propose a technique based on multi-stage programming, dubbed Allegro. We apply this technique to leading generator libraries in OCaml and Scala 3, significantly improving performance. To quantify the performance impact of the randomness source, we carry out a controlled experiment, replacing the randomness in the OCaml PBT library with an optimized version. Both interventions exactly preserve the semantics of generators, enabling precise, pointwise comparisons. Together, these improvements find bugs up to 13× faster.
@article{paperbot3788,
title = {Fail Faster: Staging and Fast Randomness for High-Performance PBT},
author = {Cynthia Richey and Joseph W. Cutler and Harrison Goldstein and Benjamin C. Pierce},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {OOPSLA1},
year = {2026},
doi = {10.1145/3798263}
}