Pre-Proposal: More Array Constructors

[fitzgen]

Pre-Proposal: More Array Constructors

The methods for constructing immutable arrays is rather limited at the moment. In particular, it is impossible to create an immutable array with both dynamic (defined at runtime) length as well as dynamic and heterogeneous contents.

Consider the current set of instructions for allocating arrays:

Instruction	Length	Contents
array.new	dynamic	dynamic, homogeneous
array.new_default	dynamic	static, homogeneous
array.new_fixed	static	dynamic, heterogeneous
array.new_data	dynamic	static1, heterogeneous
array.new_data	dynamic	static1, heterogeneous

Mutable arrays can always have their contents updated after construction. For immutable arrays, we do not have that luxury, and creating an immutable array of dynamic length and dynamic, heterogeneous contents requires the following, missing row:

Instruction	Length	Contents
???	dynamic	dynamic, heterogeneous

For this hypothetical instruction, where should the dynamic contents come from? Because they have dynamic length, they cannot come from the value stack; that would break validation. A Wasm program might want any one of three options:

1. From another array: The Wasm program might want to copy an existing array's contents, or a subslice of those contents, into a new array.
2. From a memory: The Wasm program might want to copy a slice of memory into a new array (which must be an array whose element type has a defined bit width, i.e. not an array of references).
3. From a table: The Wasm program might want to copy a slice of table elements into a new array (which must be an array whose element type is a reference type).

From an expressivity perspective, any single one of those options can unlock the construction of dynamic, heterogeneous, immutable arrays and the other operations could be built on top of it. If you had an instruction for creating an immutable array from a subslice of memory, for example, you could implement creating an immutable array from a subslice of another array by first copying the source array's subslice to memory and then using the array-from-memory-subslice instruction to create the new array. That said, while it is possible to implement these operations in terms of one another, having an instruction for each variant should be much easier for engines to optimize.

The Proposed Instructions

Instruction	Type	Informal Description
array.new_array dst src	[(ref null src) i32 i32] -> [(ref dst)]	Create an array of type dst from a subslice of the elements of an array of type src. Element subslice is given as (start, length). Validation requires elements(dst) <: elements(src). Traps on out-of-bounds.
array.new_memory dst src	[i32 i32] -> [(ref dst)]	Create an array of type dst from a subslice of the memory src. Memory subslice is given as (start, length) where length is in units of elements, not bytes. Validation requires that the memory src exists and that elements of dst have a defined bit width. Traps on out-of-bounds.
array.new_table dst src	[i32 i32] => [(ref dst)]	Create an array of type dst from a subslice of the table src. Table subslice is given as (start, length). Validation requires that the table src exists and that elements(dst) <: elements(src). Traps on out-of-bounds.

The exact details, of course, remain flexible; my intent is to provide a starting point for discussion.

Why Should We Care About Immutable Arrays?

• Zero-copy, shared-nothing linking: Shared-nothing linking requires that components are isolated from one another and that they only communicate with each other via explicit imports and exports. They cannot, for example, share some state (like a memory, for example) that would allow a malicious component to smash and overwrite another component's data in that shared state. When doing shared-nothing linking, we can pass immutable arrays at the ABI boundary without copying. This is safe because we know that even if the sender holds onto a reference to the array, it cannot mutate that array after it has been shared with the receiver, which could otherwise lead to sandboxing bugs, data smashing, and side-channels that break the shared-nothing paradigm.

