CC 2026
Foresight
A parallel, extensible equality saturation library with programmable saturation strategies, generalized e-graph metadata, and deferred parallel rewriting.
- Impact
- Up to 16x speedup
- Role
- Designed and implemented the core system
- Stack
- Scala · e-graphs · parallel rewriting · IR metadata
Publication
Peer-reviewed paper
CC 2026
Parallel and Customizable Equality Saturation
A parallel, extensible equality saturation engine with programmable strategies and generalized metadata
BibTeX citation
@inproceedings{vandercruysse2026foresight,author = {Van der Cruysse, Jonathan and Zayed, Abd-El-Aziz and Peng, Mai Jacob and Dubach, Christophe},title = {Parallel and Customizable Equality Saturation},year = {2026},isbn = {9798400722745},publisher = {Association for Computing Machinery},address = {New York, NY, USA},url = {https://doi.org/10.1145/3771775.3786266},doi = {10.1145/3771775.3786266},abstract = {Equality saturation enables compilers to explore many semantically equivalent program variants, deferring optimization decisions to a final extraction phase. However, existing frameworks exhibit sequential execution and hard-coded saturation loops. This limits scalability and requires significant engineering effort to customize saturation behavior. This paper addresses these limitations using three novel techniques. First, it shows how saturation can be parallelized thanks to the use of thread-safe data structures and the notion of deferred e-graph updates. Second, it provides an extensible mechanism to express custom and composable saturation strategies. Third, it generalizes e-graph metadata to support custom e-graph annotations. The implementation, written in Scala, is evaluated on four use-cases: classical program optimization, idiom recognition, scalability strategies and incremental equality saturation. The results show that it outperforms several existing equality saturation engines, including the highly optimized egglog library. When used to reimplement an existing idiom recognition technique, the new design finds higher-quality idioms, 16\texttimes{} faster. Additionally, the design is able to natively express state-of-the-art custom equality saturation behavior such as incremental equality saturation and multi-phase rewriting strategies without any modification to the core library.},booktitle = {Proceedings of the 35th ACM SIGPLAN International Conference on Compiler Construction},pages = {94–105},numpages = {12},keywords = {Compiler Infrastructure, E-Graphs, Equality Saturation, Program Optimization, Rewrite Systems},location = {Sydney, NSW, Australia},series = {CC '26}}Talks
Presentations and related material
Technical Story
How the system works
I designed and implemented Foresight, an equality saturation library motivated by concrete limitations I observed in existing engines, such as single-threaded execution, rigid saturation loops, and limited support for metadata.
Design goals
Foresight’s architecture is guided by three core ideas that address the limitations of prior approaches: parallel rewriting, saturation strategies and generalized metadata.
Parallel rewriting as a first-class concern
Foresight performs parallel e-matching combined with deferred rewriting by producing rewrite commands from e-matches that are batched and applied in parallel. This approach improves throughput while preserving correctness and fully exploits concurrency.
Programmable saturation strategies
Instead of a fixed saturation loop, Foresight uses composable building blocks that let users programmatically control the rewriting process. This flexibility enables experimentation and reuse, allowing saturation to be tailored to specific needs.
Generalized metadata
Metadata is implemented as extensible observers attached to e-graphs, unifying various analyses and enabling advanced features such as incremental equality saturation.
Results
Evaluation shows that Foresight consistently outperforms prior Scala-based equality saturation engines, achieving up to 16× speedups on a reimplementation of latent idiom recognition and robust scaling for key rewrite and analysis phases under parallel execution. Its deferred rewriting architecture allows parallel rule matching and application to scale effectively, while generalized metadata enables features such as incremental equality saturation without modifying the core engine. Across multiple case studies, Foresight reduces the amount of custom, application-specific saturation code from hundreds of lines to a small number of composable strategy definitions.
The source code is available on GitHub at https://github.com/jonathanvdc/foresight. The design and evaluation of Foresight are described in detail in the Foresight compiler-work page, which includes the CC’26 paper, artifact badges, and talk record.