bytecodealliance / bytecodealliance/wasmtime

Cranelift: build better abstractions around "pooled-sequences Vec and range-list Vec" data structure

Open
#4,028 6 comments 0 reactions 0 assignees View on GitHub
cranelift enhancement
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.