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.