Fail Faster

Cynthia Richey, Joseph W. Cutler, Harrison Goldstein, Benjamin C. Pierce · 2025

Read Fail Faster by Cynthia Richey, Joseph W. Cutler, Harrison Goldstein, Benjamin C. Pierce (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-19797.txt.

Introduction

Cynthia Richey, Joseph Cutler, Harrison Goldstein, and Benjamin Pierce speed up property-based testing by making its random case builders run faster, in a paper from 2025. Such testing feeds random inputs to code to hunt for bugs. The speed of the builders caps how much testing gets done.

Careful timing showed that top libraries in OCaml and Scala fall well short of what is possible. Two causes stood out: overhead from layered builder parts, and slow sources of randomness. Their fix, Allegro, uses multi-stage programming to strip the overhead away. A second test swapped in a faster random source. Both changes keep builder behavior the same, and together they found bugs up to 13 times faster.

Catalog record

CREATORCynthia Richey, Joseph W. Cutler, Harrison Goldstein, Benjamin C. Pierce
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-19797

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fail Faster Cynthia Richey, Joseph W. Cutler, Harrison Goldstein, Benjamin C. Pierce Abstract . 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 × 13\times faster. DOI: 10.1145/3798263 Journal: PACMPL Volume: 10 OOPSLA1 155 4 oopslaa26main-p387-p CCS: Software and its engineering CCS: Software and its engineering Software notations and tools CCS: Software and its engineering Software libraries and repositories CCS: Software and its engineering Translator writing systems and compiler generators Staging and Fast Randomness for High-Performance PBT † † cc-license: by 1. Introduction Property-based testing is a software testing technique that uses random test inputs to validate logical specifications ( Claessen and Hughes, 2000b ) . A recent study on PBT usage in industry ( Goldstein et al., 2024 ) shows that many practitioners run their property-based tests very frequently, and with a very short time budget. The faster the tests fail, the better. One important opportunity for performance improvement is the generators that produce random inputs to the properties under test. These generators are written with the help of generator libraries , usually expressed as embedded domain-specific languages (eDSLs) that provide combinators for building and composing generators. However, careful measurements show that the performance of existing generator libraries falls far short of what is possible, for two reasons. First, the high-level design approach followed by generator combinator libraries introduces layered abstractions that are difficult for compilers to optimize. Second, the calls a generator makes to its randomness library can constitute a large proportion of its run time, magnifying the cost of an inefficient implementation. In this paper, we characterize, quantify, and address these issues. We address the overhead of many common generator abstractions using multi-stage programming (or staging ), a well-studied technique for building fast DSLs "without regret" ( Rompf and Odersky, 2012 ) . The simple monadic structure of typical PBT generators lend themselves naturally to well-known staging transformations. Beyond these basic techniques, we observe that common usage patterns of fundemental PBT-specific combinators—e.g., weighted choices with statically known options—are amenable to advanced staging techniques ( Yallop et al., 2018 ; Kovács, 2024 ; Carette and Kiselyov, 2005 ) . We refer to this approach as Allegro. To demonstrate its generality, we implement staged generator DSLs in two strict functional languages: OCaml and Scala 3. In OCaml, we build AllegrOCaml, based on Base_quickcheck —a high-quality PBT library in OCaml, authored by software engineers at the trading firm Jane Street ( Street, 2021 ) . In Scala 3, we build ScAllegro, based on ScalaCheck—the language’s standard PBT library ( , 2021 ) . We isolate and quantify the performance benefits of faster randomness, showing that a DSL’s choice of randomness library has a dramatic effect on its performance. Based on the observation that the OCaml implementation of Base_quickcheck ’s randomness library is slow in a way that is simple to fix, we perform a controlled experiment, comparing fast and slow versions of the library to analyze the impact of faster randomness libraries on generator performance. We perform this comparison in AllegrOCaml. Both interventions preserve semantics on the nose: given the same random seed, generators written using AllegrOCaml or ScAllegro produce exactly the same sequence of values as equivalent generators using Base_quickcheck or ScalaCheck. This semantic equivalence enables pointwise—as opposed to distributional—comparisons of bug-finding effectiveness, ensuring that, if an Allegro generator finds bugs faster, this is attributable solely to the staging and randomness library interventions, not lucky choice of seeds. We evaluate the optimizations with a series of case studies in each generator library, and show that the Allegro generators run faster than their unstaged equivalents. In AllegrOCaml, they run up to 7\times faster, and in ScAllegro, up to 13\times faster. Using our improved version of Base_quickcheck ’s randomness library in AllegrOCaml, we see even greater gains—more than 12\times —showing that both staging and fast randomness play distinct and complementary roles in improving generator performance. Further, we show that AllegrOCaml generators find bugs faster by running our case studies in the Etna platform, which uses generated values as inputs to a buggy system and measures how quickly different generators can detect the bugs. In Etna, AllegrOCaml generators find bugs up to 2.5\times faster on average than their Base_quickcheck counterparts. With fast randomness, the average speedup rises to 3.8\times , with some cases exceeding 13\times . Finally, we review related libraries in other languages including Racket, F#, Haskell, Rust, Clojure, and Swift, and discuss how the Allegro technique could be applied to them. In summary, we show that PBT generator DSLs incur significant performance costs across languages and present two interventions that significantly improve their efficiency while preserving their idiomatic style. Concretely, we offer the following contributions: (1) We identify two key sources of inefficiency in PBT generator libraries—abstraction overhead and choice of randomness library—both of which significantly impact performance (Section 2 ). (2) We present Allegro, a staging technique that eliminates the abstraction overhead of generators. We apply Allegro to standard generator libraries in both OCaml and Scala 3, showcasing its generality (Section 3 ). (3) We demonstrate that writing generators using the Allegro technique combined with fast randomness libraries yields substantial performance improvements, both separately and in combination, and we show that these performance improvements extend to significantly improved bug-finding speed (Section 4 ). Section 5 discusses how the Allegro technique could be applied to PBT libraries in other languages—Racket, F#, Haskell, Rust, Clojure, and Swift. Sections 6 and 7 present related and future work. 2. What Are Generator Libraries, and Why Are They Slow? Property-based testing ( Claessen and Hughes, 2000a ) is an approach to software testing that centers around executable specifications of programs called properties . For example, if a programmer wants to test an invariant of a binary search tree (BST) implementation they are working on, they may write a property like prop_insert_invariant t x = isBST t ==> isBST (insert x t) to check that for any tree t and value x , if t is already a valid BST then inserting x into it also yields a valid BST. Once a developer has a property, they test that property by executing it on hundreds or thousands of random test inputs. These test inputs are usually produced by a generator —a program written in some domain-specific language (DSL) that allows the developer to express precisely

Read the complete text