gc 🚀 - Alternatives to i31ref wrt compiling parametric polymorphism on uniformly-represented values (OCaml)

Although you've ruled it out, I would actually suggest (4) for OCaml, albeit with some optimization.

First, the optimization I have in mind is to have OCaml function definitions operating on int compile to wasm function definitions operating on i32. For polymorphic uses of these functions, have another definition that works on whatever "uniform" representation of OCaml values you use, simply calling the optimized function with appropriate (un)boxing. Or more generally, when a value can be statically determined to be an int, represent it as i32.

There are a few reasons I suggest this:

A number of other languages have found this approach effective enough. See various JVM languages like Java, Kotlin, and Scala that all take this approach.
It's still possible the MVP will have i31ref. It's also possible it'll instead have something like i32ref, which would generally be boxed on 32-bit machines and unboxed on 64-bit machines.
Even if the MVP doesn't have these things, the MVP is just the first release. WebAssembly will advance, possibly in ways that would make specifically 31-bit integers often (if not always) be unboxed for modules that specifically request it.

So in short, I suspect the short-term costs of this approach are more acceptable than you might expect (with some local/composable optimization techniques), and I suspect it is more likely to adapt well to integrate the improvements that will be made to WebAssembly over time.

There's also a meta-point to consider: having WebAssembly modules compiled from OCaml in this manner will give the CG realistic programs to experiment with and analyze, which can be used to determine if it's worth the effort (at all levels of the process) to give modules more control over their low-level representations. Right now we can only hypothesize.

That all said, you know your specific needs much better than I, and even if this approach might work well for the OCaml community broadly, it still might not be well-suited to more specialized concerns you might have.

RossTate on 27 Jun 2020

👍1

Fair enough, (4) is close enough to (1) to look like the next best solution in terms of effort needed and we could use i32 arithmetic. I'll look into this in more detail to see if it is indeed so straightforward.

sabine on 28 Jun 2020

😄1

I'm wondering if I can do this by first compiling to "WASM GC MVP with i31ref" and then translating that code to "WASM GC MVP without i31ref". At least, this way, I will not have to go all the way back to unbox all these integers again when a feature that is equivalent to 31ref arrives. Has anyone done that?

sabine on 28 Jun 2020

Even with i31ref, you have to coerce integers to and from i31ref using instructions i31.new and i31.get_u/i31/get_s. So, if the design of i31ref changes, it should be pretty trivial to change your compiler to substitute in the appropriate coercion instructions.

The more difficult thing to change would be using 31-bit vs. 32-bit arithmetic. It sounds like putting in the effort for 31-bit arithmetic is only worth it if i31ref exists. Since that's not guaranteed, I'd use easier 32-bit arithmetic for now, and then put in the effort to switch to 31-bit arithmetic only if/when i31ref has been finalized.

RossTate on 29 Jun 2020

@sabine:

Then, static code specialization kills one nice feature of OCaml: separate compilation of modules.

That would be the smallest problem. More importantly, as you note in your edit, static specialisation kills any form of first-class polymorphism, of which OCaml has plenty (polymorphic methods and record fields, first-class modules, GADTs, ...). So I think this approach is simply impossible to use. The same is true for any other language with a rich enough type system.

@RossTate:

For polymorphic uses of these functions, have another definition that works on whatever "uniform" representation of OCaml values you use, simply calling the optimized function with appropriate (un)boxing.

That is not a scalable approach. In languages like OCaml, you have polymorphic type inference, and by design that results in _way_ more polymorphism than in traditional languages. You also use lots of abstract types. In particular, many functions are polymorphic in multiple independent types, and refer to multiple abstract types. To be efficient, the approach you suggest would require an exponential number of specialisations to be generated upfront for each such function.

There also is the practical problem of porting. If the GC proposal does not support established implementation techniques, but instead requires a major rewrite of a pre-existing compiler and runtime, then it will not be a plausible target for many existing languages.

rossberg on 29 Jun 2020

The advice I gave here is specific to OCaml. There is only one type we were talking about doing this for: int. You can do these coercions per use site, and you can consolidate coercions if you want. These are conceptually coercions between monomorphic and polymorphic calling conventions. There will need to be coercions between curried and uncurried calling conventions anyways. That is, an int -> int -> int can and should be called with two arguments (i.e. uncurried), but it can also be given to of type (int -> 'a) -> int -> 'a, in which it must be called with one argument (i.e. curried). That polymorphic function will then return a function using a curried calling convention and so that result often needs to be coerced to an uncurried calling convention. That is, unless you are suggesting that all functions always use the curried calling convention, since WebAssembly does not currently support the sort of variadic arguments that would be necessary to eliminate these coercions. So my suggestion just hooks into infrastructure that would need to be in an OCaml-to-WebAssembly compiler anyways.

RossTate on 29 Jun 2020

There has been a good amount of research work on type-directed or shape-directed unboxing, supported by code specialization. For a recent example, see the work on call-graph-based specialization of (boxed) polymorphic functions as part of the 2017 thesis of Dmitry Petrashko on Scala. But these work typically require a fair amount of sophistication. In contrast, having an efficient way to "box" immediate scalars without going through the heap is easy for backends to allow, and fairly easy to compile into for types that fit the smaller width. The two approaches are complementary (clever specialization optimizations has other benefits), and yes, boxing everything is of course possible if the low-level substrate does not provide better, but getting reasonable performances requires much more sophistication on the user side.

Many of the successful language implementations work by keeping a tight check on their complexity budget: they go for the 20% of sophistication that brings 80% of the benefits in as many areas as possible. OCaml was faster than most ML, or Chicken Scheme than most Schemes, not through extremely optimizations, but rather thanks a few very-important optimizations (static function calls) and good data-representation choices that ensured that typical programs were fast by default.

It is also possible to build fast systems that are slow by default but fast through excellent, sophisticated engineering (good JVMs or CLR implementations, GHC, Graal+Truffle, etc.), but I agree with @rossberg that it is important to ensure that the 20%-80% approaches are available first.

gasche on 29 Jun 2020

The issue is "alternatives to i31ref", and the concerns are fairly specific to OCaml due its use of specifically 31-bit arithmetic. (Haskell, for example, only guarantees 30-bit precision because they have found reserving 2 bits for GC to be useful.) There is already another very long thread, #53, about i31ref. Let's not pull this thread into an argument about i31ref, an argument that cannot be conducted well if we have not even considered the alternatives, which is what this thread is about.

RossTate on 29 Jun 2020

Consider a function like this one from the Map interface:

val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t

This is polymorphic in two type variables and two abstract types. Each of them could either be an integer or something else. So even with just int, that makes 2^4 = 16 different ways in which you'd have to specialise the code according to your suggestion (8 if the compilation scheme allows to fix the export type t).

Or you reduce the number of specialisations, lump several dimensions together, and pay the extra cost of frequent boxing/unboxing conversions for the rest. Many variations of this have been investigated in highly polymorphic languages, and there are reasons few are used in practice. Leroy (among others) actually had a line of papers researching unboxing for polymorphic languages, yet OCaml, like many similar languages, uses a uniform representation instead. He observed that the conversion overhead often is higher than the benefit of unboxing, and that a minimal unboxing scheme produces better results for typical profiles.

I'm not intimately familiar with how OCaml's native code compiler handles currying, but the byte code compiler handles it through clever dynamic stack techniques that are unrelated to compile-time unboxing.

rossberg on 29 Jun 2020

the concerns are fairly specific to OCaml due its use of specifically 31-bit arithmetic.

No, they're not, and it's getting a bit boring at this point that I have to keep refuting that. So again: plain ints are just one particular use case. The general purpose is unboxing small scalars of any sort, for which there are many, many use cases, in many, many languages. (And of course, 30 bit ints would fit just fine as well.)

rossberg on 29 Jun 2020

As a bystander who follows these threads I wanted to share some feedback that this aggressiveness is quite off-putting.

jayphelps on 29 Jun 2020

but the byte code compiler handles it through clever dynamic stack techniques that are unrelated to compile-time unboxing

Unfortunately, WebAssembly does not support these techniques. So I believe coercions will be necessary instead. @sabine, have you considered this problem with currying?

To clarify, I was not suggesting specializing polymorphic functions based on their type arguments. I was suggesting coercing monomorphic functions that work specifically on integers to polymorphic functions operating on the uniform representation (when used polymorphically). This could be done with an augmentation of the coercion system I was suggesting above for dealing with currying.

RossTate on 29 Jun 2020

To clarify, I was not suggesting specializing polymorphic functions based on their type arguments. I was suggesting coercing monomorphic functions that work specifically on integers to polymorphic functions

Oh, okay, but that's probably even worse. You would have to box/unbox in all first-order contexts where you pass a value from polymorphic to monomorphic functions and vice versa, which is like all the time. And you'd still have the same problem: for a function of type int->int->int, there are 8 different possibilities of a polymorphic context to which it could be passed in a higher-order fashion. All would have a different calling convention under the approach you suggest. So either your function has 8 different specialisations, or you're creating wrapper functions at each polymorphic use site.

rossberg on 29 Jun 2020

@sabine thanks for summarizing things so clearly.

First, until we invent JIT and other features, the current Wasm, even when including the current GC proposal, is an entirely static, dare I say "closed world" system, with AOT compilation to a single .wasm, with concrete types at the boundary. By definition, all forms of polymorphism, modularity, separate compilation etc will be resolved by the time that .wasm gets baked, no matter what the language likes to present beforehand. This alone should make (5) by far the most realistic option for most languages that care about speed, again, in the current way Wasm works.

There seems to be a lot of default fear of (5), that it going to result in unreasonable code bloat. If you generate specializations under a closed world assumption, you only generate the ones that are actually used. This causes more in-lining of single-use functions (not further increasing code size) followed by much more aggressive optimisation of inlined code working directly on specific naked (scalar) types, often shrinking the code back down significantly. It turns indirect calls into static calls, helping greatly with dead-code elimination. LLVM and binaryen can do endlessly more on code like this than code that stays generic. In my personal experience working with (5) a lot, the amount of code bloat can be remarkably small, and the resulting speedups due to code "collapsing" impressive.

But @rossberg is correct that anyone that prefers (5) can make this happen, regardless of the presence of i31ref. So why would we want i31ref additionally?

I'd like to see an example of polymorphism that is impossible to compile down to specialized code using (5), and _requires_ a struct of all anyref to work. I think, by definition, that such an example does not exist (given that we don't have any dynamic code features in Wasm that would make this statically impossible).

There will be people who have code size as their #1 concern, and don't believe my story above that it can actually help reduce code size, when done right. That's fine, because it is hard to make claims about this in the absence of specific languages with specific compilers and specific applications.

Finally, are there downsides to having i31ref when you don't use it? Under what circumstances does a Wasm implementation have to check "is this thing an i31ref?" before accessing a pointer? If anyref is always a pointer, always pointing to a heap object where the initial bytes always have the same layout (e.g. a type id), I can imagine that would lead the speedups. If indeed there are frequent checks required for i31ref, that to me would be the strongest reason to not wanting to have it.

aardappel on 29 Jun 2020

@aardappel, repeating what I pointed out above, and I believe many times before: static type specialisation _does not work_ in a language with first-class polymorphism or polymorphic recursion.

Simplest possible example in OCaml:

type poly = {f : 'a. 'a -> unit}
let g {f} = f 1; f "boo"

There is no way you can statically specialise anything here, since you don't know what polymorphic definition you are calling. It's completely dynamic. A client of g could pass anything for f, it could be taken from a list, or any dynamically computed data structure. Inversely, the site defining an f generally has no way of knowing where it flows and what types it will be used at.

The same is true for generic methods in a language like C#, which is why the CIL performs jit-time type specialisation. And it is the reason why C++ does not allow "template virtual methods", because its simplistic compilation model cannot support them.

Static specialisation also does not work in a language with polymorphic recursion, because the set of instantiations can be statically unbounded.

If I could make a wish, then that folks in these discussions could accept the fact that there are very good reasons why certain classes of languages are implemented in certain ways, that there has been decades of engineering and research into it, that we are not smarter than all the many folks who did this, and that we need to support a mapping for those compilation techniques instead of hoping for some yet undiscovered trick to make these requirements go away. Please?

rossberg on 29 Jun 2020

❤3

First, until we invent JIT and other features, the current Wasm, even when including the current GC proposal, is an entirely static, dare I say "closed world" system, with AOT compilation to a single .wasm, with concrete types at the boundary. By definition, all forms of polymorphism, modularity, separate compilation etc will be resolved by the time that .wasm gets baked, no matter what the language likes to present beforehand

