Value types rather than int31

[fgmccabe]

An alternative to the i31ref would be to support 'value types' as well as 'reference types'.
Semantically, one of the differences is that instead of the tagged value determining that the value is 'flat', the owner of the reference would have to assert the type.
The big pay-off is a uniformity of representability of data types (the only required primitive type would be bit string(s))
You can reconcile value types with existentially quantified types - at the expense of a more elaborate system of allocating local variables.
My suggestion would be to supplement reference types with value types - I am not advocating C++-style specialization of generated code.

[rossberg]

A basic assumption of Wasm is that programs are lowered to the level of machine code as much as possible on the producer side. Language-level features like "value types" are hence assumed to be compiled away already and shouldn't require support from Wasm. (Although immutable structs are actually semantically equivalent to value types if reference equality is not available for them.)

I don't see how they address the same problem as int31ref, though. Since pointer tagging is the preferred technique for implementing GC in all existing Wasm VMs -- and AFAIK proven to be the most efficient technique in general --, the GC design has to allow for this implementation while still supporting unboxed integers in places where references are stored (see the discussion of polymorphism and uniform representation in the overview).

[titzer]

Another way to say this is that Wasm's design approach is to offer minimal mechanisms for high-level languages to compile to an abstract machine without (unreasonable) loss of performance. As such it exposes an abstraction that is an efficient reflection of today's CPU capabilities with minimal additional abstraction to make it safe (e.g. function boundaries, invisible callstack, indirect function tables, globals). For languages that implement polymorphism with a universal representation, like Ocaml, int31ref is pretty close to the minimal mechanism necessary to open up implementation techniques close to what these languages employ for native instruction sets. Wasm going "full ADT"--at least at this stage--is perhaps overkill, since this can be done by the language implementation. Since int31ref seems forward compatible with any ADT mechanism we might be tempted to add in the future, I think it makes sense.

[jdh30]

Andreas Rossberg wrote:

proven to be the most efficient technique in general

Perhaps we're talking at cross purposes but I'd have said the opposite: OCaml and Java are slow because they box types like float * float (e.g. complex numbers, 2D/3D/4D vectors and matrices) and (int * float) array (e.g. hash tables, vertex buffers) and OCaml is even worse because it boxes type like i32 (e.g. RGBA colors, PRNG state).

Some relevant benchmarks:

Hash table insertion on solutions using tagging (OCaml/Haskell) is 4-10x slower than on .NET (no tagging): http://flyingfrogblog.blogspot.com/2013/09/hash-table-insertion-performance-f-vs.html

Another hash table benchmark showed that the tagging solution (JVM) was 17x slower than the non-tagging solution (.NET) http://fsharpnews.blogspot.com/2010/05/java-vs-f.html

OCaml is ~3x slower than .NET on the Monte Carlo task (a PRNG) of the SciMark2 benchmark which uses 31- or 32-bit ints http://flyingfrogblog.blogspot.com/2009/01/mono-22.html

On a hailstones benchmark that requires 64-bit ints the solutions using tagging (OCaml/Haskell) are 7-32x slower than those that do not (F#/HLVM) https://groups.google.com/forum/#!msg/fa.caml/yg3p8Txk4_o/7hDNY6ObLrYJ

On the ray tracer benchmark the solutions using tagging (Java/Haskell/OCaml) are 1.4-3x slower than those that do not (MLton, HLVM, C++) http://flyingfrogblog.blogspot.com/2010/01/hlvm-on-ray-tracer-language-comparison.html

[aardappel]

Thanks, those are some interesting numbers.

Besides efficiency, to me the bigger reason why I don't see the point of a baked in int31 type is that I don't see it as that widely applicable. The amount of languages/systems/formats/protocols that specify an int as having exactly 32 (or 8/16/64/same_as_cpu) bits has to dwarf the ones that say it is implementation defined and can conveniently pick 31 without funny things happening to certain kinds of values.

That said, I guess I am not against a feature that helps certain languages but is neutral for others, if its usefulness is sufficiently widespread.

[RossTate]

i31ref is not own its own problematic for other languages, but having i31ref be a subtype of anyref forces all engines to use this packing scheme. This packing scheme is not the most efficient in general either; there are others that work better for languages with more complex numerical systems (e.g. common mixing of integers and floats).

[rossberg]

@aardappel:

The amount of languages/systems/formats/protocols that specify an int as having exactly 32 (or 8/16/64/same_as_cpu) bits has to dwarf the ones that say it is implementation defined and can conveniently pick 31 without funny things happening to certain kinds of values.

As I discussed before, this is missing the point. We don't provide it for the purpose of exposing it in a source language. We provide it so that producers can use the very common implementation technique of (predictably!) unboxing small integers when compiling to GC types. The vast majority of implementations of dynamic or polymorphic languages rely on this -- I think you happen to be working on one of them. ;)

@RossTate:

having i31ref be a subtype of anyref forces all engines to use this packing scheme.

I don't see how it does. An engine could still use a different scheme. Though there are reasons why so many GC'ed runtimes use pointer tagging.

[RossTate]

Here's a packing scheme we found worked really well for our language we just developed: if the low bits are 00, it's a ref; if they are 11, it's a signed integer constructed by bit-shifting right 2 bits and preserving the sign (with other signed integers represented using a ref); otherwise it's a (single word) float constructed by bit-wrapping right 3 bits (with other floats represented using a ref), unless the high 30 bits are 0 in which case it is constructed by big-wrapping right 2 bits. The reason for the float-packing design is that it is fast to pack and unpack and it ensures that all 32-bit floats representing numbers whose exponent's absolute value is small are packed. This enabled us to perform well on both integer-based numerical benchmarks and float-based numerical benchmarks rather than favoring one or the other (and of course there's a 64-bit version of this packing scheme as well).

