Stream: git-wasmtime

Topic: wasmtime / issue #4028 Cranelift: build better abstractio...

Wasmtime GitHub notifications bot (Apr 14 2022 at 01:01):

cfallin opened issue #4028:

In the VCode container, we've stumbled into a fairly handy data structure design idiom, like so:

    /// 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>,

    /// 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)>,
    /// 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>,

    /// 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 Vecs 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.

Wasmtime GitHub notifications bot (Apr 14 2022 at 01:09):

cfallin edited issue #4028:

In the VCode container, we've stumbled into a fairly handy data structure design idiom, like so:

    /// 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>,

    /// 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 Vecs 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.

Wasmtime GitHub notifications bot (Apr 14 2022 at 09:21):

bjorn3 commented on issue #4028:

Isn't this just cranelift_entity::EntityList?

Wasmtime GitHub notifications bot (Apr 14 2022 at 16:43):

fitzgen commented on issue #4028:

Also basically a poor person's bump allocator, but instead of handing out references, hands out indices.

Wasmtime GitHub notifications bot (Apr 14 2022 at 16:46):

cfallin commented on issue #4028:

@bjorn3 -- not quite, though they are in the same area: EntityList has alloc/realloc/free and appears to keep metadata in the array as well (length of each individual list), and is specifically a list of indices, rather than T.

Indeed this is a bump allocator! I guess the special twist is that it has a secondary list-of-ranges and so the abstraction is "list of lists" rather than "list of arbitrary objects". It'd be great to have a wrapper that lets us do the same things we do in VCode now (build each sublist one element at a time, demarcate the end of a list and get a range).

Wasmtime GitHub notifications bot (May 10 2022 at 11:32):

akirilov-arm labeled issue #4028:

In the VCode container, we've stumbled into a fairly handy data structure design idiom, like so:

    /// 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>,

    /// 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 Vecs 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.

Wasmtime GitHub notifications bot (May 10 2022 at 11:36):

akirilov-arm labeled issue #4028:

In the VCode container, we've stumbled into a fairly handy data structure design idiom, like so:

    /// 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>,

    /// 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 Vecs 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.

Wasmtime GitHub notifications bot (May 10 2022 at 19:29):

jakubDoka commented on issue #4028:

@cfallin you don't need Vec<(u32, u32)> but just Vec<u32>, where you start with vec![0] and always push the length of operands after allocating new list. Then when you need to get a slice, ask for EntityRef and get star and and like (k.index(), k.index() + 1).

Wasmtime GitHub notifications bot (May 10 2022 at 19:30):

jakubDoka edited a comment on issue #4028:

@cfallin you don't need Vec<(u32, u32)> but just Vec<u32>, where you start with vec![0] and always push the length of operands after allocating new list. Then when you need to get a slice, ask for EntityRef and get (start, end) like (k.index(), k.index() + 1).

Wasmtime GitHub notifications bot (May 10 2022 at 21:04):

cfallin commented on issue #4028:

@jakubDoka unfortunately this technique doesn't work if the instructions are reordered in any way: for example in the VCode we emit bottom-to-top (to allow us to pattern-match up the operand trees) and then reverse at the end. In general the order of list contents in the backing pool may not match the order of lists so we can't rely on "my end is next list's start" as an invariant.

Wasmtime GitHub notifications bot (May 11 2022 at 05:18):

jakubDoka commented on issue #4028:

@cfallin I see. Well I guess these are two different data-structures, each having it's onw advantages.

Last updated: Dec 23 2024 at 12:05 UTC