I'm confused, doesn't wasm allow producing modules and linking them together? I would expect compilers to use those to produce modules at the natural separate-compilation granularity of their source language. In particular, I would expect to compile each module/crate/package separately, without making assumptions on how other modules are going to use it. Of course you can still generate WASM code only after a pass of link-time-optimization, but I would naively expect that it can lead to code-distribution issues (if the generated WASM for my library depends on the clients it's compiled with, code caching etc. is going to be more delicate to handle).

I'd like to see an example of polymorphism that is impossible to compile down to specialized code using (5), and requires a struct of all anyref to work.

It's easy to have examples where specialization leads to impressive blowups in code size. I mentioned the Scala specialization work by Dmitry Petrashko earlier; it starts by evaluating previous 2014/2015 work on call-graph-based type specialization in Scala on the codebase of the Dotty compiler, and found out that on average each method would be specialized 22 times.

Then there is the example of polymorphic recursion, where the set of different type instantiations depends on runtime data (it particular it may be arbitrarily large). (In most cases I'm familiar with, the number of different "shapes" may be bounded, especially if you only distinguish immediates vs. pointers.)

But then what about union types? Many language runtimes use representations that are either an immediate word or a pointer, with tagging to distinguish the two. This is ubiquitous for example in implementations of ML, Haskell, Scheme and what not. You can very easily have tuples or arrays of such immediate-or-pointers values, where the immediate-or-pointerness of any element is only known at runtime and can change on mutation. How would one operate on this data if functions are expected to know statically whether they take an immediate or a pointer value?

Under what circumstances does a Wasm implementation have to check "is this thing an i31ref?" before accessing a pointer? If anyref is always a pointer, always pointing to a heap object where the initial bytes always have the same layout (e.g. a type id), I can imagine that would lead the speedups.

I'm not very familiar with Wasm (I was drawn into this discussion by chance), but I believe that:

programs using int31ref would need to check for it when they know it can happen; this does not affect the performance of programs not using this type
the Wasm GC would need to check int31ref before following a reference (because in this case it's not a valid pointer); checking one bit of a word is practically free compared to dereferencing the word as a pointer
someone willing to propose runtime operations operating on any wasm value (serialization, etc.) would do similarly need to check for int31ref on anyref values; again this is extremely cheap

If I understand correctly, Wasm implementations try to be safe from undefined behavior, so in particular they are careful to check that pointers go into allowed memory before dereferencing them. This monitoring discipline, and in general wasm sandboxing/CFI features, are going to completely drown out the cost of checking bitpatterns on a word (even if you decided to do checks or masking on each dereference).

gasche on 29 Jun 2020

@rossberg your example is essentially a function pointer to a generic function if I'm not mistaken, which is indeed not possible in languages that rely entirely on monomorphic specialization. I'd expect a compiler to choose to force boxing on args for such functions (causing an extra heap alloc for f 1).

I don't see why generic functions that are _not_ used in this very dynamic fashion (which I would certainly hope are the vast majority) should suffer from the mere presence of this possibly very dynamic use, and certainly not why Wasm as an eco system should pay for this cost (if the mere presence of int31ref introduces conditionals). I'd hope the cost to only be born by functions that use this functionality.

I am well aware that there are endless people who spend longer time looking at this than me, but just an "appeal to authority" is not going to be sufficient to stop me from at least questioning this direction.

aardappel on 29 Jun 2020

If I could make a wish, then that folks in these discussions could accept the fact that there are very good reasons why certain classes of languages are implemented in certain ways, that there has been decades of engineering and research into it, that we are not smarter than all the many folks who did this, and that we need to support a mapping for those compilation techniques instead of hoping for some yet undiscovered trick to make these requirements go away. Please?

The Glasgow Haskell Compiler, which presumably is considered a production compiler within this class of languages, does not unbox Int even though the Haskell semantics specifically permits Int to have only 30 bits (a number they arrived at because other runtimes that do unbox Int found it useful to reserve two bits for GC). From what I understand, they did so because they found that algebraic operations were so common that it was more useful to embed the algebraic-constructor tag in the low bits of the pointer. So the experience of Haskell developers is that either custom pointer tagging should be preferred over i31ref for better performance or i30ref should be preferred over i31ref for better GC strategies. Having looked through a number of language implementations, this sort of gap seems pretty common. Unfortunately for OCaml, it is an outlier because I believe it is the only language anchored specifically around 31-bit integers. This is why I thought it would be useful to focus specifically on advice for OCaml.

RossTate on 29 Jun 2020

@gasche

I'm confused, doesn't wasm allow producing modules and linking them together? I would expect compilers to use those to produce modules at the natural separate-compilation granularity of their source language.

Yes, but the types at the edges are currently very basic types that may well not make it possible to express the full set of type feature of a language like ML, meaning separate compilation would only be "safe" if compiled from one version of the program, essentially not making it separate compilation anymore. This may change in the future but is TBD. Also, current linking of multiple Wasm modules is runtime-only, though static linking is planned.

and found out that on average each method would be specialized 22 times.

Average? Each method in the entire compiler? Meaning many methods would be specialized hundreds of times? (to account for the methods only used once). I find that hard to understand how that is possible. Does this account for optimization and DCE of the now much more static blown up code?

Would be more useful to know how much a codebase would blow up in total, for example the ratio of AST nodes of a large program before and after specialization. In my tests for example, in cases with heavy nesting of higher order functions, that ratio was at most 2x (after optimization). All very anecdotal of course.

If I understand correctly, Wasm implementations try to be safe from undefined behavior, so in particular they are careful to check that pointers go into allowed memory before dereferencing them. This monitoring discipline, and in general wasm sandboxing/CFI features, are going to completely drown out the cost of checking bitpatterns on a word (even if you decided to do checks or masking on each dereference).

An anyref is entirely under the control of the Wasm implementation, thus typically would need no checking of any kind before dereferencing as a pointer. Checking its bits, and potentially branching (and maybe missing) would be an entirely additional cost int31ref would bring. So no, not quite for free.

(sandboxing is only done for linear memory pointers, but even there it has no cost typically due to use of memory mapping features)

aardappel on 29 Jun 2020

@aardappel:

I don't see why generic functions that are not used in this very dynamic fashion (which I would certainly hope are the vast majority) should suffer from the mere presence of this possibly very dynamic use

You don't know at its definition site which polymorphic function ends up being used that way, and with what degree of polymorphism. The composition can happen somewhere else entirely, e.g. in a different module. And it can be partially instantiated, i.e., you plug in a polymorphic function somewhere where a less polymorphic (but not monomorphic) type is expected. There are many degrees of freedom, and you generally need a compilation scheme that is both efficient and compositional for all of them.

In the limit, the possibilities for polymorphic composition are almost similar to those in a dynamic language, which is why they make similar representation choices. (Though an important difference is that there usually is no observable type dispatch, because polymorphism is fully parametric.)

@RossTate:

As I have stated many times before, whether it's i31 or i30 is largely immaterial. This is an internal _representation type_. For the vast majority of use cases its max size doesn't matter. However, we can't easily make extra pointer bits available to user space across engines anyway, so AFAICS, we can just as well provide 31 bit range for tagged ints. But if there are reasons to pick another width, then that's totally fine as well. I just haven't heard them yet.

There are many languages that use (wordsize-1) bit integers in their implementations one way or the other. Whether a language implementation exposes that to users is a completely separate question. Some do (not just OCaml), some also expose values like 30, 29, or 28. But where they do, the language definition typically does not guarantee an actual size. For example, OCaml explicitly states that int_size can have other values. So again, size doesn't matter.

@aardappel:

Yes, but the types at the edges are currently very basic types that may well not make it possible to express the full set of type feature of a language like ML, meaning separate compilation would only be "safe" if compiled from one version of the program, essentially not making it separate compilation anymore.

Huh? I'd fully expect that a language with a proper module system can (and should!) compile its modules to Wasm modules separately, and without any loss of generality. Wasm's module system allows you to import/export anything, so such a compilation scheme should be perfectly possible.

An anyref is entirely under the control of the Wasm implementation, thus typically would need no checking of any kind before dereferencing as a pointer. Checking its bits, and potentially branching (and maybe missing) would be an entirely additional cost int31ref would bring. So no, not quite for free.

You can't deref an anyref. You first need to cast it to something concrete. That necessarily involves a check, with or without i31ref.

rossberg on 30 Jun 2020

Checking its bits, and potentially branching (and maybe missing) would be an entirely additional cost int31ref would bring. So no, not quite for free.

You can't deref an anyref. You first need to cast it to something concrete. That necessarily involves a check, with or without i31ref.

That is indeed the one place where adding i31ref has a non-zero cost: when ref.test or ref.cast or br_on_cast operate on a value that's statically typed as anyref or eqref, then before loading and comparing that value's type descriptor, they first have to check the pointer's tag bit. Given that the type descriptor check (which needs to happen with or without i31ref's existence) involves a load from memory, and the tag bit check doesn't, I'm confident that the additional overhead is negligible.
Any code that has more specific static knowledge than eqref is entirely unaffected by the existence of i31ref. Code that passes around anyref values (without downcasting them) is just as unaffected.

jakobkummerow on 30 Jun 2020

👍1

As a bystander who follows these threads I wanted to share some feedback that this aggressiveness is quite off-putting.

I don't think anyone contributing here wants to come off as aggressive (I certainly don't want to :smile:). This i31ref part of the spec is a rather controversial issue in both a technical and political sense:
(a) WASM is this great thing that everyone wants to be part of and that, by aiming for strong safety guarantees, sets the bar quite a bit higher for everyone, compared to the commonly-used traditional architectures that we are used to.
(b) so, all kinds of different people are coming together. Many people (language implementers, engine implementers) are coming here with existing codebases. When looking at compiling to WASM or implementing WASM, we discover choices in our codebases that make it difficult to work with WASM. Some things that were before considered acceptable in the existing codebase now present as technical debt. Some choices are very fundamental to the codebase and it is not immediately obvious whether or even how we can undo and rework the codebase at a reasonable cost. So we all try to understand how to work with the spec in a way that is maintainable in the long run.
(c) all involved here care deeply about performance. With WASM being a melting pot for all kinds of languages, none of the language implementers can expect to get a WASM that caters optimally to all concerns of their language (or, for that matter, a WASM that is trivial to compile to). There are so incredibly many constraints and requirements coming from all the languages overall. Still, we consider reasonable tradeoffs in performance worth it in the overall scheme, the premise of being able to run code anywhere by compiling to WASM. One important task of WASM engine implementers is to watch over the specification and look for features that introduce unnecessary performance costs, while all the compiler implementers try to lobby for and ask for features that they can make use of (ideally, while keeping in mind the overall goal of making WASM an efficient compilation target for many languages). The goal here for WASM GC is to strike a balance between WASM GC being small and fast and providing the expressivity that makes it a reasonable compilation target.
(d) resource constraints matter for all of us. Decisions need to be made and we all need to put only so much on our plates that we can still handle that and get something done. I appreciate very much that WASM is not some huge gigantic beast, but a rather compact language whose specification can be read and mostly understood in a very short time.

I'm trying to summarize and sometimes comment on some of the points brought up. If you feel that I missed your point or something needs clarification, do speak up.
@rossberg says that _first-class polymorphism, of which OCaml has plenty (polymorphic methods and record fields, first-class modules, GADTs, ...) makes it impossible to do static code specialization to the point WASM GC without i31ref requires_. OCaml compiler implementers that I asked seem to share this idea and provided some hard-to-monomorphize examples. I know too little about all the features of OCaml at this point (I have been working with the compiler only since September part time and I still have a lot to learn.) to say whether full-program monomorphization is possible or not - I do not have a proof for either of these hypotheses. @rossberg do you know good papers or theses on this topic?
@gasche says that _type-directed or shape-directed unboxing, supported by code specialization is a fairly sophisticated technique for compilers to implement, while, in contrast, having an efficient way to "box" immediate scalars without going through the heap is easy for backends to allow, and fairly easy to compile into for types that fit the smaller width_. I agree with your assessment, that OCaml, in particular, chose to go with not many optimizations by choosing a memory model that brings 80% of the performance to be expected to the table. The implicit assumption that the memory works this way, that you can put an unboxed integer into a memory cell in a heap block is being relied on in large parts of the compiler (in particular those parts where enough optimization has been done in order to make them a worthwhile starting point for compiling to WASM).
@aardappel says _There seems to be a lot of default fear of (5), that it going to result in unreasonable code bloat_. Looking into MLton, I believe now that code size with monomorphization is likely not the major problem, as the bloat is also offset by the ability to do dead-code analysis in a whole-program compiler.
@gasche says _Many language runtimes use representations that are either an immediate word or a pointer, with tagging to distinguish the two._ Indeed, we have the same representation in OCaml. type t = X | Y of int is a type that has two variants, X and Y. The variant X, which has no additional data attached, is represented as an integer, while Y is represented by a heap block with a field (tag) that says it's Y and another field that holds the attached integer value. This representation is introduced so early in the compiler that we do not have the information to undo it at a later in the compilation pipeline where we could branch off to WASM with reasonable implementation cost. I could call this either "technical debt" or a natural consequence of the choice of memory model permeating the whole compiler. There are people from the OCaml compiler team who believe that it should be possible to rewrite the compiler to introduce a different memory representation for variant types, but it will require a lot of effort.
@rossberg says that _WASM should support a mapping for fundamental compilation techniques of polymorphic languages_. As someone who wants to bring OCaml to WASM, I'm obviously very much in favor of that. In contrast, @aardappel sees WASM GC MVP as a target aimed at languages that can compile via static code specialization. Which, by looking at all the parts of the spec apart from i31ref seems mostly true.

Concerning the topic of separate compilation of modules: So far, we are not aware of any problems with separate compilation of modules for OCaml, in the presence of i31ref. Obviously, in a MVP compiler backend, to a MVP language running on MVP engines, only modules compiled with the same compiler version will be compatible. That's perfectly fine. No complaints whatsoever here. :smile: Users will understand.

To get back to the topic of alternatives to i31ref: When I think of an alternative to i31ref, I think of something that enables by some means a memory model that allows us to, with reasonable efficiency,
(1) store heap pointers and integers in the same array and read them back out
(2) in a way that we can, at runtime, check whether a value is an integer or a heap pointer
so that we can write a compiler backend for the OCaml compiler that compiles to the WASM GC MVP with the resources we have at hand.

Traditional hardware architectures have a memory model that lets us fulfill these requirements by pointer tagging integers at the cost of losing one bit on the integer representation - but there may be other reasonable alternatives that I don't see right now, that work for us, and that other languages could make better use of than i31ref. Possibly the alternative can live outside of WASM GC MVP, but I am not sure about that at all. If there was some external tool with a memory model that fulfills (1) and (2) and that compiles to WASM GC MVP, with a long-term expectation of reasonable performance, we could work with that. I don't know how that could work, though.

I believe that these two requirements are all that we need in order to compile all the crazy polymorphism in OCaml. I think @rossberg is right that, OCaml, in the long term, can work with 30-bit integers or 31-bit integers, or even, crazy as it may seem, 29-bit integers.

Requirement (2) can possibly be lifted after a major refactor of the OCaml compiler (which is not 100% guaranteed to succeed, and that we don't have resources for right now, but at least there are people optimistic that it could work).

Having both requirements (1) and (2), it looks to me like I need to double-box integers in a MVP without i31ref. I'll elaborate on that later.

I'm very interested in other languages who would use i31ref to compile polymorphism (no matter whether the language is dynamically or statically typed). Even more so, I am interested in the perspective of languages who need to compile extensive polymorphism but do not see i31ref as useful, needing something else. Please comment and describe your constraints for the memory model.

However, I expect that as soon as i31ref makes it to the implementation stage, people will start asking for i63ref.

sabine on 30 Jun 2020

👍5 ❤1

Thanks for the great post, @sabine!

I think @rossberg is right that, OCaml, in the long term, can work with 30-bit integers or 31-bit integers, or even, crazy as it may seem, 29-bit integers.

I was just about to ask you this question, so thanks for beating me to it! This is extremely useful, as it's the kind of perspective we can only get from language implementers.

Can I ask you for some more of your perspective along this line? Something I've been wondering is that, if we do change the number of bits for guaranteed-unboxed integers, what's a non-arbitrary number to change it too? The number that comes to mind is 24 bits because that's 3 bytes (so just enough for RGB and a little more than enough for some Unicode encodings). So I'm interested to hear specifically your thoughts on whether that would work for OCaml? That is, do you know of any OCaml applications or implementation strategies that would suggest a useful lower-bound on the number of bits needed for unboxed integers?

RossTate on 30 Jun 2020

👍1

JS implementations faced a similar dilemma with the need to optimize simple integers. The dominant technique there seems to be nan-boxing; which in the language of i31ref would be equivalent to i52ref.
TLDR: the discussion becomes moot when we migrate (which we no doubt will) to 64bit wasm.

fgmccabe on 30 Jun 2020

@rossberg

You don't know at its definition site which polymorphic function ends up being used that way, and with what degree of polymorphism. The composition can happen somewhere else entirely, e.g. in a different module.

It is my assumption that if you compile down to a single .wasm, there comes a moment where with static specialization you can know the vast majority of these cases. If your default way of working involves completely independent compilation to separate .wasm files, then yes, you more often cannot, but then again you're kind of bringing this upon yourself.

You can't deref an anyref. You first need to cast it to something concrete. That necessarily involves a check, with or without i31ref.

I was thinking of engine code, like the GC traversing objects. And checks can be more or less expensive.

@jakobkummerow

That is indeed the one place where adding i31ref has a non-zero cost: when ref.test or ref.cast or br_on_cast operate on a value that's statically typed as anyref or eqref, then before loading and comparing that value's type descriptor, they first have to check the pointer's tag bit. Given that the type descriptor check (which needs to happen with or without i31ref's existence) involves a load from memory, and the tag bit check doesn't, I'm confident that the additional overhead is negligible.

That bit check may involve a missed branch, but yes, for code that doesn't use i31ref (which is what I'm concerned about) you'd never get a branch miss. Conversely, one could regard loading the type field to have no cost if the subsequent code is going to touch all the following fields anyway.

I'll take your word for it for now that cost will be negligible, though I hope at some point we'll have some numbers, particularly a real world GC benchmark (not containing any i31ref values) with bit checks turned on and off. I'm a big fan of the "you pay for what you use" principle, in Wasm, and all of computing.

aardappel on 30 Jun 2020

@fgmccabe

TLDR: the discussion becomes moot when we migrate (which we no doubt will) to 64bit wasm.

It's not just about how many bits we can fit in a pointer, it is also about whether we want to force the need to check these bits upon languages that don't need it (or languages that may need it, for code where it can be statically known that it's not needed).

64-bit wasm is mostly about 64-bit operands to linear memory load/stores, and thus larger linear memories, not much else. The size of an anyref would still be entirely an implementation choice, and in theory, an implementation could be using 32-bits to represent anyref even while linear memory is running in 64-bit addressing mode.

Conversely, does the GC proposal put some expected upper bound on the amount of GC objects that can be addressed? If this can be >2GB, then likely it must use 64-bit pointers internally, and we might as well use i63ref ? ;) That would not be great for any remaining 32-bit CPU architectures we want to run on, but it is certainly is strange (and wasteful?) that in practice, almost all i31refs will sit inside a 64-bit pointer.

Actually, even an i63ref on a 32-bit architecture is not that expensive, since if the bit says its a pointer, it can simply truncate without a further check. It doesn't even need to load the 2nd half from memory. So maybe we should go for i63ref, if we believe 32-bit platforms are becoming less relevant for Wasm as time goes on.

aardappel on 30 Jun 2020

@aardappel

Yes, but the types at the edges are currently very basic types that may well not make it possible to express the full set of type feature of a language like ML, meaning separate compilation would only be "safe" if compiled from one version of the program, essentially not making it separate compilation anymore.

One could make the same argument about separate compilation when linking is done at the assembly level, or LLVM level, or JVM bytecode level, yet those are things that implementations do in practice, because whole-program compilation is extremely inconvenient in various ways. When you generate code for a library into a module, you don't know what client modules you will be linked against, so it is hard to tell what specialized instances you need to generate. It is possible of course to design whole-program three-shakers to reduce code size by propagating whole-programmation about usage, and a common practice in some communities, but that does not remove the importance in practice of also having an open-world compilation model.

@RossTate

From what I understand, [GHC does pointer tagging] because they found that algebraic operations were so common that it was more useful to embed the algebraic-constructor tag in the low bits of the pointer.

Haskell is in an exceptional situation due to the pervasiveness of laziness: many values are thunks, and GHC's evaluation model performs an indirect jump on inspection, even to find out that a value is already evaluated. The benefit of pointer tagging is not to avoid a dereference (which you need to do in most cases to get the constructor arguments anyway), but to avoid this indirect jump. The way they avoid the cost of excessive boxing is through very aggressive inlining and optimizations in general; again the "sufficiently smart compiler" approach, which I don't think should be held as a goal for language implementors.

Note that there is a lot more Haskell code written in the strict subset these days, so it is not completely clear to me that this pointer-tagging choice is still the right design. At the time it was introduced, pointer tagging provided a 5% performance improvement over a strategy without pointer tagging. At the risk of going completely into guesswork: this suggests that it is reasonable to consider implementing a Haskell runtime without pointer tagging, and get realistic performance. (You may even see interesting gains by using tagged integers, which may offset the absence of tagging.) On the other hand, when implementing a strict language, pointer tagging does not help, and not having tagged immediate values makes you fall off a performance cliff.

So the experience of Haskell developers is that either custom pointer tagging should be preferred over i31ref for better performance

I am not aware of a performance comparison between pointer tagging and immediate-integers tagging for Haskell programs.

or i30ref should be preferred over i31ref for better GC strategies.

Chicken Scheme uses more than one bit of tag for value shapes, but only immediate integers use the least bit set to 1. In this model you can have i31ref, and still there are extra tag bits available in the 0 case. (Not sure whether this would work for the Haskell runtimes you are mentioning.)

I believe that in practice, if you used much less than 31 bits for immediate values, people would not use this for an integer type (24 is too small for your main type of machine-length integers), only for other immediate values. This might be a workable compromise (in particular, maybe people want 60-plus integers nowadays anyway), but it is not completely clear what the benefits are.

@sabine

I know too little about all the features of OCaml at this point (I have been working with the compiler only since September part time and I still have a lot to learn.) to say whether full-program monomorphization is possible or not - I do not have a proof for either of these hypotheses.

Ahead-of-time full-program monomorphization is known to be impossible for languages that support polymorphic recursion, including OCaml and Haskell (but not SML, see MLton), Agda, Idris, etc. If you have a JIT you can monomorphize "on the fly", this is what the dotnet runtime does. This point was made in this earlier comment of @rossberg: https://github.com/WebAssembly/gc/issues/53#issuecomment-545889014

gasche on 30 Jun 2020

👍3

@RossTate here is another argument that you may find interesting, in terms of finding a "principled" argument for choosing one size or the other.

We are talking about splits in the data space of values that can fit one word. You may want to have tag bits/patterns for either pointers (GHC pointer tagging, or other tricks used by other implementations) or scalars (non-pointers). For example, the Chez Scheme runtime has a bitpattern for fixed-sized numbers but also for booleans, pairs (the "cons tag" mentioned in the discussion), symbols, vectors, etc. The GC only needs to know the fine-grained structure of the pointers, so from the GC perspective we may need many categories of pointers, but only one category of values (which language implementations can the subdivide with more tagging). Given that both sides may need tag space depending on the language, it makes sense to divide the space evenly between pointers and non-pointers: this is exactly the int31ref design.