How do you propose that my 32-bit engine use this packing scheme and support i31ref with the performance expectation that 31-bit integers be packed rather than boxed? What about the various packing schemes that rely on having references be 8-byte aligned and so can use the lower 3 bits for tagging? What about packing schemes in which the lower bits are used to distinguish between different types of references, such as using a bit to distinguish interior references so that the gc knows to walk it differently?

[rossberg]

@RossTate, that sounds like a plausible scheme for a native implementation of a specific language, but I think I'm missing how that matters for Wasm. How would a Wasm engine benefit from such a scheme? Custom tagging or packing schemes would perhaps be nice for certain producers, but there is no way that Wasm could expose a mechanism for that to producers in a platform-neutral manner.

FWIW, extra tagging bits are compatible with i31ref. Bit 0 tells you whether it's an int or not. If not, it's a pointer that can use the next couple of bits for tagging, as alignment allows. V8 is one engine using this scheme (or once did).

[steveblackburn]

FWIW, we believed a tagged reference was important for the Mu micro vm (which has similar objectives to Wasm). We have tagref64, which is tag union of:

• double,
• int<52>,
• ref<void> and int<6>

See the 'Tagged Reference' in the Mu spec or 5.2.4 of Kunshan's thesis.

[RossTate]

Ah, so you found nan boxing was a better packed representation than a simply bit flag. I suspect nan hacking wouldn't do so well in the 32-bit setting, but that's just a detail. The important thing is that both general-purpose virtual-machine engines and specialized language implementations have found it worthwhile to pack floating-point numbers at the expense of reducing the number of integers that can be packed. This is how a wasm engine could benefit from my scheme (to answer your question). It is plausible that wasm has some special properties that make that not the case, but wasm's implementation strategies certainly have not been explored enough at this point to know that, so adding something like i31ref that will make those other packing strategies difficult seems premature.

FWIW, extra tagging bits are compatible with i31ref.

As for using i31ref to do these sort of packing tricks at the source level, the 31-bit representation is not always appropriate, and wasm doesn't always offer the low-level operations. For my example, both issues apply. On x86, an engine could unpack from my scheme by simply masking to get the lowest 2 bits, branching on the zero flag for the reference case, branching on the parity flag for the integer case (then sign-preserving shifting right 2 bits), and then falling into the float case (and rotating right 3 bits). But in wasm, the packing and unpacking process has to use a single bit to indicate whether the exponent started with 01 or 10, and this forces unpacking within the float case to either branch yet again (within just the float case) or use 2 additional registers to store the necessary intermediate values to achieve the result through bit-level instructions.

And all of this complexity is pointless if the wasm module happens to be executed on a 64-bit machine, in which case many packing schemes can easily store a full 32-bit integer.

So i31ref is simply at the wrong level of abstraction to a) be compatible with established packing schemes, b) be useful for a wide range of languages, and c) adapt well to various architectures (especially 32-bit vs. 64-bit).

[rossberg]

@steveblackburn, that's interesting. So this is another type in the spirit of i31ref, fixing on a specific encoding. That could be a post-MVP feature. We actually discussed the viability of such a type in the past. There are some issues for Wasm, though: such a type won't easily work on 32 bit platforms, and Wasm requires strict portability; (2) injection into such a type would be lossy for f64, and Wasm elsewhere guarantees to maintain all its bits. Also, we weren't aware of many impls using NaN boxing in practice, it seems to be interesting primarily for languages like JavaScript, where floats are the only number type (and even there most engines don't use it). Are you aware of other interesting examples?

