Batches for Recursive Data Structures

submited by

Style Pass

2024-09-01 06:30:03

Most of Herbie is spent thinking about expressions: generating them, evaluating them, mutating them, analyzing them, filtering them, and so on. So naturally this has to be as fast as possible.

Herbie is a primarily mutational synthesis engine—most expressions it thinks about are generated by changing, in small ways, another expression—so most of its expressions are very similar and share subexpressions. This makes duplication a big problem: Herbie wastes a lot of time analyzing identical subexpressions repeatedly. Caching things can help, but caches introduce their own problems: hashing large expressions is slow, hash tables are slow, garbage collection becomes an issue, and memory usage increases. We are therefore rewriting Herbie to focus on batches.

A batch is a linear encoding of a recursive data structure. This is a well-known performance trick (Adrian Sampson has a good walkthrough), but the details of actually working with this representation have been challenging, and in this blog post I want to walk through some of the things I've learned.