Fail Faster: Staging and Fast Randomness for High-Performance PBT
This work addresses performance issues in PBT libraries for developers, offering incremental improvements to existing methods.
The paper tackled the performance bottlenecks in property-based testing (PBT) generators, which are slow due to abstraction overhead and suboptimal randomness sources, and by applying multi-stage programming and optimized randomness, it achieved up to 13x faster bug detection.
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\times$ faster.