@RossTate:

The important thing is that both general-purpose virtual-machine engines and specialized language implementations have found it worthwhile to pack floating-point numbers at the expense of reducing the number of integers that can be packed. This is how a wasm engine could benefit from my scheme (to answer your question).

Not sure that answers my question. ;) Concretely, which Wasm reference type would be represented as an unboxed float, and how would you make its performance predictable?

And all of this complexity is pointless if the wasm module happens to be executed on a 64-bit machine, in which case many packing schemes can easily store a full 32-bit integer.

You are fixated on int32s, but that misses the point of this type, which is completely unrelated. It isn't meant to map native integer types from a source language. Nor is it limited to mapping integer types in the first place. Instead, a producer can use it for the representation of a broad range of scalar types, like booleans, enums, characters, small integers, etc. For these, they don't care whether the max range is 32, 31, or 28 bits, they are smaller anyway. But they do care that they are unboxed. So 31 bit is indeed a somewhat arbitrary choice, but we have to pick some portable max range, and it's the most common one by far.

So i31ref is simply at the wrong level of abstraction to a) be compatible with established packing schemes, b) be useful for a wide range of languages, and c) adapt well to various architectures (especially 32-bit vs. 64-bit).

Agreed with (a) on a more philosophical level, but I still haven't heard a suitable alternative given Wasm's portability constraint! Strongly disagreed with (b) and (c), see above.

Why not be concrete: What would be your counter proposal for supporting portable unboxed scalars under the Wasm GC proposal?

[jdh30]

Why not be concrete: What would be your counter proposal for supporting portable unboxed scalars under the Wasm GC proposal?

Does Wasm need to support dynamic linking or could it assume whole-program compilation? If the latter, types are known at compile time and there is no need for any boxing or tagging.

[sabine]

@jdh30 what is the downside of the .NET approach, i.e. for what kind of code is the OCaml tagging strategy faster than .NET? (Or does the OCaml strategy, generally, just consume less memory at the cost of being slower? Or does the OCaml strategy enable something that is not possible under the .NET garbage collector?) I'd really like to understand how the .NET GC works.

@rossberg I believe I understand this: We need i31ref as an escape hatch.
One problem, that this escape hatch can be useful for, is the inability to have a uniform representation of values for polymorphic functions (of ML-style languages) in the presence of typed WASM heap structs. Reason being that we can't easily compile a polymorphic function to a single WASM function if we need to provide types for every type (and all the combinations of types, if a function is polymorphic in more than one argument) our polymorphic function could be passed values of.
So, instead of compiling a polymorphic function to multiple WASM functions (which ones we could only discover by looking at the program as a whole, no longer on a per-module basis), one would use the anyref type together with explicit type casts to get a uniform value representation on the heap. Now, the polymorphic functions can operate on anyref arrays and the problem is solved, there is only a single, uniform type for values.
Except that the problem is not actually solved yet because the anyref type is only for references and ML-style uniform value representations also contain primitive values, and not just references to other heap blocks. Thus, in order to be able to store values other than references inside an anyref array, there is the proposed i31ref type that is a subtype of anyref and that one enables typecasting 31-bit integers to anyrefs forth and back.
And, I suppose, the argument continues that, since browsers do use tagging of primitive values already in JavaScript, exposing this via i31ref isn't a big deal (at least for the browsers).

This is my current mental model, I am not an expert at any of this, please try to correct where I am just plain wrong. Also, feel free to drop links to papers or anything that someone who wants to understand this should study.

[wingo]

@sabine Not sure if this answers a concern, but for what it's worth, it's perfectly possible to use anyref to get tagged integers into a program. Schism does this, for example; e.g here's a declaration of a make-number import, and here's the definition. There's no extra allocation overhead relative to i31ref.

Problem is, you have to call out to the runtime to do type predicates and to tag/detag the value. The i31ref proposal effectively allows us to pull those predicates / constructors / accessors into WebAssembly, and to use the type system to eliminate some run-time type checks that you have to do if you have a uniform value type.

[rossberg]

@jdh30:

Does Wasm need to support dynamic linking

Yes, absolutely. Furthermore, whole-program monomorphisation approaches cannot handle first-class polymorphism or polymorphic recursion anyway, which are common today.

@sabine, yes, that's right. Uniform representation is one important motivation for tagging schemes. That is not at all specific to OCaml, but used by many or most dynamically or polymorphically typed languages. The approach used by .NET is the only expressive enough alternative, but it is waaaay more complicated (in Wasm, it would require dynamic generation and compilation of Wasm code, i.e., shipping a Wasm code generator with your web page), and the type passing involved can also become a significant cost.