gasche on 30 Jun 2020

👍1

@RossTate

if we do change the number of bits for guaranteed-unboxed integers, what's a non-arbitrary number to change it too?

I don't think that a non-arbitrary number of bits per se exists. In an ideal world, we would have garbage collection in hardware, and we wouldn't need to chop off bits from a hardware word in order to implement efficient garbage collection in software. However, a specification for garbage collection in hardware mostly faces the same challenges as the WASM GC spec: there being a lot of different ideas of how efficient GC should work like, with nearly every language bringing both some acquired tastes and some fundamental invariants to the table.

I agree with @gasche that, if the number of bits gets too low, we will not use this to implement integer types: the better trade-off in that situation is to implement the integer types via boxed values instead of these unboxed integers, work on optimizing that representation, and enjoying native 32-bit arithmetic.

Note, though, that the implementation of integer types is only one of the situations where guaranteed-unboxed integers are used in the data representation of OCaml. My impression is that the OCaml compiler can make good use of guaranteed-unboxed integers with less bits in most, if not all of these other situations. (I need to check back with people tomorrow to make a list of all the situations where boxing the unboxed is considered to be particularly bad and confirm if this assessment is correct.)

@gasche

Ahead-of-time full-program monomorphization is known to be impossible for languages that support polymorphic recursion, including OCaml and Haskell (but not SML, see MLton), Agda, Idris, etc. If you have a JIT you can monomorphize "on the fly", this is what the dotnet runtime does. This point was made in this earlier comment

Are there any resources that show how a simple JIT compiler that can monomorphize code that contains polymorphic recursion looks like? I do believe Andreas Rossberg when he says it's not possible to do ahead-of-time full-program monomorphization because of polymorphic recursion. I would like to understand the argument in detail, why this is the case, where exactly things cannot work when trying to monomorphize ahead of time.

sabine on 30 Jun 2020

👍1

Here would be an artificial example:

(* a fairly inefficient way to compute 2^n,
   by creating a full tree of depth n and counting its leaves *)
