Parallel rewrites

[Kixiron]

Egg could probably see a sizeable speedup from parallel rewrites, each thread could get a subset of the total rewrites for itself to apply within each iteration before merging the generated graphs and then continuing iterating

[mwillsey]

We have tried it on a branch before, but parallelizing the actual rewriting (as opposed to just the searching) is non trivial. Yes, I guess we could clone the e-graph or something, but that is definitely more complicated. I believe the speedup was less that you'd hope for, because search runtime is typically dominated by one or two "slow" rules, and you can't really speed up one rule.

[Kixiron]

Can you parallelize searching then if that's the big time sink?

[mwillsey]

Since search runtime is dominated by a very small number of "slow" rules, you'd have to be able to speedup a single rule. I'm not totally sure how to parallelize at a granularity smaller than a single rule: you could do rule and e-class level, but I'm worried that'd be so fine-grained that you'd start seeing too much overhead. It's not impossible, I just haven't figure out how to usefully parallelize egg yet.

(migrating this to a discussion for now; it's not an immediate work item)