• More opportunities for compiler optimizations: Because immutable objects do not change, the compiler is free to eliminate redundant loads, replacing their uses with uses of the previously-loaded value (essentially GVN'ing loads) without first performing any complex and potentially expensive alias analysis. This leads to better code generation and faster Wasm execution while maintaining compiler simplicity and fast compile times.

• More opportunities for specialized garbage collection: Immutable objects cannot create cycles, which creates opportunities for garbage collectors to special case these objects. A reference counting collector that has a periodic cycle collection phase need not consider an immutable sub-graph in its cycle collector. Alternatively, a collector that generally uses tracing might decide to use reference counting for immutable sub-graphs of objects once they graduate from the nursery to the tenured heap, combining some of the incremental benefits of reference counting with the throughput and completeness of tracing. Furthermore, certain kinds of GC barriers can be completely omitted for immutable objects: an immutable object can never point to another object that is younger than itself so in a generational collector, for example, an immutable object need not record its edges in the remembered set. These kinds of specializations lead to less work for the collector and, ultimately, better mutator throughput and shorter GC pauses.

In general, however, we only get to leverage these benefits for immutable arrays in practice if Wasm can create arbitrary immutable arrays, and that requires something like the instructions proposed above. These proposed instructions are pretty trivial to implement but provide out-sized benefit for Wasm programs; that is, these instructions yield a lot of relative bang for a little buck. The language already has immutable arrays and engines must already support them, so we might as well actually make them useful.

Why Not Define readonly References Instead?

The GC proposal's repository's post-MVP document sketches a new type of reference: a readonly reference. A readonly reference can point to any kind of heap type (with mutable or immutable elements or fields) but the referenced object cannot be mutated through this reference. You must have a non-readonly reference to mutate the object. You cannot cast or coerce a readonly reference into a non-readonly reference.

With this potential extension, a mutable array could be allocated, initialized, and then a readonly reference to the object could be passed to code that must not mutate it.

This language extension might be desirable, but it does not obviate the benefits of adding new instructions for creating arbitrary immutable arrays:

• In a shared-nothing linking scenario, we cannot avoid copies for readonly references because the side that allocated the array could hold onto a non-readonly reference. Then, it could mutate the array after sharing it, which breaks the shared-nothing isolation properties. Therefore, a shared-nothing linking scenario would be forced to copy the array.

• Because a mutable-and-exclusive xor immutable-and-shared discipline similar to Rust would not (presumably) be forced upon references by validation, the compiler could not generate code for readonly references under the assumption that the referenced object's elements or fields could not change. In fact, they could indeed change if some non-readonly reference exists elsewhere in the program. Proving that they could not change, and therefore that optimizations like redundant load elimination are safe, would require a potentially complex and expensive alias analysis.

• A garbage collector could not assume that a readonly reference points to an immutable sub-graph that does not participate in cycles; the cycles could have been created before the readonly reference existed, or might be created via some other non-readonly reference to the same object or sub-graph.

Previous Discussions

• webassembly/gc#515: Dynamically initializing a non mutable array
• webassembly/gc#570: Ability to construct const/non-mutable arrays of unknown size from mutable arrays
• webassembly/gc#579: cast mutable array to immutable array
• webassembly/gc/.../Post-MVP.md: Readonly Fields

I'm sure I've missed some links here, please share any other previous discussions you know of.

Footnotes

1. For array.new_data and array.new_elem, the contents are arguably not fully static, as they may be any subslice of a pre-existing data or element segment. The important bit is that, because new segments cannot be constructed at runtime, the instruction does not allow for fully dynamic, arbitrary contents defined at runtime. ↩ ↩²

[tlively]

Makes sense to me. These instructions would definitely fill expressivity gaps in the current design. Have you heard from any toolchains that would be interested in using these instructions?

[fitzgen]

@tlively

Have you heard from any toolchains that would be interested in using these instructions?

My employer has an internal language that compiles to Wasm and would like to leverage these instructions to unlock zero-copy, shared-nothing linking in more cases.

I've also talked with @ospencer about these instructions, and I believe that Grain would also like to have them, although I will let him answer more definitively.

While I haven't talked to any other toolchain folks yet, I expect that any toolchain that

1. targets WASI and/or the component model,
2. uses Wasm GC, and
3. has source-level immutable objects

will want these instructions as well. In fact (1) is probably not even a prerequisite, since any Wasm toolchain with (2) and (3) will want to preserve immutability at the Wasm level when possible to take advantage of things like better compiler optimizations in Wasm engines.

[ospencer]

In particular, for Grain, I ran into this when switching over to GC from linear memory. Grain strings are immutable, so I started out by implementing strings as (array (ref i8)), and quickly ran into an issue implementing concatenation—there's no way to create a new immutable array from two (or any number, for that matter) arrays. It's not a huge deal because this is easily solved by using mutable arrays, but is a bit of a bummer from a codegen and optimization perspective. This also wasn't just the case for strings, but nearly every data type—one by one I found a situation where immutable arrays just wouldn't work. The implementation isn't complete yet, but every array type used is mutable, even though pretty much all of our data structures in the language are immutable.

I felt this was all fixable/addressable, but I wasn't too pressed until we started thinking about the Component Model, and realized that if we naively defined string types as (array (ref i8)) or (array (ref i16)) instead of their mutable counterparts, it (generally) wouldn't be possible for GC languages to pass strings, since their internal representation is likely mutable, and there's no way to convert them to the immutable type. While this is kind of okay for language toolchains, it's less desirable for something like the Component Model, where we want to minimize passing mutable buffers between components, since they could be used as a separate communication channel.

[tlively]

Hmm, this proposal alone wouldn't be sufficient to solve the string concatenation problem you mentioned unless you first copied data into a mutable array/table and then back out. Would that be sufficient for you, or would we also need something like array.new_concat or array.new_flatten to construct immutable arrays from several other immutable arrays?

[rossberg]

It makes sense to me to add a couple more array constructors, but I don't think that will ultimately achieve what is suggested here. Languages that feature immutable array-like data types typically provide a whole range of primitives for creating them, like some of

• init (and init 2D, init 3D)
• tabulate (and tabulate 2D, tabulate 3D)
• append, flatten (and deep flatten)
• subrange
• map, map with index, map over pair
• zip, unzip
• conversions from other types
• ...

In a native implementation, all these are naturally implemented with mutation under the hood. It is unrealistic that Wasm could efficiently support an open-ended set like the above for immutable representations. Hence it has always been the assumption that source-level immutable types are lowered to mutable ones, no different from linear memory or native code.

As I mentioned in the past, the only reason we support immutability at all is that it is needed to obtain certain subtype relations, e.g. for method tables. But these are typically structs. For most cases we are currently missing, readonly ought to be enough.

As for optimisations, I can't think of many interesting ones that an engine could apply to immutable arrays that a producer cannot do itself. And we have always made the assumption that producers are responsible for most optimisations.

I haven't considered the component system before, but of course it's generally impossible to achieve zero-copy there. No attempt of doing so will realistically work cross-language/runtime, since impedance mismatches between representations are just way too frequent. For the intra-language case OTOH, the component system probably is overkill to boot.

That said, if we want to seriously support non-trivial uses of immutable array representations, then an additive approach of just adding more constructor instructions isn't going to solve the problem. The only sufficiently general solution would be some kind of freeze primitive, that turns a mutable into an immutable array (and perhaps structs) after it has been initialised. However, that is a highly non-trivial feature, as it requires either some kind of static linearity/ownership tracking in the type system, or a runtime check, probably for all mutating instructions. The Frozen Value proposal proposes the latter, but I'm not sure how viable it is, because of the unbounded cost of deep freezing. Perhaps a shallow variant is possible, but it is unclear if it would be general enough to handle more interesting cases.

[ospencer]

I agree that the set of instructions here doesn't completely solve for all of what I was saying—it's pretty likely that we'll continue to use mutable types for a variety of things for many of the reasons Andreas suggested.

The main thing that I do feel needs to be addressed is that we can't produce an immutable array from a mutable one, particularly for cases where I have an import like this:

(module
  (import "env" "func" (func $func (param (ref (array i8)))))
)

If my internal representation of byte arrays are mutable, I don't have any way of passing it to this import without modifying the module (or host code) that's providing the import, which may not be possible.

If I have an instruction that lets me produce a new array from an existing one, then I can satisfy this interface, even if it isn't the most efficient.

To @tlively's question, I mostly care about enabling this behavior. It'd be nice to have additional instructions, but not necessary.

[tlively]

Even if we accept that shared-nothing-linking may requiring copying from a "normal" mutable array to a special immutable array, we would still need new constructors filling the expressivity gap @fitzgen identified. It sounds like we're all on the same page that some new constructors are warranted, but we want to avoid scope creep and do not think opening the door to new arbitrarily complex constructors makes sense. The initially proposed set of new constructors sounds good to me.

[fitzgen]

@tlively

but we want to avoid scope creep

Big +1 to this.

---

@rossberg

Languages that feature immutable array-like data types typically provide a whole range of primitives for creating them

It is true that the proposed constructors will not solve all use cases, but I believe that they would still provide value, especially given the current expressivity gap and their relatively trivial implementation. We haven't generally held ourselves to solving everything for everyone before shipping something useful in the past (see: Wasm MVP, Wasm GC MVP, etc.) and I don't see why we should start now.

As for optimisations, I can't think of many interesting ones that an engine could apply to immutable arrays that a producer cannot do itself.

The Wasm producer cannot do GC-related things like omit barriers; that must be done by the engine itself.

I haven't considered the component system before, but of course it's generally impossible to achieve zero-copy there.

Yes, in the general case, we have to copy. We would still like to avoid it when possible.

The Frozen Value proposal proposes the latter, but I'm not sure how viable it is, because of the unbounded cost of deep freezing. Perhaps a shallow variant is possible, but it is unclear if it would be general enough to handle more interesting cases.

Perhaps the frozen value proposal is the most-general and most-viable solution in the long term, but that is not clear to me. I also share your concerns about the associated costs. Either way, it doesn't solve our current expressivity gap.

(Regarding shallow- vs deep-freezing, unless I am missing something, it seems like a shallow-freezing primitive would be the way to go, since deep-freezing could then be implemented in Wasm on top of it.)

[rossberg]

As mentioned, the OP proposal sounds fine. But we must be careful not to create the expectation that lowering immutable data structures to immutable Wasm is or will be an expected or "supported" approach.

Yes, in the general case, we have to copy. We would still like to avoid it when possible.

The "avoid when possible" part is not something I subscribe to unconditionally. In a case like here, where the only way to do so is adding an open-ended set of features, it would in reality result in an ad-hoc feature selection that privileges specific languages, which is the worst possible outcome. I'm always wary that Wasm could fall into this bias trap.

it seems like a shallow-freezing primitive would be the way to go, since deep-freezing could then be implemented in Wasm on top of it.

Unfortunately, deep freezing is more expressive and cannot easily be emulated with shallow. Consider the case of (multiple) mutually recursive objects that can only be frozen together. Closure graphs of mutually recursive functions are one common example of this. I believe a shallow freeze would at least have to operate on a (static) list of objects of possibly heterogeneous type, and that could still not cover the case where the object set is dynamic (which may be good enough for most purposes).