BlockstreamResearch / rust-simplicity

Creative Commons Zero v1.0 Universal
58 stars 12 forks source link

types: use slab allocator for type bounds #231

Closed apoelstra closed 2 months ago

apoelstra commented 2 months ago

Our existing type inference engine assumes a "global" set of type bounds, which has two bad consequences: one is that if you are constructing multiple programs, there is no way to "firewall" their type bounds so that you cannot accidentally combine type variables from one program with type variables from another. You just need to be careful. The other consequence is that if you construct infinitely sized types, which are represented as a reference cycle, the existing inference engine will leak memory.

To fix this, we need to stop allocating type bounds using untethered Arcs and instead use a slab allocator, which allows all bounds to be dropped at once, regardless of their circularity. This should also improve memory locality and our speed, as well as reducing the total amount of locking and potential mutex contention if type inference is done in a multithreaded context.

This is a 2000-line diff but the vast majority of the changes are "API-only" stuff where I was moving types around and threading new parameters through dozens or hundreds of call sites. I did my best to break everything up into commits such that the big-diff commits don't do much of anything and the real changes happen in the small-diff ones to make review easier.

By itself, this PR does not fix the issue of reference cycles, because it includes an Arc<Context> inside the recursive Type type itself. Future PRs will:

uncomputable commented 2 months ago

To summarize:

apoelstra commented 2 months ago

Is that correct?

Correct on both counts.

apoelstra commented 2 months ago

Fixed both nits. Will leave the ShallowClone stuff to a later PR.