bytecodealliance / bytecodealliance/wasmtime
Cranelift: build better abstractions around "pooled-sequences Vec and range-list Vec" data structure
- Dominant language
- Rust
- Stars
- 18.6k
- Forks
- 1.8k
- Avg merge
- 1d 18h
- Merged PRs (30d)
- 126
Description
In the VCode container, we've stumbled into a fairly handy data structure design idiom, like so:
```rust
/// Operands: pre-regalloc references to virtual registers with
/// constraints, in one flattened array. This allows the regalloc
/// to efficiently access all operands without requiring expensive
/// matches or method invocations on insts.
operands: Vec,
/// Operand index ranges: for each instruction in `insts`, there
/// is a tuple here providing the range in `operands` for that
/// instruction's operands.
operand_ranges: Vec<(u32, u32)>,
```
which lets us aggregate allocation overhead into fewer, larger `Vec`s rather than a bunch of little ones when we have a conceptually-2D (or N-D) array. This pattern can be extended further, for example for outgoing block args, which are 3D (per block, per successor, we have a list): we do this with a rangelist that gives a range in another rangelist that gives ranges in a pooled sequence.
We manage this manually, and even combine the pooled `Vec` when we can for more goodness. It would be nice to make this less error-prone by wrapping it up in a typesafe wrapper:
* A core struct that owns the pool (the `operands` above);
* A means of composing types to add one or more range-lists on top of that pool;
* A handle type that temporarily takes ownership, allows appending, and adds a rangelist entry when done, to enforce that sequences must be contiguous in the pooled sequence.
Doing this while allowing pool-sharing will take a little thought, but if we can find a way to do it, it could allow us to reduce allocations further.
Contributor guide
Assessment
This issue has not been assessed yet.