let pow2 n =
  let rec loop : 'a . int -> 'a -> ('a -> int) -> int =
    fun n v count ->
      if n = 0 then count v
      else
        (* call ourselves on values of type ('a * 'a) *)
        loop (n - 1) (v, v) (fun (v1, v2) -> count v1 + count v2)
  in
  loop n () (fun _ -> 1)

let () =
  (* The type of [v] in the last call to [loop] in the code below
     is determined dynamically  by the integer read at runtime.

     For example if we read 3, the last iteration takes a value of type
      (((unit * unit) * (unit * unit)) * ((unit * unit) * (unit * unit)))
     and returns 8. *)
  print_int (pow2 (read_int ()))

gasche on 30 Jun 2020

👍1

@aardappel

It's not just about how many bits we can fit in a pointer, it is also about whether we want to force the need to check these bits upon languages that don't need it (or languages that may need it, for code where it can be statically known that it's not needed).

Yes, I think this is a crucial point. In order to find out whether this feature is reasonable, we need a more thorough survey among the compiler teams of the candidate languages that could run on WASM and would use the built-in GC instead of bringing their own.

The hypothesis, as I understand the previous discussions, is that
(a) languages that belong in the wider sense to the family of Lisp will be able to make good use of the feature,
(b) some languages would use the feature for the sake of convenience/simplicity during compilation (but could ultimately compile to WASM with no major loss in performance even if it didn't exist), and
(c) other languages will not use it at all, no matter what.

Now this becomes something that can be checked with the maintainers, to sort the languages into these three categories.

It would also be very helpful to have performance comparisons for languages that want/need this feature, with the feature and without it. This requires significant effort to be put into optimizing the compiler version that cannot use i31ref, though, in order to be a fair comparison at all.

At least, this could make it easier to decide whether to include it, and, if so, in what form.

sabine on 30 Jun 2020

👍1

A reference on the use of a JIT to perform type-directed specialization at runtime would be the article "Design and Implementation of Generics for the .NET Common Language Runtime", by Andrew Kennedy and Don Syme, 2001.

gasche on 30 Jun 2020

❤1

Here would be an artificial example:

(* a fairly inefficient way to compute 2^n,
   by creating a full tree of depth n and counting its leaves *)
let pow2 n =
  let rec loop : 'a . int -> 'a -> ('a -> int) -> int =
    fun n v count ->
      if n = 0 then count v
      else
        (* call ourselves on values of type ('a * 'a) *)
        loop (n - 1) (v, v) (fun (v1, v2) -> count v1 + count v2)
  in
  loop n () (fun _ -> 1)

let () =
  (* The type of [v] in the last call to [loop] in the code below
     is determined dynamically  by the integer read at runtime.

     For example if we read 3, the last iteration takes a value of type
      (((unit * unit) * (unit * unit)) * ((unit * unit) * (unit * unit)))
     and returns 8. *)
  print_int (pow2 (read_int ()))

So, in every call to loop, the type of v is different, first it is () (the unit value), then a pair of unit values, a pair of pairs of units. Yes, that looks like the loop function cannot be monomorphized, and, since we are getting the number n from an external source, we cannot even perform static analysis to know all the inputs that loop is going to be called on.

Admittedly, this particular example is not very representative of real world code, but the general principle that there are functions that can be called recursively with different types applies.

sabine on 30 Jun 2020

@fgmccabe

The dominant technique [among JS implementations] seems to be nan-boxing

Not sure how you define "dominant"; V8 at least uses pointer tagging, almost exactly like i31ref. Needless to say, this is purely an internal implementation detail, and not at all spec'ed in or visible to JavaScript. (Which is making me think that other dynamic languages, when compiled to Wasm, might want to use i31ref similarly, with dynamic checking for any given integer value whether it fits or needs to be boxed -- but this is just speculation on my part.)

@aardappel

I hope at some point we'll have a real world GC benchmark (not containing any i31ref values) with bit checks turned on and off

I agree that that would be an interesting data point; I'd also like to point out that probably none of the browser Wasm engines are going to provide this data point: whether through pointer-tagging or nan-boxing, they all have unboxing techniques already in widespread use in their GC implementations, so when they add Wasm-GC support (with or without i31ref specified, and with or without i31ref actually occurring in the running Wasm module), they won't be able to turn that off.
In other words: in the browser engines, the GC must check for pointer tags anyway as it walks the heap, so in browsers we're getting this theoretical cost of i31ref support for free. (Disclaimers: I can only speak about V8 with certainty, but I'm pretty sure that this holds for Spidermonkey and JSC as well. Of course I'm aware that browser engines aren't the only game in town, so I'm just providing one perspective here.)

in theory, an implementation could be using 32-bits to represent anyref even while linear memory is running in 64-bit addressing mode

Not just in theory; that's almost certainly what we'll be doing in V8.

does the GC proposal put some expected upper bound on the amount of GC objects that can be addressed? If this can be >2GB, then likely it must use 64-bit pointers internally,

I don't think we've talked about limits yet; it's fair to assume that there will be a limit, just like the Wasm JS API spec already defines a bunch of other limits. Note that the theoretical limit of managed objects that are addressible with a 32bit pointer (even tagged) is not 2GB; with 4-byte object alignment it's trivially easy to support 4GB heaps with tagged 32bit pointers (V8 has that support today, though our default heap size limit is lower); with 8-byte alignment and an appropriate "pointer compression" design (left-shifting to decompress before each access) one could go as far as supporting 16 GB heaps (at a certain performance cost, which may or may not be worth it for saving half the memory of all pointer-sized fields).

and we might as well use i63ref ?

V8 uses 32-bit pointers everywhere (yes, even on 64-bit desktop browsers, because that saves massive amounts of memory), so I assume that i63ref would experience significant pushback, to put it gently :-) (Because it would force all pointers to be 64 bits wide, by virtue of being a subtype of anyref and demanding an unboxed implementation.)

jakobkummerow on 30 Jun 2020

@jakobkummerow Thanks for the insights on the existing V8 codebase.

So,

existing GC implementations of browser engines generally use either pointer-tagging or nan-boxing already. At least in browsers, we are going to bear the cost of i31ref, no matter if it is implemented as part of the WASM GC or not, since it is certain that the WASM GC will be implemented by means of the existing GC.
In contrast to i31ref, i63ref is not always easy to support in the existing codebase because it forces all engines to use 64-bit pointers. Pointer width should be an implementation detail of the engine.

Anything to add to this, from your side @lukewagner?

sabine on 1 Jul 2020

@RossTate:

Can I ask you for some more of your perspective along this line? Something I've been wondering is that, if we do change the number of bits for guaranteed-unboxed integers, what's a non-arbitrary number to change it too? The number that comes to mind is 24 bits because that's 3 bytes (so just enough for RGB and a little more than enough for some Unicode encodings). So I'm interested to hear specifically your thoughts on whether that would work for OCaml? That is, do you know of any OCaml applications or implementation strategies that would suggest a useful lower-bound on the number of bits needed for unboxed integers?

I have several comments, some of which have already been made by others:

The ability to have multiple tag bits on pointers does _not_ imply that more than one bit is needed for tagging scalars. For example, both OCaml and V8 have 31 bit scalars but two bits on pointers. It is always possible to implement it that way, for the price of taking one more bit from pointers in the worst case.
Additional pointer tag bits come with the cost of having to increase alignment of allocations. 8 tag bits would require aligning every allocation by 256 bytes, which is so wasteful that I think no engine would be doing that these days, especially not on a 32 bit machine, which is the case that matters here. So going down to 24 bit sounds just silly from a practical perspective.
There is no objective criterion I can think of by which 24 bits is any less arbitrary than 31.

In summary, to decide on a smaller value, we should at least have some plausible scenario by which _a Wasm engine_ could actually benefit from using more than 1 bit _to distinguish scalars from pointers_.

As an aside, one additional implementation detail I just remembered about OCaml is row polymorphism for objects and variants. Both are implemented with hashes over method/constructor names, which I believe are 31 bit. The hash function has to be the same across architectures because it affects what types are allowed (to rule out ones with hash collisions). So going below 31 might make objects and variants more difficult to implement and much more expensive to use. Probably not a show stopper, but at least a problem.

@aardappel:

If your default way of working involves completely independent compilation to separate .wasm files, then yes, you more often cannot, but then again you're kind of bringing this upon yourself.

Are you assuming that everybody should be doing whole program compilation? That clearly is not what Wasm intends to impose, and it generally is not a scalable approach to development or deployment. In any case, it doesn't solve the problem either, as others have shown above.

I hope at some point we'll have some numbers, particularly a real world GC benchmark (not containing any i31ref values) with bit checks turned on and off. I'm a big fan of the "you pay for what you use" principle, in Wasm, and all of computing.

AFAICT, the vast majority of GC runtimes makes use of tagged integers. And even some prominent ones that don't have second thoughts about that (https://blogs.oracle.com/jrose/fixnums-in-the-vm).

In any case, you are probably worrying about the wrong cost. It has actually been observed that unboxing can make GC _slower_ than tagging, not faster (for example, see https://xavierleroy.org/publi/unboxing-tic97.pdf). Mainly because you need to carry around and inspect more type descriptors, which has repeatedly been observed to be costly. So if there is a cost to worry about wrt Wasm GC, then it is the cost of supporting heterogeneous unboxing in the form of structs, and the need for complex type descriptors that induces.

Of course, as @jakobkummerow points out, none of that will be measurable in Web Wasm engines, because they've already sunk the cost of both mechanisms for JS's sake.

rossberg on 1 Jul 2020

The hash function has to be the same across architectures because it affects what types are allowed (to rule out ones with hash collisions). So going below 31 might make objects and variants more difficult to implement and much more expensive to use. Probably not a show stopper, but at least a problem.

It is true that having less than 31 bits would require work on the OCaml compiler and that different, and (due to having less bits) more hash collisions would occur. People assume that this is ultimately solvable in some way or another (people compiling OCaml to WASM getting used to the quirks and/or taking some acceptable degree of performance degradation).

We would clearly prefer the ability to embed 31 bits into anyref (and also 63, but asking for that would be too much in the light of this being not implementable in the short, and possibly even the longer term :smile:). If there were important technical reasons that make 31 bits impossible to commit to, we would understand.

In any case, you are probably worrying about the wrong cost. It has actually been observed that unboxing can make GC slower than tagging, not faster (for example, see https://xavierleroy.org/publi/unboxing-tic97.pdf)

It seems to me like we currently do not have a simple way to do specify efficient type-directed unboxing in WASM, with as good results and as little implementation effort as the i31ref solution.

I suspect that a solution for type-directed unboxing on WASM that is reasonably simple runs the very real risk of being not expressive enough for polymorphic languages, while at the same time being just a convenience feature for languages that can already monomorphize their code.

sabine on 1 Jul 2020

Meta-note: I am not engaging in comments on whether to have unboxed integers. While there have been a number of informative remarks on this topic, it is separate from this discussion on considering alternative implementation strategies for OCaml if there are no unboxed integers. Exploring this discussion will help inform whether to have unboxed integers (as we may discover there are or are not good alternatives for OCaml), but the other way around is not true. Please create a separate issue on whether to have unboxed integers if y'all would like to continue that topic.

Monomorphization

Let's examine how this idea might work out in more detail.

Polymorphic Recursion

@gasche gives an example illustrating how polymorphic recursion can cause a type parameter to represent an unbounded number of surface-level types. However, for the issue at hand, we need only consider the low-level abstractions of those types. In particular, it seems there are two low-level abstractions for OCaml's types necessary for the issue at hand: scalar and reference.

For reference, I've repeated @gasche's example here: (By the way, Section 5.1 of this paper provides a real-world example.)

(* a fairly inefficient way to compute 2^n,
   by creating a full tree of depth n and counting its leaves *)
let pow2 n =
  let rec loop : 'a . int -> 'a -> ('a -> int) -> int =
    fun n v count ->
      if n = 0 then count v
      else
        (* call ourselves on values of type ('a * 'a) *)
        loop (n - 1) (v, v) (fun (v1, v2) -> count v1 + count v2)
  in
  loop n () (fun _ -> 1)

let () =
  (* The type of [v] in the last call to [loop] in the code below
     is determined dynamically  by the integer read at runtime.

     For example if we read 3, the last iteration takes a value of type
      (((unit * unit) * (unit * unit)) * ((unit * unit) * (unit * unit)))
     and returns 8. *)
  print_int (pow2 (read_int ()))

We can monomorphize this at the low-level by having two forms of loop: loop_scalar and loop_ref. The implementation of loop_scalar would recursively call loop_ref. The implementation of loop_ref would also call loop_ref. The implementation of pow2 would call loop_scalar. It's possible I messed up, but I believe the implementation code resulting from fleshing out that strategy would all type-check in WebAssembly (using the current GC proposal).

Code Bloat

Monomorphization would require every data structure and function to have 2ⁿ variants where n is the number of type parameters (but not existentially-quantified module types—more on that later). For very large functions, this can be mitigated by using having scalar versions call reference versions with boxed scalars if necessary. If this is impractical for OCaml, which only has two low-level abstractions for each type, then it seems inconsistent to expect C# to monomorphize and JIT (and the current proposed alternative for C# includes having integers being boxed).

Higher-Rank Polymorphism

OCaml supports higher-rank polymorphism through its records' field types. This might be addressed by having a field for each monomorphization. It can also be addressed by having just one field and using something like dispatch tags with the dispatch_func extension so that the appropriate funcref can determine which specialization to defer to based on the dispatch tag that was chosen by the callee according to the monomorphization they need.

Modularity

The current proposal does not support import/export of non-reference types. So any module importing types can assume their reference types, and any module exporting scalar types will unfortunately have to box all scalars. This boxing would have to happen anyways if you wanted to guarantee abstraction.

Summary

All in all, there are some weaknesses, but so far it seems to me like this strategy is at least plausible. There are also some potential plusses. Instead of 32-bit integers, this strategy could alternatively let you do 64-bit integers and 64-bit floats without boxing. I'm curious to hear your thoughts on this analysis, @sabine.

RossTate on 1 Jul 2020

👍1

I'm a bit late to this discussion but I'll offer the following datapoints:

The amount of code bloat produced by full monomorphization is highly application dependent. In fact, it is quite literally a function of the program's use of polymorphism. While anecdotal evidence would suggest many programs do not exhibit exponential code bloat, we cannot simply assume all language implementations will follow suit and opt for one particular strategy. As Rossberg pointed out, a language with polymorphic recursion or first-class polymorphism needs a different solution.
Whole program compilation is only feasible for single-language, single-application WebAssembly programs. It does not support an "ecosystem of cooperating modules" that is assumed by many embeddings, such as the web.

(The above said, I love whole program compilation! Virgil uses it, combined with polymorphic reachability and specialization as its default implementation strategy. On a big program, the compiler itself, about 30% of the final binary corresponds to specialized code originating from < 5% of the source code being polymorphic; mostly collections and utilities. Its prototype implementation strategy is to specialize _up to machine representation_, and this reduces that 30% to about 10%. Virgil targets wasm too, but when targeting this GC proposal, it cannot share as many specializations because doing so loses static type information and would force the introduction of casts.)

Type erasure has been an absolute fiasco in the JVM world. We cannot repeat that mistake. This is primarily because Java programs, in fact, all object-oriented languages that mix generics and inheritance, do not actually have the parametericity property that is assumed by a lot of theoretical work and functional languages. Simply put, generic Java programs in practice rely heavily on type information that only comes from their type arguments. Scala has gone through many incarnations of reification to work around this. I don't know where it landed, but its clear that this problem is not going away. The end result is that these programs work around specialization by a bunch of ad hoc mechanisms that amount to passing dynamic information about types at runtime.

Let me also point out the elephant in the room:

Type imports are type parameters to modules. It seems almost certain to me that wasm modules will use (abuse?) them in the future to offer polymorphic library code. In separate discussions there has been an implicit assumption that type imports are some kind of mechanism that only applies to external types and that we can safely assume that all type imports are subtypes of externrefs. I am not sure where we are all on that topic, but if we still assume that, then that's our "type erasure moment". Users will try to to use type imports with primitive types on day 2. If we want to support that and lift the restriction on externref, then I think we fall into a situation where we will, at a minimum, require dynamic specialization in the engine. I am not too terrified of this, since I believe we can introduce staging to bind at least machine representation of type imports at compile time so an engine can at least generate machine code.

Which brings me to an important point,

The CLR is the only successful example of a VM at scale that handles generics well. Though our story is more low-level than the CLR, since we don't bake in an inheritance model, we will fail if we don't have a coherent polymorphism story.

I generally think that i31ref is pretty-alright, not necessarily because it is great for compiling polymorphic statically-typed languages, but because it will be extremely useful for _dynamically typed languages_. What we are seeing here is just another instance of the pattern where static typing cannot be expressed properly so we fall back on dynamic typing.

Last point.

Even though we probably do want i31ref sooner rather than later, it cannot be implemented efficiently on top of either the CLR or the JVM (though everything else in Wasm so far can be) since they have no "machine representations" that are the union of integers (of any size) and pointers. Either boxing or making a (int, Object) pair (and flattening that out into multiple scalars!) is required. While that clearly punishes the (maybe wonky) idea of doing a Wasm VM in userspace on top of one of these VMs, this also holds for adapting the underlying CLR or Java VM directly to do Wasm. They would need to learn a lot of new tricks. While such a scenario is not a design _constraint_, let's keep in mind that not all VMs get i31ref for free by virtue of starting life as a JavaScript VM.

titzer on 2 Jul 2020

👍1

@RossTate:
I believe you are still overlooking essential parts of the larger picture.

For example, what about abstract types? Consider this example:

module type S = sig type t  val xs : t list end
module A : S = struct type t = int let xs = [0; 1; 2] end
module B : S = struct type t = string let xs = ["foo"; "bar"] end
module M = (val if random_bool () then (module A : S) else (module B : S))

When somebody passes M.xs to a polymorphic list function, say hd, what do you do? This is existential types. To solve this, you cannot avoid passing runtime type information in and out for both universal and existential types. And because all these features compose, you’ll end up having to do that everywhere where flow/escape analysis cannot prove that type witnesses are completely contained.

Such type passing implementations for polymorphic languages have been researched long ago and shown to have significantly more overhead than tagging.

As for whether that is even “plausible” for OCaml: in practice it is not. For all the reasons mentioned in this thread, OCaml’s compiler is designed for a uniform representation and hence happily uses untyped IRs. That is, none of the relevant phases would even know where polymorphism occurs and where to insert type or representation witnesses. You’d essentially need to redo its entire compilation pipeline. Similarly for most other languages in this class. (That is also the reason why most of them never saw a usable port to the CLR, and we only have F#, which is _much_ less expressive.)

But it doesn’t stop there. You also have types with heterogeneous representations, something which all of the suggestions so far have completely ignored. For example:

type t = A | B | C | D of int * int

You naturally want to represent constructors A to C unboxed, but D clearly has to be boxed. When you have a list of t, or instantiate a polymorphic function with t, then it has to be able to handle both kinds of values at the same time. Short of tagged scalars you will be forced to box all nullary constructors, which would penalise a lot of typical code patterns — datatypes are ubiquitous in functional programming.

At this point I expect you to argue that we should introduce variant types into Wasm to address that. But that’s not good enough, because you also have row polymorphism, where the set of constructors is open and can be extended arbitrarily! Unless you also want to make _that_ primitive in Wasm, representing variants with tagged scalars is the only practical way to unbox their constructors.

And I could probably go on.

The bottom line is that a monomorphising implementation of polymorphism is the analogous to a coercive implementation of subtyping. It has all the same problems that you’re familiar with regarding compositionality, scalability, etc. Probably worse, because it’s more general.

And none of this is limited to OCaml. You'll have similar problems with most other polymorphic languages.

[Hopping on the train now and will be off the grid for the next week or two.]

rossberg on 2 Jul 2020

@titzer

Type erasure has been an absolute fiasco in the JVM world. We cannot repeat that mistake. This is primarily because Java programs, in fact, all object-oriented languages that mix generics and inheritance, do not actually have the parametericity property that is assumed by a lot of theoretical work and functional languages. Simply put, generic Java programs in practice rely heavily on type information that only comes from their type arguments. Scala has gone through many incarnations of reification to work around this. I don't know where it landed, but its clear that this problem is not going away. The end result is that these programs work around specialization by a bunch of ad hoc mechanisms that amount to passing dynamic information about types at runtime.

In Scala we ended up rolling back virtually all aspects of reified types at runtime. We have learned to embrace type erasure at runtime, while taking advantage of typeclasses and their type-based resolution at compile time. The only remaining uses of runtime type information are what we call ClassTags, and they are only necessary for generically working with Java arrays, the one thing that Java does not use erasure for.

So the ultimate experience of Scala is that type erasure is a success, not the terrible fiasco that you are presenting.

sjrd on 2 Jul 2020

@sjrd

I am glad that Scala found an expressive solution that works around the JVM's limitations. Nevertheless Java itself still suffers from expressivity problems because of, e.g. unchecked casts involving generics. We'd like to avoid hampering the design of future languages targeting Wasm as well as support existing languages like C# in a way that is competitive with their existing native implementations.

titzer on 2 Jul 2020

Oh shoot, I did forget about functors. That does complicate things. That's where more whole-program considerations would have to come in. 😕

type t = A | B | C | D of int * int

You just have A, B, and C each be some singleton reference. For pattern matching, you could either compare with each singleton reference one by one, or those references could each have an i32 field indicating the case that you could switch on.

And none of this is limited to OCaml. You'll have similar problems with most other polymorphic languages.

I went through the top 50 in the TIOBE index. I might have missed some, but here's a rough survey:

(Parametric) polymorphic languages whose predominant implementation uses unboxed integers: OCaml, SML
(Parametric) polymorphic languages whose predominant implementation does not use unboxed integers: Java, C++ (although not impredicative), C#, Swift, Rust (impredicative?), Dart, Kotlin, Groovy, Scala, Haskell

Most of these languages use boxed integers when interacting with polymorphic/generic functions. So this survey suggests that, at least for an MVP implementation, boxed integers is a reasonable alternative for OCaml.

RossTate on 2 Jul 2020

❤2

We'd like to avoid hampering the design of future languages targeting Wasm as well as support existing languages like C# in a way that is competitive with their existing native implementations.

If you'll allow me to give another page of the Scala experience book: about 10 years ago we also tried to compile Scala to .NET. That effort, despite significant (multi-person-year) engineering, did end up as a total fiasco, which was completely abandoned, never to be picked up again. Why? Because of the reified types of .NET. Reified types in the VM might be great if the source language and the VM agree about their type system. In the case of Scala, there were minor mismatches between its type system and that of .NET. This eventually meant that Scala and its type system simply could not be compiled accurately to .NET, because .NET would insist that its type system was reified, and it entered in conflict with Scala.

At the opposite end of the spectrum, the compiler from Scala to JavaScript is a huge success, which maintains semantic equivalence with the original Scala to such a large extent that all major libraries cross-compile with virtually nothing else than build tool configuration. That's on a platform that only has dynamic types, the complete opposite of reified types.

So the experience of Scala is that targeting a VM with specialization is much harder, sometimes impossible. If you'd like to avoid hampering the design of future languages, which might have a type system that does not completely agree with your choice of type system today, my advice would be not to reify types.

sjrd on 2 Jul 2020

This is the boxing solution, I came up with so far:

(global $boxed_unboxed_integer_tag i32 (i32.const 245))

(type $boxed_unboxed_integer (struct (field $value i32)))
(type $value (struct (field $tag i32) (field $contents (ref $block_contents))))
(type $block_contents (array (mut anyref)))

(func $is_int (param $x (ref $value)) (result i32)
  (local.get $x)
  (struct.get $value $tag)
  (global.get $boxed_unboxed_integer_tag)
  (i32.eq)
)

(func $unbox_boxed_unboxed_integer (param $a (ref $value)) (result i32)
  (local.get $a)
  (struct.get $value $contents)
  (i32.const 0)
  (array.get $block_contents)
  (ref.cast anyref $boxed_unboxed_integer)
  (struct.get $boxed_unboxed_integer $value)
)

(func $box_boxed_unboxed_integer (param $x i32) (result (ref $value))
  (global.get $boxed_unboxed_integer_tag)

  ;; create the inner box
  (local.get $x)
  (struct.new $boxed_unboxed_integer)

  ;; make an array of length 1
  (i32.const 1)
  (array.new $block_contents)

  (i32.const 0)
  (array.set $block_contents)

  ;; create the uniform value
  (struct.new $value)
)

Note that we need to double-box, because we do not know beforehand whether a given field of a heap block is a scalar or a reference. That's why we need a tagged block that we can do the Is_int check on. Maybe there is a less costly solution?

sabine on 2 Jul 2020

@RossTate

I went through the top 50 in the TIOBE index. I might have missed some, but here's a rough survey:

(Parametric) polymorphic languages whose predominant implementation uses unboxed integers: OCaml, SML

(Parametric) polymorphic languages whose predominant implementation does not use unboxed integers: Java, C++ (although not impredicative), C#, Swift, Rust (impredicative?), Dart, Kotlin, Groovy, Scala, Haskell

What about Lisp and Ruby? Lisp and Ruby, if I am not mistaken, belong to the former camp. Python belongs to the latter (everything is boxed).

There is no reason to limit this list to languages with strict typing and polymorphism, as the usefulness of i31ref is not necessarily tied to that.

It would be good if we don't include languages that are not, in their original implementations, using garbage collection as their overall memory management strategy (C++, Rust). I'll retract that suggestion if there is sufficient evidence that C++ or Rust would realistically be using the WASM GC to implement some of their memory management features.

@titzer

I generally think that i31ref is pretty-alright, not necessarily because it is great for compiling polymorphic statically-typed languages, but because it will be extremely useful for dynamically typed languages.

Maybe we should explore more on this point, how i31ref is going to be useful for dynamically typed languages, considering that they make up a significant share of the garbage collected languages.

@sjrd Thanks for the insights on Scala's effort of compiling to .NET. Entering into such a kind of heroic but ultimately futile effort is exactly what we as a compiler team worry about.

OCaml has stories related to compiling to LLVM (which, back in the days did not have the support for garbage collection that OCaml needed, but today might be a more suitable compilation target).

And, again, similar to Scala, compilers to JavaScript exist and are very successful, despite their shortcomings (e.g. exception handling).

sabine on 2 Jul 2020

Oh shoot, I did forget about functors. That does complicate things. That's where more whole-program considerations would have to come in. 😕

FWIW, my example did not even contain a functor.

type t = A | B | C | D of int * int

You just have A, B, and C each be some singleton reference. For pattern matching, you could either compare with each singleton reference one by one, or those references could each have an i32 field indicating the case that you could switch on.

You could, but that's more complicated, especially for polymorphic variants, where you would now need a runtime system that maintains a centralised cache to canonicalise these singletons and achieve structural semantics.

And none of this is limited to OCaml. You'll have similar problems with most other polymorphic languages.

I went through the top 50 in the TIOBE index. I might have missed some, but here's a rough survey:

(Parametric) polymorphic languages whose predominant implementation _uses_ unboxed integers: OCaml, SML

(Parametric) polymorphic languages whose predominant implementation does _not_ use unboxed integers: Java, C++ (although not impredicative), C#, Swift, Rust (impredicative?), Dart, Kotlin, Groovy, Scala, Haskell

Okay, I never defined "polymorphic language", but it should be fairly obvious that I was referring to the breed of high-level languages with polymorphic type inference or something close to it, where polymorphism is ubiquitous and used heavily and implicitly. That would include ML, OCaml, F#, Haskell, Agda, Clean, and so on, but not Java or C#, etc, which have quite different use patterns. Scala is somewhere in-between. C++ and Rust don't even have GC, so are totally besides the point.

Among these, Haskell is a special case: due to laziness, it already has to pay the boxing price most of the time, so boxing ints by default is less painful (GHC also has unboxed ints, but they are not first-class). Nevertheless, other Haskell implementations have used tagged ints. For that reason, the language standard explicitly states that ints need only be 30 or 31 bit.

Languages like Groovy or Scala have specifically been built for the JVM, so didn't have a choice. Their performance also tends to be quite inferior to native functional language implementations, due to the inherent limitations and language bias of the JVM. One goal for Wasm was not to repeat such mistakes.

The Dart VM most definitely uses tagged integers. As do major JavaScript VMs, Smalltalk, Ruby, Scheme & Lisp, and other dynamic languages, calling them fixnums or smi's, among other names.

rossberg on 2 Jul 2020

❤1

@jakobkummerow (and @rossberg and @titzer who made a similar point):

I'd also like to point out that probably none of the browser Wasm engines are going to provide this data point: whether through pointer-tagging or nan-boxing, they all have unboxing techniques already in widespread use in their GC implementations, so when they add Wasm-GC support (with or without i31ref specified, and with or without i31ref actually occurring in the running Wasm module), they won't be able to turn that off.

I hadn't considered that, and that would indeed be a very pragmatic reason to support it. But I for one will be really sad that we're going to have our hand forced by JS implementation details on the design of a Wasm feature. Once we have i31ref, these "free" bit checks will never be able to be removed from any Wasm engine, ever, whether it also runs JS or not.

@rossberg

Are you assuming that everybody should be doing whole program compilation? That clearly is not what Wasm intends to impose,

It kinda does currently, if a single .wasm is to be the output. And if that is the case, languages might as well make use of it to compile their programs to more efficient code.

It has actually been observed that unboxing can make GC slower than tagging, not faster

I can totally believe that. I also still hope that GC is but a small slice of runtime cost, and accessing raw untagged values during the remainder is usually faster.

aardappel on 2 Jul 2020

@sabine

(type $boxed_unboxed_integer (struct (field $value i32)))
(type $value (struct (field $tag i32) (field $contents (ref $block_contents))))
(type $block_contents (array (mut anyref)))

Yeah, so there are a number of reasons for needing this triply boxed inefficient design in the current MVP.

You don't want to use the given casting mechanism for distinguish between integers and other values because its very inefficient for such purposes. The casting mechanism has been designed with the expectation that everyone must share the same casting mechanism, and as such it is the worst of all words.
The MVP does not provide a good way to mix scalar and referential data in a way that can be walked without knowing the precise type of the structure. Since OCaml has operations like structural equality/comparison/hashing, you're therefore forced to use an array of references as your $value type, and therefore you have to box integers to put them in that array.
Arrays don't have headers in the current MVP because that's not strictly necessary; you can always do the boxing trick you're employing. Despite the fact that many languages would benefit from arrays with headers, and that arrays with headers would impose little-to-no cost, they have been excluded from the MVP based on the minimality principle. Yet somehow that same reasoning does not apply to i31ref.
An i32ref was rejected for the MVP because it would be inconsistently boxed/unboxed across different architectures; consistently bad performance was preferred.

That said, you could optimize integers by making other operations slower: use anyref for $value and have your values be either boxed integers or arrays. Unfortunately this means you'll have to do a slow cast nearly every time you use a value, again because the MVP does not support case casts.

Note that i31ref would only fix this problem for OCaml int. An OCaml float would still be stuck with the above bad options.

RossTate on 2 Jul 2020

@gasche

A reference on the use of a JIT to perform type-directed specialization at runtime would be the article "Design and Implementation of Generics for the .NET Common Language Runtime", by Andrew Kennedy and Don Syme, 2001.

This was very interesting. Though, it seems the described strategy would not work for OCaml. Early on, they state _"We do not currently support the higher-order types and kinds that feature in Haskell and in encodings of the SML and Caml module systems,"_.

@aardappel regarding separate compilation: I don't think, at least for OCaml, there is a problem with separate compilation on WASM. While linking is not (yet) part of the official spec, it is entirely possible to do one of two things: (1) use the host environment of the WASM engine to link at runtime (in JavaScript, this is possible right now, I expect it has a noticeable impact on runtime performance, but shows that it can be done), or (2) implement a linker that links several .wasm files into a single one.

@RossTate

The MVP does not provide a good way to mix scalar and referential data in a way that can be walked without knowing the precise type of the structure.

I agree with this assessment. If we could, look into the tag field of a struct (always an integer), and then type cast to a (type (struct (field $tag i32) (field $boxed_integer_value i32))), if it is a boxed integer, this will help. I estimate this to be a pretty likely optimization because it is probably useful for a lot of Tiobe-index languages.

Despite the fact that many languages would benefit from arrays with headers, and that arrays with headers would impose little-to-no cost, they excluded from the MVP based on the minimality principle. Yet somehow that same reasoning does not apply to i31ref

That's an interesting observation. I suppose that this is because something like arrays with headers are an optimization that is highly likely to appear in the long run. I estimate that everyone is fairly confident that this will be taken care of in the long run.

sabine on 3 Jul 2020

you could optimize integers by making other operations slower: use anyref for $value and have your values be either boxed integers or arrays. Unfortunately this means you'll have to do a slow cast nearly every time you use a value, again because the MVP does not support case casts.

Correct. Considering that, in typical programs, references are more common than integers, this seems worse.

Still,

Oh shoot, I did forget about functors. That does complicate things. That's where more whole-program considerations would have to come in.

Functors are a very widely-used construct in real-world OCaml code.

sabine on 3 Jul 2020

@sabine @RossTate

(type $boxed_unboxed_integer (struct (field $value anyref)))
(type $value (struct (field $tag i32) (field $contents (ref $block_contents))))
(type $block_contents (array (mut anyref)))

Does $block_contents need to be a mutable array? I.e. do you know anything about the size of the memory block in OCaml's IR so that you can compile to structs with a given number of fields instead of arrays?

(type $boxed_unboxed_integer (struct (field $value_1 anyref)))
(type $value_1 (struct (field $tag i32) (field $field_1 (mut anyref))))
(type $value_2 (struct (field $tag i32) (field $field_1 (mut anyref)) (field $field_2 (mut anyref))))
...

Or does the MVP not allow us to cast something that is a $value_2 to a $value_1 and only use its first field?

timjs on 3 Jul 2020

@timjs

Does $block_contents need to be a mutable array?

For the largest part of the blocks, they are treated as immutable, after they are created. Their contents are immutable. Exceptions are mutable data structures (e.g. arrays, strings) or OCaml's ref feature which lets you create a reference to a mutable variable.

I.e. do you know anything about the size of the memory block in OCaml's IR so that you can compile to structs with a given number of fields instead of arrays?

Definitely not at every point in the computation. This was a very interesting question, as I get told there is an (unfinished) patch for the IR that adds information the size of the block to every field access. It is still an open question whether this can be added for every field access, but for everything so far, it was possible.

type foo = { foo : int; }
type bar = { bar1: int; bar2: int; }
type _ t = Foo : foo t | Bar : bar t
let foobar (type a) (w : a t) (x: a) =
  match w with
  | Foo -> x.foo
  | Bar -> x.bar1

For example, here, we can only know the size of the heap block of x after the match on w. So, that means we need to pass x to the function as an anyref and perform the type cast after we know its size.

Or does the MVP not allow us to cast something that is a $value_2 to a $value_1 and only use its first field?

That we cannot do this is how I understand it. If we could do this, we wouldn't even need to cast to the $value_i type with the correct length, we could just cast to $value_i where i equals the (largest) field index being accessed (though, it is not unlikely that casting to the correct type may be implemented in such a way that it has better performance than casting to a structural subtype).

This isn't related to the troubles introduced by i31ref, and I expect that a lot of other languages will ask for optimizations in this space at some point later in the future. So I'm not worried here that the workaround will stick with us for all time. :smile:

sabine on 3 Jul 2020

@timjs The problem is that there are OCaml operations, like structural hashing/comparison, that need to be able to walk over a structure without knowing what structure it is. The only reasonable way to do that in the MVP is to make everything an array.

This isn't related to the troubles introduced by i31ref, and I expect that a lot of other languages will ask for optimizations in this space at some point later in the future. So I'm not worried here that the workaround will stick with us for all time. 😄

@sabine Don't take this for granted. The MVP is not aligned with any successful system in either industry or research. It is, however, aligned with research systems that proved to be dead ends: insufficiently expressive, slow run-time performance, too burdensome to generate, and extremely high type-annotation size. This has been a standing concern for multiple years, and so far all attempts to address it have hit the same walls that the research did. So while small improvements like arrays-with-headers should be doable, there is still no evidence that the MVP can be extended in a meaningful manner to address deeper issues, whereas there is evidence that it can't be.

RossTate on 3 Jul 2020

@RossTate

The problem is that there are OCaml operations, like structural hashing/comparison, that need to be able to walk over a structure without knowing what structure it is.

Another approach may be to use one MVP "runtime type" per OCaml block shape, which correspond to the "tag" in your representation? If I understand correctly, one would define a structure or array type for each block shape (boxed primitive types, strings, (double)float, strings, tuples, arrays, etc.), then a runtime type representation for those types, and the runtime primitives would branch¹ on the rtt from the block pointer. One advantage is that block fields are then not forced to fit in the anyref type, specific shapes may use larger fields. One could even define structure types for program-defined types (records, arguments of variant/sum constructors), as subtypes of a more generic representation, and thus get precise types for those.

¹: currently there is no instruction for switching on rtts, one would have to do a linear sequence of equality checks if I understand correctly. It may be possible to use the subtyping hierarchy to build a dichotomic tree of rtts, but this seems a bit awkward.

gasche on 3 Jul 2020

Yeah, so you're arriving at the conclusion we arrived at too. Because the MVP's type system is too inexpressive, casts will have to be frequent, and so the best thing for OCaml (and many languages) would be to have some small number of variants that can be efficiently cast to (ideally with a switch). That's why we put this proposal together (which also supports 31-bit unboxed integers, but without requiring everyone to use them).

Alternatively, the problems here could be solved by having a single reference type that can mix scalar and referential data together, along with an efficient cast to check whether a given reference is one such structure (as opposed to a funcref). That's where this conversation also led.

RossTate on 3 Jul 2020

@sabine

Definitely not at every point in the computation. This was a very interesting question, as I get told there is an (unfinished) patch for the IR that adds information the size of the block to every field access. It is still an open question whether this can be added for every field access, but for everything so far, it was possible.

Adding this ability would help elimination an extra indirection!

That we cannot do this is how I understand it. If we could do this, we wouldn't even need to cast to the $value_i type with the correct length, we could just cast to $value_i where i equals the (largest) field index being accessed (though, it is not unlikely that casting to the correct type may be implemented in such a way that it has better performance than casting to a structural subtype).

I ask this because we were discussing an alternative approach where Wasm structs consist of a number of references tracked by the GC and a block of linear memory in #94. The idea there is that structs can be casted to "smaller" structs (i.e. having less refs and a smaller block of linear memory). I'm curious to know if such a design would help you.

@RossTate

The problem is that there are OCaml operations, like structural hashing/comparison, that need to be able to walk over a structure without knowing what structure it is. The only reasonable way to do that in the MVP is to make everything an array.

Ah, yes! I take it OCaml itself has support for this in its runtime system? Letting language designers have such an option in Wasm would need some kind of runtime type inspection, which I assume is not a part of the MVP. Is such a thing planned for in the future? Or something we'd like to avoid?

@gasche

Another approach may be to use one MVP "runtime type" per OCaml block shape, which correspond to the "tag" in your representation? If I understand correctly, one would define a structure or array type for each block shape (boxed primitive types, strings, (double)float, strings, tuples, arrays, etc.), then a runtime type representation for those types, and the runtime primitives would branch¹ on the rtt from the block pointer. One advantage is that block fields are then not forced to fit in the anyref type, specific shapes may use larger fields. One could even define structure types for program-defined types (records, arguments of variant/sum constructors), as subtypes of a more generic representation, and thus get precise types for those.

That would be exactly what I'd like to do in this case!

timjs on 4 Jul 2020

Is such a thing planned for in the future? Or something we'd like to avoid?

No idea. I just know that we need to support the pattern in some way, whether or not it's through the same direct mechanism that OCaml's "standard" runtime uses.

@sabine On that point, I realized the best design for the current MVP might actually be to use v-tables (treating all reference types as nullable):

(type $vtablet (struct
  (field $hash (ref (func (param (ref $value)) (result i32))))
  (field $eq (ref (func (param (ref $value) (ref $value)) (result i32))))
  (field ...)
  (field $case i32)
  (field $apply funcref)
)
(type $value (struct (field $vtablef (ref $vtablet))))

Every value would have a pointer to its v-table. This v-table indicates how to implement various structural operations for the value's type. If the value is a case of some algebraic data type, then $case indicates which case it is. That way you can determine the case of a match and then cast to the appropriate type for that case. This sets it up so that you are only ever casting to a type when you know it has that type; no need to do successive inefficient casts to try to figure out which case it belongs to. The $apply field is for closures (see later).

(type $int (struct (field $vtablef (ref $vtablet)) (field $int_value i32)))
(global $int_vtable (ref $vtablet) (struct.new $vtablet ...)) ;; $case is 0, $apply is null

(type $float (struct (field $vtablef (ref $vtablet)) (field $float_value f64)))
(global $float_vtable (ref $vtablet) (struct.new $vtablet ...)) ;; $case is 0, $apply is null

int and float are implemented with their obvious boxed counterparts. Note that i31ref wouldn't help here. Actually, it would make things worse because then your uniform type would have to be anyref so that it could contain i31ref, which in turn means that you'd have to perform an inefficient cast to ref $value for any other purpose.

(global $nil_vtable (ref $vtablet) (struct.new $vtablet ...)) ;; $case is 0, $apply is null
(global $nil (ref $value) (struct.new $value (global.get $nil_vtable)))
;; it's okay for different nils to be distinct values and have distinct tables. the global $nil is just an optimization.
(type $cons (struct (field $vtablef (ref $vtablet)) (field $head (ref $value)) (field $tail (ref $value))))
(global $cons_vtable (ref $vtablet) (struct.new $vtablet ...)) ;; $case is 1, $apply is null

Here you see where $case comes into play. A match on a list value would first check if $case is 0 or 1. There's no need to cast the value in the 0 case since you know there's no more content to get. If it's a 1 and you need either the head or the tail or both, then you'd cast the value to ref $cons.

(func $polyvar_vtable_nullary (param $id_hash i32) (result (ref $vtablet))
  (struct.new $vtablet ...) ;; $case is (local.get $id_hash), $apply is null
)
(type $polyvar_single (struct (field $vtablef (ref $vtablet)) (field $elem0 (ref $value))))
(func $polyvar_vtable_single (param $id_hash i32) (result (ref $vtablet))
  (struct.new $vtablet ...) ;; $case is (local.get $id_hash), $apply is null
)
;; have a different type and vtable generator for each small arity
(type $polyvar_large (struct (field $vtablef (ref $vtablet)) (field $elems (ref (array (ref $value))))))
(func $polyvar_vtable_large (param $id_hash i32) (result (ref $vtablet))
  (struct.new $vtablet ...) ;; $case is (local.get $id_hash), $apply is null
)
;; it's okay to accidentally generate multiple v-tables for the same case

Here we see that $case is also useful for polymorphic variants. I'm assuming there's some process for turning the string representation of the case name into an integer representation. So long as that process is consistent, there's no need to use the same v-table for the same case (though obviously that'd be more efficient).

;; type coordinate = { xcoord : int ; ycoord : int; }
(type $coordinate (struct (field $vtablef (ref $vtablet)) (struct (field $xcoord i32)) (struct (field $ycoord i32))))
(global $coordinate_vtable (ref $vtable) (struct.new $vtablet ...)) ;; $case is 0, $apply is null

Another advantage of this strategy is that records and cases can use packed representations of their components, with the v-table taking care of specializing structural equality to the record/case at hand, rather than having every component in the uniform representation that you then have to inefficiently cast from every time you access a component.

Now to consider functions. Given a a -> b -> c, we cannot know if it is a closure waiting for two arguments, or a closure waiting for an argument that then will return another closure, or a closure waiting for more than two arguments (since the type variable c could represent a function type). This is a lot of cases to consider at every function application, which is problematic for efficiency (especially since casting is inefficient) and for code size. Ironically the callee is the one who knows best what to do, if only you had some way to call it safely without knowing its run-time arity.

We can solve this problem by using the dispatch_func extension described in WebAssembly/design#1346. This lets you define a number of "dispatch tags", and let's a funcref case match on which dispatch tag was supplied, and these dispatch tags can have different arities. So you could have dispatch.tag $apply1 : [(ref $value) (ref $value)] -> [(ref $value)] and dispatch.tag $apply2 : [(ref $value) (ref $value) (ref $value)] -> [(ref $value)] and so on up to some arity, after which you use arrays or something (the first (ref $value) is the closure itself).

Then given a value of OCaml-type a -> b -> c, you'd grab its $apply funcref and call_funcref it using the dispatch tag for however many arguments you are supplying. Suppose you supply it with two arguments, i.e. $apply2. If it's a closure waiting for two arguments, then it's case for $apply2 will redirect to a function that calls the enclosed function with the contents of the closure and the last two arguments just supplied. It it's a closure waiting for one argument, then it will redirect to a function that calls the enclosed function with the contents of the closure and the first argument just supplied, and then does call_funcref $apply1 on the resulting value with the second supplied argument. If it's a closure waiting for more than two arguments, then it'll make a new closure waiting for two fewer arguments. There will be some boilerplate to make these dispatch_funcs, but it'll be done once and reused by the entire program rather than at each call site, and it should be much more efficient. It's essentially a finitary approximation of the dynamic stack tricks that the standard OCaml runtime performs.

I realize this feels like how you'd compile OCaml to Java. This is the second time where it seems that this MVP is only well aligned with Java (and Kotlin).

RossTate on 5 Jul 2020

@timjs

we were discussing an alternative approach where Wasm structs consist of a number of references tracked by the GC and a block of linear memory in #94. The idea there is that structs can be casted to "smaller" structs (i.e. having less refs and a smaller block of linear memory). I'm curious to know if such a design would help you.

So, if I understand this correctly, in order to have a uniform representation on #94, OCaml must box all their unboxed integers.
Optimization on that can only be done by facing the nontrivial task of implementing type-directed or shape-directed unboxing, supported by code specialization, which breaks up the uniform representation into more specialized representations.
Thus, I think that #94 is worse for OCaml than the current proposal with i31ref.
In the existing proposal with i31ref, we would make the $value type of OCaml an anyref array. The anyref array with i31ref enables both assumptions (ability to store scalar or reference in the same "cell", and ability to check at runtime whether a cell contains a scalar or pointer) of the memory model our existing compiler seems married to.
While we think we can box all the unboxed integers, recovering some of the performance loss seems only possible by means of sophisticated techniques, where the likely outcome is that we need to advise OCaml users to not use language features that are too complex or fundamentally impossible to optimize. It seems that precisely those features that make people choose OCaml (extensive support for polymorphism) would be affected.

Compared to the current proposal without i31ref, an advantage of #94 seems to be that heap blocks naturally are arrays (which is closer to our memory model than the struct types of WASM GC MVP). There is no notion that we can optimize performance by emitting lots of types. I like the simplicity in that.

For OCaml, it looks to me like the current proposal with i31ref is a reasonable target to attempt to compile to, with a realistic chance to make a compiler that people will choose over the existing OCaml-> JavaScript solutions.
Even then, some people ask "but what about a 64-bit target on WASM?". The most realistic way to get that seems to be to compile to the linear memory and bring our own GC. But that's fine, having a reasonable 32-bit target on WASM goes a long way.

To compare, the current proposal without i31ref, after reading a boxed unboxed integer needs us to:

read the tag of the heap block pointed to by the reference (memory read)
read the actual integer value from the heap block pointed to by the reference (memory read)

vs.

check whether the anyref is an integer (bit check)
extract the integer from the anyref (shift operation depending on signed or unsigned)

This is all under the assumption to reuse the existing compiler to the extent that is reasonably possible.

sabine on 6 Jul 2020

@sabine anyref array works for many OCaml blocks (that only contain OCaml values), but there are other blocks whose tag is above No_scan_tag, whose payload should not necessarily be scanned by the GC: strings, double floats and double float arrays, custom blocks, etc. If you use anyref array as the block type you need to box the opaque payloads, either word-by-word (in the array) or, preferably, with the second anyref pointing to a precisely-typed representation in these case. (I suspect that the overhead of the extra indirection for those blocks would be sensibly lower than imposing boxing of immediate values, so that is probably okay.)

@RossTate I haven't had time to look at your alternative MVP proposal, sorry.

Regarding vtables, I'm not sure what you gain compared to just having the block tag (your $case field), and runtime operations switching over this value to cast to the appropriate type. I suspect that dispatching on the vtable is typically slower than having all the runtime-operation code in a single function, due to loss of code locality (but it may allow to benefit from finer-grained static block-shape information, what you call the "packed representation", so maybe this could be a win).

(talking about i31ref again, sorry.) Regarding typed block shapes, In the current MVP one may use width subtyping by having the tag be the first field of each struct. One design could thus be:

value: anyref (unboxed immediate or pointer to a block)
immediate: i31
block pointer: (ref (struct i32 ...))

tuple<n> block:     (struct i32 anyref^n)
record<n> block:    (struct i32 (mut anyref)^n)
double block:       (struct i32 f64)
int64 block:        (struct i32 i64)
closure block:      (struct i32 funcref i32 funcref (ref (array anyref)))    (see at the end for more information)
array block:        (struct i32 (ref (array anyref)))
double-array block: (struct i32 (ref (array f64)))
string block:       (struct i32 (ref (array i8)))
custom:             (struct i32 (ref custom-ops) (ref (array i64)))

All the array fields correspond to extra indirections that could be avoided with a trailing-inline-array or array-with-header design, but I think that the cost may actually not be that large (assuming the array is allocated close to the value); again, smaller than the overhead of boxing all immediate values without substantial (and slightly unrealistic-sounding) changes to the compilation model. One thing I don't realize is how cheap or costly would be the cast from anyref to ref (struct i32), and from ref (struct i32) to ref (struct i32 ...) for each tag.

The current OCaml GC uses an i8 for the tag, packed with GC information etc. in a single header word. If typical Webassembly runtimes do not allow packing struct data with their own metadata, using an i32 instead opens the door for finer-grained tags corresponding to program-defined types, which could eliminate anyref loss-of-precision for statically typed tuples, records and variant parameters.

Re. currified applications (apologies @RossTate for not answering your questions on currification/application earlier): OCaml closures contain two code pointers, one that exposes a "naive" API where arguments are passed one by one (fun x -> (fun y -> (fun z -> foo)))), and one that expects the "static" arity of the function definition (3 in this example if foo is not a fun ..), with an "arity" field that stores this expected-arity information. If you want to call an unknown function and pass N arguments, you first check if its expected arity is N (this is the fast-path), or you fallback to passing the arguments one-by-one. (Implementation note: to avoid code-size blowup, the "pass arguments one by one" and "expect arguments one by one" parts are factored into helper functions caml_curry<n> and caml_apply<n> that are generated by the compiler at link-time. See generic_functions in the compiler code.)

gasche on 6 Jul 2020

@gasche

Yes, I think the use of runtime types to represent a block's tag, so that we know what type to cast it to is a valid choice in the current MVP. And you are right, the presence of heap block shapes that can store i32 values is what breaks the uniformity of the representation with plain anyref arrays.

Edit: to add to that, I hadn't considered this at the point where I commented on #94, so that puts #94 in a better shape, since we have to do type casts all over the place in order to allow the shape of the heap blocks that contain i32 values. Will reevaluate later.

2 hours later:
Hmm... what about #94, but with i31ref support in the reference array? The generic heap block of OCaml is represented by using the reference array with unboxed scalars of the WASM heap block. Heap blocks of OCaml that hold 32-bit values (e.g. string, Int32, array, etc.) are represented using the linear memory array of the WASM heap block.

sabine on 6 Jul 2020

@gasche Thanks for the info on how the standard OCaml runtime deals with currying!

One thing I don't realize is how cheap or costly would be the cast from anyref to ref (struct i32), and from ref (struct i32) to ref (struct i32 ...) for each tag.

In the current MVP, an rtt cast entails the following steps:

if the value being cast is an anyref, check that the value is not an unboxed scalar
load the array of rtts from the reference at the appropriate offset in the heap
load the size of the array
check that the size is greater than than the index of the rtt being cast to
load the rtt in the array at the index of the rtt being cast to
check that the loaded rtt is referentially equal to the rtt being cast to

This is not cheap, especially since it involves double indirection. I don't know of any runtime that has such casts as regularly parts of the hot path (and remember that WebAssembly is not supposed to need speculative techniques like inline caching to achieve decent performance).

So one way to evaluate these various designs is to consider how many rtt casts they require. Let's consider in particular two programs: fold_left (+) 0 nums and fold_right (+.) 0.0 nums. The design I gave involves 3 * |nums| + 1: one for each time the fold casts the list to a Cons, two for each call to the implementation of + and +. in order to cast their arguments to the expected types, and lastly one to cast the final result to the expected type. None of these casts are from anyref and so can skip the check for unboxed scalars. However, although my design skips the need to cast closures here, it does involve a load of the v-table in place of the cast. Similarly, although my design skips the need to cast to get the case, it does involve involve a load of the v-table in place of the cast.

On the other hand, the design @gasche just gave involves, for each iteration element in nums:

Cast the list to a block pointer (even in the nil case).
Cast the list to a tuple<2>.
Cast the function to a closure. (Can be amortized in the fold_left case.)
Cast the two arguments to (+) to i31ref and the two arguments to (+.) to int64.

So its hard to say which design would perform better for fold_left (+) 0 nums, but it seems very likely that mine would perform better for fold_right (+.) 0.0 nums (and probably for fold_right (+) 0 nums and fold_left (+.) 0.0 nums as well).

I suspect that dispatching on the vtable is typically slower than having all the runtime-operation code in a single function, due to loss of code locality (but it may allow to benefit from finer-grained static block-shape information, what you call the "packed representation", so maybe this could be a win).

Good point, though the locality cost (if any) would only happen in structural operations, whereas the benefits of packed representations would happen regularly. Plus having the funcref for application in the v-table I think will help optimize OCaml's frequent use of closures.

P.S. @sabine @gasche @timjs This is a great brainstorming discussion! I hope this sort of thing will happen for every language targeting WebAssembly. 😄

RossTate on 6 Jul 2020

😄1

I'm not that worried about the cost of rtt checks for typical "block shapes", which would be declared all together as the rtts of a handful of structural types. If we do those checks all the time, the rtt values will be in cache, so the dereferences should be relatively cheap. (Of course supporting variants/enumerations-with-parameters in the language would be even faster, as switching on the tag would then be enough to learn the static type information, instead of having to combine with a runtime check.) Following an indirection which is part of our working data is worse, as it may typically have poor locality and cache behavior.

Cast the list to a block pointer (even in the nil case).

Cast the list to a tuple<2>.

In the current OCaml implementation, the nil case [] is represented as the (tagged) integer 0 (this is a natural consequence of the fact that parameter-less constructors are represented as immediate integers), so the cons-cell is the only possible block for list-typed values, and pattern-matching on a list never checks the block tag, directly accessing its fields. This would correspond to casting the anyref to tuple<2> directly if it is not a tagged integer. So there would be the ref.is_i31 check in any case, and a single reference cast in the cons-cell case. (Same with 'a option, OCaml's Maybe.) Of course, most datatypes have several non-constant constructors, so there one would use two casts.

If you use int31ref with 31-bits integers, (+) also doesn't need any rtt cast, just ref.as_i31 which is much cheaper. For (+.), again the static types tell you that the values you get can only be double, so you never check the tag, you convert to a double block right away.

Without counting the function usage, and ignoring int31ref checks, I count |nums| rtt casts in the unboxed-integer case, and 3*|nums| rtt casts in the boxed-double-float case.

When you have type information (on lists, on floats, etc.), the code generator knows what block shape it wants to use, so in general you should only need a single cast from "uniform value representation" to "more precise type" -- but you still do need it. (Being able to dispatch on all possible shapes only comes up in ad-hoc runtime operations.)

gasche on 6 Jul 2020

Ah, nice observation that, because nil can be check for via ref.is_i31, and because Cons is the only block-pointer case, we can skip the cast to get the case info. That only eliminates |num| casts though, so for fold_right (+.) 0.0 nums you still have 4 * |nums| + 2 casts (cast to Cons, cast to closure, cast args of (+.) to boxed doubles). That said, that improvement probably puts the two strategies in the same ballpark, at least for algebraic data types with just one non-nullary case.

RossTate on 6 Jul 2020

@timjs @RossTate @taralx @gasche

I suspect that, if the structref proposal #94 supported i31ref in the reference array, this is a better heap model for OCaml than the current MVP proposal:

value: anyref (unboxed immediate or pointer to a block)
immediate: i31ref
block pointer: (ref structref)

tuple<n> block:     (structref n 1)   (one byte for the tag and n references)
record<n> block:    (structref n 1)
double block:       (structref 0 9)    (one byte for the tag, and 8 bytes for a f64)
int64 block:        (structref 0 9)
closure block:      (structref (n+2) 5)    (one byte for the tag, 4 bytes for the arity,
                                            two function references and n values
                                            as the environment of the closure)
array block:        (structref n 1)
double-array block: (structref 0 (1+8*n))   (one byte for the tag, 8 bytes for each f64)
string block:       (structref 0 (1+n))     (one byte for the tag, one byte per char)
custom:             (structref 1 (1+n))     (one byte for the tag, one function reference,
                                              as many bytes as needed)

Edit: the numbers are off. In practice, we need to align the values so that they can be read in a single memory acccess. This is something that should be worked out in proposal #94 or by using explicit padding.

We can work around not having i31ref in #94 by using roughly twice the amount of memory and only one more memory access:

the value array of the generic heap block of 32-bit OCaml (whose cells can hold either a reference or a scalar value) with length n can be represented by a structref with n references and n 32-bit integers in the linear memory part.
to represent a scalar value at field position i, we set the pointer i to null and store the scalar value in the ith 32-bit integer
at runtime, we can check whether the value at field position i in the OCaml heap block is a scalar by doing a null pointer check on pointer i
(Exact details of this workaround still to be worked out, this is just to illustrate the principle.)

Note that, if there is no i31ref, we do get 32-bit integer arithmetic, at the cost of one additional memory access for loading the "boxed" integer (which is only boxed from OCaml's viewpoint, but not in the WASM GC heap model, where it lives in the same struct, but in a different place). Edit: and at the cost of using twice as much memory, and having to copy twice as much memory when duplicating an object, etc.

We don't need to make up a hierarchy of types and casts between them, the bounds checks are easy for us to emit from the existing compiler.

Considering that I'm a really junior person working on the OCaml compiler, I might miss something here that makes this all fall apart. Please go ahead pick this apart.

sabine on 7 Jul 2020

🚀1

@RossTate: thinking about this more, I think that vtable-based and rtt-based tag checks would have very close performance profiles (with the rtt representation sketched in the proposal): we are following a pointer which we expect to be in the cache (there is a small number of block rtts or vtables), then doing some cheap operations on the dereferenced block (in the vtable case, only a field read, in the rtt case we do three reads on the block and an equality check). rtts are also more likely to benefit from some sort of optimization by the underlying engine.

Regarding closures, I think that one principled way to amortize the rtt cast (to avoid doing one on each application) would be to use a lightweight typed compilation, where each type variable is typed in the wasm translation by its "shape": any function type a -> b is typed as a reference to a closure block, an integer is just a i31ref, etc. (This sounds similar to "transient" gradual typing.) With this compilation strategy (which would require some extra type propagation or local type reconstruction in the type-erasing OCaml compiler), fold_left (+) would not require any closure-specific cast: (+) is already known at the precise type ref closure-block, and fold_left expects a ref closure_block as first argument. On the other hand, Fun.id (+) requires a cast (Fun.id is the polymorphic identity), as function application in wasm returns an anyref value, which needs to be refined again into a closure reference.
This is similar to some type-based unboxing approaches, which are known to have the downside of sometimes applying more coercions than necessary, changing the space complexity of a computation (note: we are not wrapping functions in coercions here). For example, if iterate : int -> ('a -> 'a) -> 'a -> 'a is repeated function application (function exponentiation), then iterate n Fun.id (+) would perform n unnecessary casts. This can be a very costly corner-case for unboxing, as the unecessary boxing/unboxing would cause n allocations, but this is actually fine for casts that preserve the value unchanged, so neither space nor time complexity have changed here. (Also, one half of the wrapping/unwrapping operations are just subtyping, so completely free.)

gasche on 7 Jul 2020

Here would be a proposal for a slightly different i31ref design: instead of being a subtype of anyref, this could be a modality on reference types, like null is used to indicate nullability: ref i31 <heaptype> would be either a reference or an int31 value (ref null i31 <heaptype> would also exist).

With this design, one could use a uniform block representation that is finer-grained than anyref, saving a cast. In the (struct i32 ...)-based representation I proposed above for OCaml, one would use ref i31 (struct i32) as the uniform value type, so no cast would be necessary to access the block tag in the block case.

When type information is available, we could even use a more specific type, for example a lists could be represented as

(type $list (ref i31 $cons-block))
(type $cons-block (struct i32 $value $list)

which would require no cast at all when following the list spine.

gasche on 7 Jul 2020

❤1 👍1

@sabine your proposal would be fine (some numbers need tweaking). The main improvement compared to the one in https://github.com/WebAssembly/gc/issues/100#issuecomment-654214132 is that there is no need to have an extra indirection for arrays/strings. (For closures, one could avoid the indirection by having an environment-length field and casting to the refined struct type. For arrays and strings, this indirection could be avoided by post-MVP arrays-with-headers extensions.)

On the other hand, because the representation of blocks is less precisely typed, you need extra casts when you access the data in some cases. You don't need cast if you access a reference value as a uniform value (for example a field out of a closure), and I expect that the reinterpretation-cast for non-reference values (from bytes to typically int64 or float64) would be very cheap. But in the case of closures, you would need a cast from an arbitrary reference to a function pointer, and those could be expensive (I don't know how the engine would implement this). With the more-typed design, funcref are directly available, so the type-system guarantees that closures contain callable functions. Depending on the cost of anyref-to-funcref casts, this could drown out the performance benefits for arrays and strings.

gasche on 7 Jul 2020

in the case of closures, you would need a cast from an arbitrary reference to a function pointer, and those could be expensive

That's a good point I hadn't considered: functions pointers are the weak point in this largely untyped heap. Can that be resolved by refining #94 into a better proposal?

The engine must perform some checks on the signature of the function pointer and the state of the heap at runtime anyways, does that affect the cost of a type cast from the generic reference type to a function reference?

One existing workaround is to use indices into a table to represent the function pointers on the heap. But that's certainly not very cheap either. So, in the long run, there should be a reasonably efficient way to deal with function pointers on the heap.

sabine on 7 Jul 2020

Thinking about this more: if the engine maintains runtime type information on the side (which is suggested by the MVP proposal at least) and this information can be trusted for security/safety purposes, then casting an anyref to a funcref needs not be more expensive than any other runtime-checked cast. For the purpose of imaginary considerations on performance, you could just count this as an extra checked cast. Then this is just an extra cast in the (fast-path) case of function application compared to the more-typed proposal, which does not sound so bad; and the "structref bounds/width assertion" that you need to access the block fields might be cheaper in the structref design than a rtt cast in the typed design (not sure).

On the other hand, the typed design opens the door to the idea of generating more precise types during compilation, with precise subtypes of the uniform value type, which could save many casts. This wouldn't be possible in the lower-level structref design, if structref bounds are not part of the static type information.

gasche on 7 Jul 2020

Sorry for jumping in a middle of a discussion, I'll probably comment on the rest later for other things, but right now, there is something that I (and others) find a bit strange. I don't really see why only i31ref should exist.
I understand that as this is currently expressed, i-n-ref is a subtype of anyref, which mean that anyref must be large enough to represent it. And of course forcing every engine to use larger than 32 bits addresses is unacceptable.
But it looks like the type ordering relation here is not the right one. There could be one more type (I'll call it 'reforinteger'). anyref would be a subtype of it. i-n would be a subtype of it too. That way anyref would not have to be able to store it, so 32bits pointers would still be doable. But also you could have two versions 'reforinteger-32' and 'reforinteger-64' of which i31 and I63 would be their interger subtypes. Note that this pattern could even allow to represent nan-boxing by having a reforfloat type representing both pointer or f64.

chambart on 7 Jul 2020

Above I suggested to use a reference-modifier like null, so ref i31<reftype>, it looks like you are proposed a more general feature tagged <immtype> <reftype>.

gasche on 7 Jul 2020

On the other hand, the typed design opens the door to the idea of generating more precise types during compilation, with precise subtypes of the uniform value type, which could save many casts. This wouldn't be possible in the lower-level structref design, if structref bounds are not part of the static type information.

So, in proposal #94, it should be possible for the producer to emit structref bounds as part of the static type information, in order to allow engines to optimize when this information is provided by the WASM producer.

@chambart Making tagged integers a supertype of anyref instead of a subtype is a very interesting idea because it would enable much more flexible use, and the potential for, e.g. Ruby, OCaml to establish a reasonable 64-bit target on the WASM GC.

I found the discussion about tagged integers at https://github.com/WebAssembly/design/issues/919. I read this as: @lars-t-hansen proposed a supertype to the pointer type that can store tagged values, but this was not pursued further because the pointer in that supertype was untyped (and would thus require a type cast before accessing it).

Has enabling unboxed integers as tagged <immtype> <reftype> been seriously considered elsewhere? There seems to be a qualitative difference to the proposal in https://github.com/WebAssembly/design/issues/919, since the tagged type does include both types, the immediate type and the reference type.

sabine on 7 Jul 2020

There's the soil-initiative alternate design, which has something like a genericized "ref i31 typ".

taralx on 7 Jul 2020

Lot's of cool thoughts here.

But in the case of closures, you would need a cast from an arbitrary reference to a function pointer, and those could be expensive (I don't know how the engine would implement this).

A cast to a funcref should be just as efficient as to the other "primitive" reference types. The information might even be encoded by some engines as a bit directly in the pointer. Casting to a typed function, on the other hand, would be more expensive. But there's not really a need to do that.

There's the soil-initiative alternate design, which has something like a genericized "ref i31 typ".

To give some context, one of the premises of this alternative design is that efficient case-testing/casting/switching would be useful for an MVP that needs much more casting than other systems due to its coarse type system (and which would ideally support runtimes for untyped languages that also rely heavily on efficient casting). The design recognizes that each language has its own casting/representation needs, and that a universal reference type like anyref causes languages to compete with each other (it seems like the ideas in WebAssembly/design#919 were ruled out basically because of the conflict with a universal reference type), so the design lets each module define its own reference types and keeps them from getting mixed up. The design also recognizes that the engine has its own needs, and so it has languages specify the high-level casting structure they need and lets the engine determine how best to implement that casting structure (including unboxing scalars and such) within its own infrastructure. So an OCaml module could say one of its cases is immutable signed 31-bit integers, and the engine would decide whether/how to pack or box those integers. The design ensures that the choice made is unobservable (besides the performance difference).

RossTate on 8 Jul 2020

We can work around not having i31ref in #94 by using roughly twice the amount of memory and only one more memory access:

Although not discussed there yet, something that would make sense for #94 is to have a way to coerce i32 to and from primitive references, with again the expectation that these coercions would be pretty efficient. Whether they'd be boxed or not may or may not depend on the engine. Regardless, this would further reduce the cost of not having i31ref.

RossTate on 8 Jul 2020

Ignored this discussion for four days and it exploded again 😄 Below I tried to structure some replies on comments of the last few days.

@sabine

I suspect that, if the structref proposal #94 supported i31ref in the reference array, this is a better heap model for OCaml than the current MVP proposal.

This is exactly what I had in mind, but obviously didn't take the time to explain as thoroughly as you did now. I think the memory model using structref is simpler and hopefully more flexible than the current MVP. It naturally supports mixing refs and values in one heap object and bounds checks are cheaper than the proposed rtt casts. Adding i31ref to the proposal is just an optimization.

We can work around not having i31ref in #94 by using roughly twice the amount of memory and only one more memory access.

I haven't thought of this one before, and I like it! The solution I had in mind for an i32 array was using n refs pointing to new structrefs containing just the integer. But this solution uses 2 * (n + c) memory, where c is the size of each structref's header, instead of 2 * n in your solution.

That's a good point I hadn't considered: functions pointers are the weak point in this largely untyped heap. Can that be resolved by refining #94 into a better proposal?

I did not think about the casting of function pointers at all. Well not a type safe cast as we'd like to have in Wasm... All FP backends I know just "use the pointer as a function pointer" because they already statically know this is true 😅

@gasche

With this design, one could use a uniform block representation that is finer-grained than anyref, saving a cast. In the (struct i32 ...)-based representation I proposed above for OCaml, one would use ref i31 (struct i32) as the uniform value type, so no cast would be necessary to access the block tag in the block case.

But this design can still be used with the current MVP isn't it? Only Wasm itself wouldn't statically now about the possibility that we'd like to store an i31 in the anyref:

(type $list anyref)
(type $cons-block (struct i32 $value $list)

Case splitting on something of type $list would branch on a cast to i31ref: if succeeding, we have a Nil; if failing, we have Cons.

Thinking about this more: if the engine maintains runtime type information on the side (which is suggested by the MVP proposal at least) and this information can be trusted for security/safety purposes, then casting an anyref to a funcref needs not be more expensive than any other runtime-checked cast. For the purpose of imaginary considerations on performance, you could just count this as an extra checked cast. Then this is just an extra cast in the (fast-path) case of function application compared to the more-typed proposal, which does not sound so bad; and the "structref bounds/width assertion" that you need to access the block fields might be cheaper in the structref design than a rtt cast in the typed design (not sure).

I think it is true that bound assertions are cheaper than rtt casts. But I don't know how to extend #94 with rtts and if it is necessary to do so. Only thing you can do with structrefs is expose the number of references and the size in bytes of the linear memory _in the type_, so bound checks kind of refine the type of a structref. However, all references in a structref will be anyrefs always. Or we have to extend the type of structrefs once more, to include the type of all its references. I really don't know if that is something which is helpful to do, and if it will save us from a lot of casts.

@RossTate

A cast to a funcref should be just as efficient as to the other "primitive" reference types. The information might even be encoded by some engines as a bit directly in the pointer. Casting to a typed function, on the other hand, would be more expensive. But there's not really a need to do that.

It is good to know that casting to a funcref shouldn't be expensive. Can you elaborate more about your statement that there is no big need to cast a _typed_ function pointer?

P.S. @sabine @gasche @timjs This is a great brainstorming discussion! I hope this sort of thing will happen for every language targeting WebAssembly. 😄

I love these kind of discussions too!

timjs on 9 Jul 2020

One way to understand @sabine's interesting twice-the-amount-of-memory proposal is that in a design that does not allow for unboxed immediates, one approach is to make all values (struct anyref i64) (meaning the immediate if and only if the pointer is null), and use the struct-of-array optimization for any sequence of such values. But besides memory usage, this design also pays a somewhat heavy price in terms of extra allocations, as reading a uniform-value representation from an array always boxes. (Floating-point numbers in OCaml behave more or less in this way already, they are unboxed in arrays and otherwise boxed, with local unboxing optimizations. It works, but there is a noticeable overhead when mixing floating-point code and parametric functions.)

@timjs:

(type $list anyref)
(type $cons-block (struct i32 $value $list))
Case splitting on something of type $list would branch on a cast to i31ref: if succeeding, we have a Nil; if failing, we have Cons.

The problem is that when you learn that the value is not an immediate, you still don't know that it is a ref $cons-block, you have to do a cast for this. If instead of anyref you use my proposed (ref i31 $cons-block), then the knowledge is statically available. (You don't even need a bound check as in the less-typed proposal.)

gasche on 9 Jul 2020

Can you elaborate more about your statement that there is no big need to cast a typed function pointer?

The standard approach here, if we work with uniform / dynamic / weakly-typed value representations, would be to cast to a function pointer whose type is basically anyref anyref ... -> anyref, by casting the arguments instead of trying to cast (or wrap) the function pointer itself. You will need a cast for the arity at application time, but you dot not need to cast the arguments (the function body itself can do it) or the return value (the consuming code itself can do it). Of course, when you do have more information statically on the function type, then it is definitely interesting to cast to a more-typed representation right away, to avoid losing precision on the argument and return types.

gasche on 9 Jul 2020

Regarding function references, a call to an "untyped" funcref is just a little slower than what a call to a typed function reference would be (see WebAssembly/design#1346 on dispatch tags for more info), faster than what it would take to first cast that funcref to a typed function reference (especially using the current MVP's design), and an engine can even amortize the small overhead over successive calls. So a cast to funcref can be done quickly (since it's a coarse/primitive type), and there's not really good reason to cast to a more precise type. (I also talked here about how to make dispatch tags for each arity, and even how to implement dynamic arity tricks with funcref.)

RossTate on 9 Jul 2020

👍1

@gasche

instead of being a subtype of anyref, this could be a modality on reference types, like null is used to indicate nullability: ref i31 would be either a reference or an int31 value (ref null i31 would also exist).

That's a really nice idea actually, that way any languages not needing i31ref in combination with engines where pointer tagging is optional would not pay the price of this extra bit check.

So null makes a ref nullable.. and i31 makes a ref.. scalarable? :P

aardappel on 9 Jul 2020

I don't know how to extend #94 with rtts and if it is necessary to do so

My impression is that #94 does not need a rtt mechanism, because the only "typing" #94 provides is the size of the reference array and the size of the linear memory array (and this linear memory is a sequence of bytes, just like the other WASM linear memory). Internally, every heap block must carry around these bounds (for security reasons, to prevent out-of-bounds access). The bounds here are effectively the type.

A WASM producer whose compilation strategy involves checking which shape a block is at runtime could place a header in the linear memory, and, based on that, assert different bounds. Or, #94 could expose the bounds checks as explicit operations, and a producer, who uses an encoding that allows to distinguish their blocks at runtime only based on the bounds, can use that.

I might be missing the greater point of runtime types, though, that cannot be achieved by this simple method.

The appeal of #94 is really that this feels closer to a mental model that producers are already accustomed to. They have full control over arranging their linear memory array as they see fit. The open question is: what are the qualitative differences to the existing proposals? And what #94 it look like when we add all the things that are needed for efficiency's sake?

sabine on 10 Jul 2020

👍1

@rossberg @aardappel @RossTate what's your assessement of a type tagged <immtype> <reftype> as a supertype of anyref - as proposed by @chambart, and given syntax by @gasche?

This would additionally enable 63-bit scalars, at the cost of producers who want to use 63-bit scalars using more memory for references when storing them on the heap. Producers who do not use the 63-bit or 31-bit scalars simply do not use them.

I have the impression that handling this as a supertype of the general reference type could be the correct way to deal with scalars and references that live in the same heap cell. This way, engines can internally use 32-bit or 64-bit pointers, without exposing this to the outside world. At the same time, it becomes possible to efficiently represent 63-bit scalars on the heap - which means producers that rely on efficient scalar representation on the heap can compile to 64-bit WASM.

sabine on 10 Jul 2020

Something needs to be clarified before I can give thoughts. Is tagged a type constructor? In particular, can different modules specify different sizes for <immtype>?

RossTate on 10 Jul 2020

If I understand this correctly, tagged <immtype> <reftype> is a new type where <immtype> is either i63 or i31, and ref type is a regular reference type. Please correct if wrong @chambart. Edit: I think there was the point about float nan-tagging in there, too, so tagged f64 anyref should be possible.

E.g., a value of type tagged i63 anyref can be either i63 or anyref. A value of type tagged i31 (ref $x) can be either i31 or ref $x.

Edit: different modules could most likely use different tagged-types.

sabine on 10 Jul 2020

Yes, this is the idea. The storage size of tagged <immtype> <reftype> would be max(size(<immtype>) +1, size(<reftype>)). If we wanted to be even more precise, we could have a sort of aligned 8 <reftype> form to reduce the storage size of a reftype through an alignment guarantee, and use tagged i31 (aligned 2 <reftype>), with size(tagged i r) = 1 + max(size(i), size(r)).

gasche on 10 Jul 2020

I'm not sure my question was answered. Let me lay out the problem. Suppose one module use tagged i30 ... and another module uses tagged i31 .... In the context of #94, these both need to be coercible from primref. That means primref needs to be able to tell whether a given reference was created as tagged i30 versus tagged i31. Thus bits will have to be used to determine which immediate type was use, making the information no longer fit into the given space. So this only really works (in a design with a universal representation) if there is a universally agreed upon immediate type (or maybe two, one for large immediates that would be boxed on engines with 32-bit pointers, and one for small immediates).

So now let's suppose we choose to support just i31 and i63 to address the above problem. I think it's safe to say that i63 doesn't work. It's incompatible with NaN boxing, which is an option that should be left open (at least, with the understanding that WebAssembly is supposed to be compatible with a wide variety of implementation techniques rather than prescribe specific ones).

As for i31, I think it makes the wrong tradeoffs for #94. In #94, one of the most frequent operations you will be doing is casting primref to the various primitive reference types. So if I were using 32-bit pointers, I would think a viable strategy would be to use the low 2 bits of the pointer to flag various common reference types, e.g. 01 for structref, 10 for funcref, 11 for some other common reference type (I have ideas for what that should be, but I won't go into that here), and 00 for "other" references. Even if I reserve 11 for scalars, that's just 30 bits. And before we go into considering i30, another factor to consider is the complication to garbage collection itself. With the approach I give above, precisely garbage collecting a structref is pretty easy; you just walk through the reference elements, mask off the low 2 bits, and then proceed to the referenced value (using standard tricks for dealing with nulls). With i30, you'd need to branch before dereferencing each element, slowing down the whole process.

Fundamentally, in any design with a universal representation such as the current MVP and #94 (but not the SOIL Initiative's preliminary design) unboxed scalars come at a cost to all languages that do not use them. Meanwhile, something like i32ref (and/or i64ref) would not have such costs but would at least enable more compact/efficient means for boxing scalars (that some engines might even be able to keep unboxed). It's also easier to add unboxed scalars as a feature later, if we discover it's more useful and less costly than we expected, than it is to remove the feature. So in a system with huge backwards-compatibility considerations, I think it's better to go with the more conservative option.

RossTate on 10 Jul 2020

Letting Wasm modules specify custom tagging schemes like tagged i31 anyref, tagged i63 anyref, tagged f64 anyref seems to be at odds with:

engines can internally use 32-bit or 64-bit pointers, without exposing this to the outside world

because it effectively forces engines to use the prescribed pointer width and tagging scheme anywhere where these types propagate.

Also, consider subtyping: a subtype that refines a field type from tagged i63 anyref to just anyref would have to store that anyref with 64 bits as well (so that its layout is compatible with its supertype's). If you stick to the structural subtyping of the current proposal, then I think the sheer possibility of such subtyping relationships would force all reference fields everywhere to be 64 bits wide; if you switch to nominal subtyping, then (a) that's a much bigger change and (b) that would have the consequence that you can't compute a struct's on-heap layout without inspecting all of its supertypes as well.

More generally: I believe there's a hard requirement that references to any type in a subtyping hierarchy have the same bit width. So "anyref" can't possibly be a subtype of both a 64 bit wide tagged i63 anyref and a 32 bit wide tagged i31 anyref.

For unboxed integers, 31 bits is the obvious width: it's the largest value (hence maximizing benefit/applicability) that's small enough to let engines choose their own pointer width and tagging scheme (maximizing implementation freedom -- as was pointed out before, object pointers can still use extra tag bits, e.g. <...31bits...>1 could be i31ref and <...30bits...>10 and <...30bits...>00 could be differently tagged object pointers; and of course NaN-boxing is compatible with i31ref as well).

This isn't to say that we must have i31ref, just that: _if_ we want a guaranteed-unboxed iXref, then X=31 is the way to go.

I'd be perfectly fine with having a fairly-generic reference type that's guaranteed to not be an i31ref, to shave off a machine instruction or two from code that doesn't need it. That could be some sort of annotation (like the (ref null? i31? $t) suggested above), or a new type in the predefined hierarchy, e.g.:
i31ref <: eqref <: anyref
$t <: heapref <: eqref for all struct/array types $t

jakobkummerow on 10 Jul 2020

@jakobkummerow @RossTate Ok, I got this wrong. I said make tagged a supertype of anyref, and that cannot work because type casting is an operation that cannot change the bit representation of the value. That makes sense. The same goes for primref of proposal #94 which also cannot be a subtype of tagged.

Does it make more sense as a separate type that is not in a type hierarchy with anything else, and where we have operations to extract the immediate or the reference?

tagged i63 anyref
tagged.from_imm $immediate_value
tagged.from_ref $ref_value
tagged.is_imm $tagged_value
tagged.as_imm $tagged_value
tagged.as_ref $tagged_value

Conversion from tagged i63 anyref to anyref, if anyref is represented by 32 bits would mean to take the lower 32 bits from the value of type tagged i63 anyref. The point here would be that extracting and wrapping values from/into a tagged-value does not require a memory access - it only uses arithmetic, logic or shift instructions.

In proposal #94, I think, introducing tagged means that you need to choose on a per-structref basis whether its reference array contains taggeds or primrefs. So, a structref's type becomes structref <tagged-or-untagged> N M where <tagged-or-untagged> is either some tagged <immtype> <reftype> or some <reftype>. The reason why this needs to be chosen on a per-struct basis is that, for the GC to walk a structref, it needs to be able to distinguish references and immediates, and we do want to avoid non-users of tagged to incur a tag-check on every pointer access.

So, you could have a structref (tagged i63 primref) N M whose low-level representation of the pointer array is a sequence of 64-bit values which either represent a 63-bit scalar or a primref.

Okay, this looks to me like #94 with tagged (internally?) needs a header that describes to the GC the type of the values in the reference array. This is starting to look somewhat like a runtime type (in addition to the existing bounds). @timjs @gasche do you see a simpler way to introduce something like tagged in #94 (where "being like tagged" means that it allows to represent 63-bit scalars in the reference array without generally forcing a pointer width on the WASM engine)?

@RossTate I haven't been doing the soil initiative proposal justice by so far not working out the shape of the OCaml heap on that proposal. I just spent some time looking through the spec, trying to piece things together. I suppose I am having difficulty wrapping my head around this because the soil-initiative model is so far away from my own mental model of the OCaml heap (and there are a lot of attributes on the types). It seems to me like the soil-initiative model is an attempt to make a very abstract, customizable heap model.

I guess, the block shapes of the existing compiler could look similar to this:

$uniform
:= scheme.new (extensible (cases $immediate $value))

value :=      scheme.new ((field $tag (unsigned 8) immutable) castable
immediate :=   scheme.new 
                         (field $value (unsigned 31))
block pointer := (gcref $value)

tuple<n> block: scheme.new (parent implicit $value)
                         ((field $tag (unsigned 8) immutable)
                         (field length $tuple_length (unsigned 32) immutable))
                         ?? - array of gcref $value
record<n> block:    same as tuple<n>
double block: scheme.new (parent implicit $value)
                         ((field $tag (unsigned 8) immutable)
                          (field (unsigned 64) immutable))
int64 block:        same as double block
closure block:  scheme.new (parent implicit $value)
                         ((field $tag (unsigned 8) immutable)
                         (field funcref immutable)
                         (field $arity (unsigned 32) immutable))
                         (field funcref immutable)
                         (field length $environment_length (unsigned 32) immutable))
                         ?? - array of gcref $value
                             )
array block:    scheme.new (parent implicit $value)
                         ((field $tag (unsigned 8) immutable)
                         (field length $array_length (unsigned 32)))
                         ?? - array of gcref $value
                             )
double-array block: scheme.new (parent implicit $value)
                         ((field $tag (unsigned 8) immutable)
                         (field length $array_length (unsigned 32)))
                         ?? - array of (unsigned 64)
string block:    scheme.new (parent implicit $value)
                         ((field $tag (unsigned 8) immutable)
                         (field length $string_length (unsigned 32)))
                         ?? - array of (unsigned 8)
custom:         scheme.new (parent implicit $value)
                         ((field $tag (unsigned 8) immutable)
                         (field funcref immutable)
                         (field length $length (unsigned 32) immutable))
                         ?? - array of gcref $value

sabine on 10 Jul 2020

@RossTate @jakobkummerow you both seem to be assuming that tagged <immtype> <reftype> is a reference type -- that it needs to be a subtype of #94's primref/pointer or the MVP's anyref. But I don't see why that would need to be the case; it is perfectly fine to have explicit operations tagged.check, tagged.as_imm and tagged.as_ref to coerce into the immediate / reference representation, which do something at runtime (they are not witnessing a subtyping relation). In particular size(tagged i r) and size(r) do not need to be the same.

Edit: ah, @sabine said just the same thing slightly earlier. Apologies for the redundancy.

gasche on 10 Jul 2020

👍1

I think #94 should be fleshed out as a summarized proposal; right now people are discussing it as a single proposal while taking some points in the middle of the discussion, it is confusing/difficult to keep track of what they mean.

@sabine: I think the simplest way to extend what-I-understand-as-#94 with tagged <immtype> <reftype> would not be to have three sized regions in each structref: one for immediates (size I), one for references (size R), and one for tagged values (size T). If having three regions is not easy from an implementation perspective, one could require that either R=0 or T=0: either a block uses only pure references, or only tagged references, but not both.

gasche on 10 Jul 2020

@sabine @gasche I would say that if tagged potentially being a different size from anyref would cause 3 rather than 2 size fields, that would be enough to prefer the simplicity of having just i31, in the context of #94.

In the context of the MVP however, (with coercion, not subtyping), allowing several scalars types could be worth it, as the cost of ani63 in a tagged is not greater than generally storing an i64. Making this a coercion seems generally saner than subtyping, and it accomplishes the goal of making only producers that use these types pay for their cost (in engines that do not use tagging already).

In fact, this modularizes the i31ref feature, to the point where you could go ahead with a GC MVP proposal that does not contain it, and make it an add-on (which may be useful if we want to debate further tagging schemes).

It will have the downside that access to the JS world is defined entirely in terms of anyref, and a JS API allows us to store an "abitrary" value, then an OCaml producer, say, cannot simply pass its i31ref as-is, and will need to box. That is probably acceptable.

aardappel on 10 Jul 2020

👍1

@RossTate @jakobkummerow you both seem to be assuming that tagged <immtype> <reftype> is a reference type -- that it needs to be a subtype of #94's primref/pointer or the MVP's anyref.

@sabine @gasche The arguments I gave are not about types, they're about values. The purpose of using smaller scalars like i31 and i63 is entirely to let scalar values occupy spaces primarily intended for reference values, whether those spaces be the non-linear fields of a structref or wherever anyref happens in the current MVP. The costs I gave have to do with the optimized representations for references that get pushed out by scalars despite likely being more useful for more languages (possibly including even OCaml).

RossTate on 12 Jul 2020

@aardappel For OCaml, I think it is enough in #94 to have a runtime type for the heap block that specifies the type of values in the reference array (tagged with 64 bits, tagged with 32 bits, or primref). I agree that maintaining three size fields would be too much.

Explicit coercion between anyref and a tagged reference value seems the right thing to do. The cost model here is predictable, since tagging and untagging are ALU operations.

There's nothing wrong with having i31ref as subtype under anyref, if that helps JavaScript interop, or even just to provide something that can be used right now. We can use that as a workaround, to implement a 32-bit target for the OCaml compiler on WASM while we wait for tagged to implement a 64-bit target.

Though, tagged looks to me like the more correct thing to implement in the long run, precisely because languages that do not use tagged do not need to pay for it and because languages that do use it get the 63-bit tagged that they will use in their 64-bit targets.

@RossTate

The purpose of using smaller scalars like i31 and i63 is entirely to let scalar values occupy spaces primarily intended for reference values

Ah, the purpose you assume is more specific than what we actually need:

In the OCaml heap model, we let 31-bit and 63-bit scalar values occupy spaces that can be occupied by either scalars or references.

We do not need our scalars to fit in the same space as a generic reference value.

What we do need is a type that can store both scalars and references with reasonable efficiency. tagged as a type coercible to and from anyref looks like it fits the bill.

sabine on 13 Jul 2020

@RossTate I still don't understand your argument. In a design where tagged <immtype> <reftype> is available, then anyref does not need to be include i31ref, and can remain represented using 32 bits. The only assumption that we need for tagged to make sense is that pointers are 2-aligned. (This could be made statically explicit with a type aligned 2 <reftype>, but we haven't been using this in the discussion.) Then if you use tagged i31 anyref, you get what is currently anyref (in the current MVP that includes i31ref), and this can fit in a 32bit word. If you use tagged i63 anyref, you get a new type that requires 64 bits of storage space. The fact that this type can be expressed does not change any property of anyref itself. Yes, if now you start to use tagged i63 anyref heavily in your programs, those program will consume more memory than if they used tagged i31 anyref. The choice is entirely left to the producer of the code.

The existence of i64 or f64 in wasm does not mean that anyref has to be 64bit-wide, and tagged i63 anyref is just the same.

In the current MVP proposal, anyref is the only type that can efficiently represent either references or scalars, so it is the only sensible choice for a "universal type" in a language that needs a uniform representation for both scalars and values. If tagged is available, then you get several sensible choices "universal types", with different sizes: tagged i31 anyref, tagged i63 anyref, but also more precise types like tagged i31 (ref (struct i32)) or `tagged i63 (ref (struct i32)) (in the case of OCaml where blocks are known to start with a block tag). Users (or in our case, compiler authors) can choose the type they prefer for their usage.

(In my intermediate proposal (ref i31 <reftype>), you can only tag with i31, but retain the ability to use either anyref or more precise types as the reference type.)

gasche on 13 Jul 2020

Y'all are assuming that anyref or primref do not have anything better to do with those lower 2 bits, and so there's implicitly free space making it possible for tagged i31 ... to have room for a reference and for a scalar. What I am saying is that there might be better uses for those lower 2 bits rather than to leave room for scalars. For example, primref might want to use the bits to distinguish at least funcref and structref values in order to permit fast casting. And anyref might want to use bits completely differently to support NaN boxing.

In other words, while tagged i31 primref might make boxing integers faster for OCaml (by not boxing them), it has the cost of making either casts to structref or casts to funcref slower for OCaml and for everyone else.

RossTate on 13 Jul 2020

@sabine

There's nothing wrong with having i31ref as subtype under anyref

It means we commit to checking that bit in any anyref we want to access as ref, forever, even in Wasm engines that don't also have a JS implementation, and could otherwise store/access anyref as a naked pointer.

aardappel on 13 Jul 2020

❤1

@RossTate we could think about having, for example, (tagged structref funcref). In other words, maybe the strategy of exposing tagging structures in types can also fit your favorite needs.

My impression is that (ref i31 <reftype>) and (tagged <type> <type>) are interesting "alternatives to i31ref" (they feel much more realistic to me than monomorphisizing everything), and they would each design a dedicated PR to expose a design and foster further discussion.

(Again, the primref PR should really write its design down to summarize the #94 discussion. This would also help with discussing (ref i31 <heaptype>) and (tagged <type> <type>) in the context of that lower-level proposal.)

gasche on 13 Jul 2020

we could think about having, for example, (tagged structref funcref). In other words, maybe the strategy of exposing tagging structures in types can also fit your favorite needs.

@gasche, you seem to be describing a heterogeneous system, meaning there is no global tagging structure. But then you need structref to say what kind of reference fields it has, e.g. (tagged structref funcref), but then the structrefs in those field presumably have the same tagging convention, leading to recursive types. See this proposal for how to carry that out.

(Again, the primref PR should really write its design down to summarize the #94 discussion. This would also help with discussing (ref i31 ) and (tagged ) in the context of that lower-level proposal.)

We're working on it, but it will not have a structref type that is parameterized by the type of its reference fields. One of the benefits of the proposal is its simplicity, and furthermore that complexity doesn't solve problems without introducing recursive types (see above).

RossTate on 13 Jul 2020

Out of curiosity, I manually boxed an OCaml program performing integer arithmetic, in order to evaluate the performance overhead of systematic integer boxing on the current runtime. (The function I used is what I call "sumtorial", like factorial but with a sum instead of a product, basically a complex way to complex n*(n+1)/2.)

let sumtorial n =
  let rec loop acc = function
    | 0 -> acc
    | n -> loop (acc + n) (n - 1)
  in loop 0 n

module BoxedInt = struct
  type t = Int of int
  let (+/) (Int a) (Int b) = Int (Stdlib.(+) a b)
  let (-/) (Int a) (Int b) = Int (Stdlib.(-) a b)
end

let boxed_sumtorial n =
  let open BoxedInt in
  let rec loop acc = function
    | Int 0 -> acc
    | n -> loop (acc +/ n) (n -/ Int 1)
  in loop (Int 0) n

let locally_unboxed_sumtorial n =
  let open BoxedInt in
  let rec loop acc = function
  | Int 0 -> acc
  | Int n ->
    let (Int a) = acc in
    loop (Int (a + n)) (Int (n - 1))
  in loop (Int 0) n

boxed_sumtorial is an exact translation of the sumtorial definition, with boxed integers instead of unboxed integers. locally_unboxed_sumtorial is a version where I manually inlined the arithmetic constants and operations and applied local boxing/unboxing simplification.

On my machine, the boxed version is precisely three times slower than the unboxed version. The locally_unboxed_sumtorial is not much faster than boxed (3.6s rather than 3.9s on a test), because for this program it only eliminates redundant unboxing, there is no redundant boxing that can be eliminated locally. (Of course we could change the calling convention of the function to take unboxed integers, but this is not a local transformation anymore.)

gasche on 15 Jul 2020

Quick update: as of just now, i31ref as described by the current proposal is fully implemented in V8's prototype, so you can use that for any experimental performance investigations/comparisons.

In case anyone has a demo where they suspect that significant (or at least measurable) time is being spent on taggedness-checks even though the demo doesn't use i31ref, it would be simple to create a custom build (or introduce a runtime flag) to turn off i31ref support and verify this suspicion. I won't do that until/unless someone asks me to though :-)

(Disclaimer: this is not a statement of opinion on whether i31ref should exist in the spec, or in what form. I find the flexibility of a generalized form like (tagged i31 anyref) appealing; I also like the simplicity of the current proposal (and believe that it doesn't incur an unreasonable cost at runtime); and I'd also be fine with not having it at all -- we can always add it later if needed.)

jakobkummerow on 16 Jul 2020

👍3 🎉1

For example, primref might want to use the bits to distinguish at least funcref and structref values in order to permit fast casting. And anyref might want to use bits completely differently to support NaN boxing.

In other words, while tagged i31 primref might make boxing integers faster for OCaml (by not boxing them), it has the cost of making either casts to structref or casts to funcref slower for OCaml and for everyone else.

Ok, if I get this right, you say that having tagged i31 anyref in the spec prevents the engine from using the lower (unused) bits of a heap pointer.

I see two cases here:

In case an aligned heap pointer is stored by means of the type tagged i31 anyref, this is true. 32 bits are used, there is no way for the engine to embed additional information about the heap pointer in these 32 bits at runtime.
In case an aligned heap pointer is stored by means of the type anyref, the engine is still free to use lower (unused) bits in any way it sees fit.

Since we cannot type cast between tagged i31 anyref and anyref, at any point in program execution, the engine knows exactly (thanks to type annotation of the WASM program) which of these representations it is dealing with.

It looks to me like there is no difference for the GC walking the heap, when adding tagged to the current MVP proposal. It already needs to know the type of the heap struct it is walking, in order to know which fields may be pointers.

So, there are three entities here:

aligned heap pointer
value of type anyref
value of type tagged i31 anyref

Is there anything that prevents the engine from assuming different semantics for the implementation of

aligned heap pointer represented as tagged i31 anyref (cannot store information in lower bits), and
aligned heap pointer represented as anyref (can store information in lower bits)?

It looks to me like adding tagged instead of i31ref can only potentially bring a disadvantage to the users of tagged (who are likely to be willing to incur that because it enables reusing their existing compilers), but not to those who only use anyref and no tagged representations. In contrast, i31ref comes at a cost to everyone, but is less complex.

sabine on 17 Jul 2020

@gasche

we could think about having, for example, (tagged structref funcref)

This tagged-idea could in theory even be taken further:

tagged (ref $A) (ref $B) (ref $C) i30

tagged (ref $A) (ref $B) (ref $C) (ref $D) (ref $E) (ref $F) (ref $G) i61

sabine on 17 Jul 2020

So what you're describing is a heterogenous approach. Unfortunately, the current MVP is designed around a homogenous approach. For example, its compilation model for imported/exported types is designed around a universal representation. As such, you would not be able to use tagged i31 anyref as imported or exported types (without effectively changing anyref to bake in i31ref).

But if you want to go with a heterogeneous approach to enable custom low-level representations, then it's better to take things further than just tagged. For example, right now the coercion from tagged i31 anyref to anyref (with specialized low bits) would require a memory read to determine the low-bit information that was omitted from tagged i31 anyref to make room for the unboxed scalar. To prevent these kinds of efficiencies, you want a coordinated tagging scheme for your types. That's what the SOIL Initiative's proposal does.

For completeness, I should note that tagged i31 anyref can still have a cost even with your clarifications. Note that the coercion from tagged i31 anyref to anyref required a way to look at the heap contents to determine the low bits. That assumes the heap has that information. But some garbage-collection implementations don't put meta-information in the heap at all, at least for common small objects, relying on the fact that the meta-information is always available in the low-bits of the pointer. For example, if we were to add i32ref and i64ref, instead of a wasting a word in the heap for each of these objects just to say that they are i32ref and i64ref respectively, an engine could make sure that the low bits of every pointer to these objects tracks whether they are i32ref or i64ref (or other). But it can't do that if tagged i31 anyref exists, because there's not enough room in the low bits to track that information, forcing these values to take more information in the heap. (Since a funcref is a pair of a code pointer and a module-instance pointer, it too might be treated as a common class of small objects.)

RossTate on 17 Jul 2020

❤1

the current MVP is designed around a homogenous approach. For example, its compilation model for imported/exported types is designed around a universal representation. As such, you would not be able to use tagged i31 anyref as imported or exported types

Thanks for bringing up the type imports spec, I hadn't read that in all details yet. :+1:

Okay, the type imports proposal says "As far as a Wasm module is concerned, imported types are abstract. Due to Wasm's staged compilation/instantiation model, an imported type's definition is not known at compile time." (https://github.com/WebAssembly/proposal-type-imports/blob/c9700ff6267571f4a52151c8a46e800f8534f923/proposals/type-imports/Overview.md)

One paragraph later it says "However, an import may specify a subtype constraint by giving a supertype bound with the import"

If I understand this correctly, this means that all type imports/exports must be subtypes of the type any ("the type of all importable (and referenceable) types"). So, we generally cannot import/export any value types, only reference types.

Okay, now looking at this from a practical perspective for OCaml: why would we need to import/export types for tagged i31 anyref in the first place?

When importing something like a global, a function, or a table, I don't need to have a nominal type that wraps tagged i31 anyref, I can use tagged i31 anyref as a type directly, just like i32 and the other value types, right or wrong?

I could still import/export struct or array types that contain tagged i31 anyref, right or wrong?

But some garbage-collection implementations don't put meta-information in the heap at all, at least for common small objects, relying on the fact that the meta-information is always available in the low-bits of the pointer.

You mean, some garbage-collection implementations don't put meta-information in the bit-representation of the small object, but instead they put meta-information in the bit-representation of the pointer pointing to the small object?

we were to add i32ref and i64ref, instead of a wasting a word in the heap for each of these objects just to say that they are i32ref and i64ref respectively, an engine could make sure that the low bits of every pointer to these objects tracks whether they are i32ref or i64ref (or other). But it can't do that if tagged i31 anyref exists,

How does that work with arrays of i32ref and i64ref, or structs that contain them? I see that, for an individual ref i32ref or a ref i64ref, an engine could store in the pointer whether there is a 32-/64-bit scalar or a pointer stored in the pointed-to heap location, but for arrays or struct fields, the engine must store that information somewhere else?

To prevent these kinds of efficiencies, you want a coordinated tagging scheme for your types. That's what the SOIL Initiative's proposal does.

I understand that as "The SOIL initiative proposal aims to give the producer a way to influence the tagging scheme the engine uses." To achieve that, unavoidably, there is some added amount of complexity that the current GC MVP does not have (in particular, it adds complexity to the engine implementation while producers get to pick what they need from the spec). Is there potential for simplifying the SOIL initiative proposal, or do you think it cannot get simpler than it is?

Can you give feedback on the scheme I sketched in https://github.com/WebAssembly/gc/issues/100#issuecomment-656880383? I was confused about some things, in particular, how to represent arrays. Is cases meant as a hint for the engine to use a tagging scheme to represent the different cases?

sabine on 20 Jul 2020

@RossTate I believe that forcing imported/exported types to be ref types (by requiring they are deftypes) is a stopgap to avoid the whole polymorphism issue. I believe strongly that we should not preclude true parametric polymorphism in that proposal but should design for the most general case of importing types of unknown representation. That is necessitated by embeddings that need to reference and manipulate values of host types that do not fit into Wasm's type system at all.

What about making i31ref a type constructor instead of a type? We already have ref T and nullref T, why not i31ref T?

titzer on 6 Aug 2020

Oops, so sorry @sabine! I let this get buried.

Okay, now looking at this from a practical perspective for OCaml: why would we need to import/export types for tagged i31 anyref in the first place?

Well ideally a WebAssembly built with OCaml would be able to export its values for others to use. If, say, you built an efficient hashmap (as a toy example), then you'd like to export your hashmap type abstractly in WebAssembly (just like you would in OCaml) along with WebAssembly functions for operating on your hashmaps (just like you would in OCaml).

You mean, some garbage-collection implementations don't put meta-information in the bit-representation of the small object, but instead they put meta-information in the bit-representation of the pointer pointing to the small object?

Yep.

How does that work with arrays of i32ref and i64ref, or structs that contain them?

There's a wide variety of techniques, and which one a GC can use depends on the invariants it can maintain. Some techniques are to always use the same tagging convention throughout the system (this is what OCaml does). Another technique is to have a descriptor at the top of any struct/array informing the GC how to work with that structure. That descriptor can be encoded as bits in a variety of ways, or point to some meta information (or even a code address to jump to).

Is there potential for simplifying the SOIL initiative proposal, or do you think it cannot get simpler than it is?

Yep. We've been waiting for there to be a proper discussion and round of feedback to determine which simplifications we should explore.

Can you give feedback on the scheme I sketched in #100 (comment)?

Ah! Even more sorry! You went through all that work and I somehow missed it entirely. I'm happy to give some feedback. Also, note that we did a case study on how to do typed functional languages here. It's handling of closures is a little outdated though, since the call-tags proposal now provides a better way to deal with the complications caused by currying.

value :=      scheme.new ((field $tag (unsigned 8) immutable) castable

Instead of using $tag here, I would recommend having value declare (extensible (cases ...)) with all the various cases of reference values you have (which should each be marked as castable). The proposal will then take care of encoding these as a tag for you, whether in the pointer or in the metadata on the heap. You'll still want $tag in tuple<n> though, for distinguishing between cases of an ADT.

I was confused about some things, in particular, how to represent arrays.

For arrays, you use indexed fields. For example,

double-array block: scheme.new (parent implicit $value)
                         ((field $tag (unsigned 8) immutable)
                         (field length $array_length (unsigned 32)))
                         (field (indexed $array_length) (gcref $value))

Besides that (and insignificant syntactic things), your sketch looks good to me.

RossTate on 14 Aug 2020

@RossTate Thanks for the feedback! It does look like things are representable in the proposal.

Instead of RTTs, there are schemes, and it is possible to test whether a gcref belongs to a certain scheme, similar to being able to test whether a reference has a certain RTT.

Well ideally a WebAssembly built with OCaml would be able to export its values for others to use. If, say, you built an efficient hashmap (as a toy example), then you'd like to export your hashmap type abstractly in WebAssembly (just like you would in OCaml) along with WebAssembly functions for operating on your hashmaps (just like you would in OCaml).

It seems nice, from a language user's (someone who writes code in a language that compiles to WebAssembly) perspective, to have the ability to create and link modules that expose opaque values and functions that operate on them.

I don't know, if the ability to express and handle these opaque types" must or should be provided on the WebAssembly level. It looks to me like it is still an open question whether WebAssembly should provide all this infrastructure, or whether languages should invent their own abstraction on top of WebAssembly for this.

The only place where I so far know about built-in opaque values being strictly necessary is in the case of WebAssembly system interfaces, where, for security reasons, handles to operating system resources must not be modifiable by a WebAssembly program.

We've been waiting for there to be a proper discussion and round of feedback to determine which simplifications we should explore.

I would guess that, if one could get many different languages to represent their heap in that model, it should be possible to quantify which of the features are not used (or so rarely used that it doesn't make sense to implement them in a MVP).

If there was an interpreter implementation of the SOIL initiative model, that would enable some experimentation. However, that's a fairly large effort, even though the performance of the interpreter is not important at all.

Another way to look at the model is to look at every piece and try to answer the question "what would be
the effect on performance if this is removed".

sabine on 21 Aug 2020

👍1

Gc: Alternatives to i31ref wrt compiling parametric polymorphism on uniformly-represented values (OCaml)

Most helpful comment

All 108 comments

Monomorphization

Polymorphic Recursion

Code Bloat

Higher-Rank Polymorphism

Modularity

Summary

Related issues