Allow references to any numeric type

[wingo]

Given that this proposal aims to allow WebAssembly be a target for high-level languages, I think that the right way to go with intref is to allow a reference to any numeric type (i32, i64, f32, or f64). As you say, it's a bit more high-level but would allow for better perf on some architectures.

Floatrefs would seem to hit the sweet spot for those WebAssembly implementations that can actually represent even f64 as immediates. Additionally I speculate that when embedded in a Web engine, (ref f64) would minimize impedance mismatch with JS numbers when just shunting a JS value through a WebAssembly component via anyref -- but I defer to the actual web engine experts here :)

For intrefs, I assume that even if a 31-bit restriction is recommended, that it's not part of the semantics: an intref is already 32 bits. Otherwise that would have other ripple effects and failure modes. For that reason I think (ref i32) is probably the right formulation; intrefs are already high level in that they abstract over a platform-specific limit (edit: a soft limit between two different perf profiles). While you have that, you might as well have (ref i64), and a first implementation of any of these can just use heap numbers.

[rossberg]

Note that this possibility is already mentioned in the current overview.

[aardappel]

@rossberg how would a reference to any numeric type typically be implemented? If floats would be implemented similarly to java.lang.Float (a heap allocation), that would probably be unacceptable performance-wise to dynamically typed languages (if they were to use anyref thru-out).

in wasm32, I don't see how we can tag all 4 types numeric types sensibly.

If wasm had something like Rust's enums (ADTs as value types) then a dynamically typed language could implement its own tagging that does not steal bits from numeric types.. but of course is typically inefficient in memory usage. Though I guess you might argue that in this case a dynamically typed language is better off using linear memory and its own GC?

Besides for dynamically type languages, a java.lang.Float style solution to unifying type representation may also be problematic to statically typed languages trying to implement generic containers on top of wasm (if they can't or won't specialize them).

[rossberg]

@aardappel, algebraic data types (aka sum types or disjoint unions or variants) is the TODO under "Possible Extension: Variants" that I ought to fill in. See the older discussion and my comment here for some context.

I believe what you are getting at is the ability to define what is often called a universal representation. All languages that are either untyped or provide expressive enough parametric polymorphism (like most functional languages and modern OO languages) typically need to map all their values into an efficient universal representation, usually a machine word that is tagged as either a pointer or an integer. Unfortunately, it is very difficult to do that effectively in a manner that is independent from hardware, especially word size. Even variants might not be good enough for that. The only way to make that sufficiently efficient across all platforms might be to provide a universal type in Wasm itself, and let the VM pick the most efficient representation at JIT time on the executing hardware. We will probably need to explore a number of options.

[aardappel]

Ah ok. Would be good to flesh that out, here or elsewhere.

While generally giving room to the VM implementor seems like a good idea, I don't think we can leave this undefined without at least some guidance as to what we expect a typical implementation to look like, as the trade-offs are too significant for a language implementor.

Trade-offs as I see them on how to represent numerical values and pointers uniformly:

• Use tag bits in a pointer. Downsides are:
  • It affects semantics (many languages specify the number of bits in their types and may not have room for tag bits, i.e. users may rightfully expect to be able to preserve all bits in a uint64_t).
  • We already committed to 4 numeric types, which would need more tag bits and/or a minimum 64-bit size for these universal values even in wasm32.
  • We need to support all these cases even though we don't know what the language needs. There are languages out there with only one numeric type (or only one bit-width) that are not optimally served by whatever solution we provide.
• Use tag bits outside of a pointer / numerical value (this is similar to your "variant", right?). Downsides are:
  • Uses excessive memory, need 128-bits to store an aligned uint64_t that preserves all bits. Worse, need those same 128-bits to store a 32-bit value in a context that may also need to store full 64-bit values.
• Store numerical values as objects. This is the java.lang.Float referred to above. Downsides are:
  • Causes heap allocation. Maybe this can be optimized by some smart analysis, but I doubt we want to rely on that.

If I am language implementor needing such a universal representation, not knowing which of the above I can rely on the be efficient for my use case, I'd be forced to roll my own in linear memory.

Linear memory also allows me to use an entirely untagged representation which has none of the above problems. A language front-end may well have strong enough type information (either statically or in auxiliary data structures) such that it always knows what a particular memory location contains, but it dynamic enough in how values are assigned to memory locations that it cannot convey that information in wasm's managed typing system.

[rossberg]

@aardappel, there clearly are trade-offs. But it seems impossible to avoid them. The idea is that with a sufficiently high-level enough abstraction producers could rely on engines doing a sufficiently good job on all architectures. For example, they might use NaN-boxing on 64 bit archs. The spec could state some conditions under which e.g. it is guaranteed that a certain operation is always fast.

The alternative would be that every producer has to make a choice ahead of time. That choice will likely be inefficient on all but one class of architectures.

FWIW, rolling your own in linear memory has similar issues. Currently, we only provide a 32 bit address space, more or less emulating a 32 bit architecture, so you don't even have much choice. But even if we added 64 bit address space, a producer would still be forced to choose one -- and thereby effectively a word size, which will result in a less than ideal data representation on mismatching hardware.

[bvibber]

64-bit NaN-boxing in wasm32 linear memory seems to work ok though I haven't explored all the performance characteristics. Even with 32-bit addressing you get native 64-bit loads, stores and bit-ops, and once you verify the tag for a pointer you can i32.wrap/64 to get the 32-bit pointer so it ought to perform reasonably.

But it would be nice to make use of native GC to avoid worrying about memory fragmentation and stuff...

A possibility is to represent dynamic variable bindings as indexes into two parallel lists: one array of i64s (in linear memory or a GC'd array) containing tagged values, and the other an array of object references. When reading a value not already known to be an object, read its i64 tagged value, and if it has an object tag, pull the corresponding ref from the object array.

The clear downside is that you're eating extra memory because you can't alias the reference into the tagged value, and reads of object refs mean two loads instead of a load + bitop. Function-local bindings could push/pop on a stack to avoid allocating the list frames on the heap, at least.

[bvibber]

(Or now that I think of it, an array of structs with a tagged i64 and a ref should work versus two separate stacks, as long as you keep them out of linear memory. But either way, that brings us back to doubling the word size, and generally makes for awkward parameter passing.)

[tlively]

The current MVP has settled on containing some sort of i31 because we expect that to be the only numeric type that can easily be represented as a tagged pointer on hardware supporting Wasm. Closing this, but feel free to reopen if you feel more discussion is warranted.