Tagged GC Pointers

[sebmarkbage]

I noticed in the GC doc that there is no mention of tagged pointers. I wanted to make the case for it. When compiling languages that might heavily rely on tagged unions (such as Rust or OCaml) with GC interop you will have to store the tag as a separate field which can be quite inefficient.

Even as part of the initial proposal for opaque reference types, it would be nice to expose a way to allow a tag to be associated with the reference.

I realize that not all architectures or VM implementations will be able to take advantage of this and might even need to box in some cases. The available space for a tag may also already be used by the JS VM to store its type information. However, for environments that can take advantage, it would be very helpful to have the appropriate affordances.

I could imagine this being related to a possible JavaScript enum proposal as well (which I'm interested in exploring in TC39). That could be the JavaScript representation of this value.

You can do this already in the linear memory, just mask the pointer before use. I have been battling for years now to get this use case considered, and could use support, and I have a plan.

[jfbastien]

@sebmarkbage do you have an outline for the enum proposal?

For tag: would you rather have the VM give you a property "N bits of tag available" and anything above you do handle yourself, or auto-magically use side-storage if you exceed an unspecified limit?

[rossberg]

@sebmarkbage, we are thinking about the possibility (although you probably don't primarily mean tagged pointers but tags in object headers, plus tagged integers for plain enums). It is gonna be rather tricky, though, because of the diversity of VMs and architectures, and would essentially require making both sums and products primitive in the Wasm type system. Whether that can work out is hard to say at this point.

[sebmarkbage]

@jfbastien I'm not sure yet whether it would be better to be in control or have it built in. Now I also think that it might be better to use object header tags than tagged pointers in some cases. Generally I like being in control as an author but in this case you might have to ship a lot of extra code for each branch so I think I'm leaning towards automagically use side-storage.

I can't seem to find the enum proposal online. It was part of value types but I think we can do it decoupled from value types. cc @littledan

@rossberg-chromium I did mean tagged pointers but now that you mention it, I can see how tags in object headers might be more useful in some designs like V8. I could see it being useful to pick one or the other depending on platform. Tricky indeed.

@rossberg-chromium Could you please be more specific when you use the term "we" as in "we are thinking about" in future. As far as I am aware no thoughts on this matter have been under discussion by this community group and I don't want the work of this community group misrepresented. For example you may wish to word this as 'The v8 team' in future or to create a name for a subgroup giving the membership. If the Chairs have allowed a private discourse to continue that has driven the direction of this groups work without keeping the members informed and in control then could they please hand back their Chair. If there are Chairs not elected by the members then could they please hand back their Chairs.

[littledan]

I'd suggest pursuing tagged pointers in a way that's decoupled from value types or typed objects. For example, you may want to restrict to 2-4 tag bits here, whereas an ADT added to JavaScript should not surface such a restriction. cc @tschneidereit

[titzer]

When @rossberg-chromium talks about "we" he means in informal settings amongst people working on WASM. Considering that I sit 3 meters away from him, it seems like a lot of overhead to establish specific subgroup to bless this communication :-)

I think tagging is less general than sum types. Tagging is also unfortunately tied to the underlying machine's word width in bits. However, unrestricted sum types would leave their value representation completely up to the engine, which some language implementors may be uncomfortable with. So maybe restricted sums (e.g. only over some subset of the primitive types and references) might lead to an efficient value representation without a lot of complexity in the engine.

[lukewagner]

@titzer Coincidentally, "we" (@lars-t-hansen, I and some other wasm folks) were discussing the same basic idea of some kind of restricted sum that always allowed a tagged-word representation.

[lars-t-hansen]

What fell out of a conversation this summer was the idea that in a design where there's a separate heap of gc-able objects (TypedObjects, probably) there might be two new wasm types:

A "Pointer" is an opaque reference (maybe null) to some gc'd thing in the gc-able heap. It is 4 bytes on Wasm-32 and 8 bytes on Wasm-64.

A "Box" is a Pointer-sized triple:

• pointer designator bit (1 bit)
• tag bits (2 or 3 bits, could be wordsize dependent)
• value (a Pointer if the pointer designator is set, otherwise an integer)

Some plausible operations:
boxptr(pointer, tag) -> Box[1, tag, pointer]
boxval(integer, tag) -> Box[0, tag, integer & ~15]
ptrbitof(Box) -> 0 or 1
tagof(Box) -> tag
ptrof(Box) -> Pointer or null if the box is not a pointer box
valof(Box) -> integer value or 0 if the box is not an integer box

Local and global variables in wasm would be box-typed or ptr-typed in addition to current types. Pointers and boxes are not storable in the linear heap.

What I've sketched should be appropriate and performant for many dynamic languages, at least; in practice, 3 tag bits (pointer bit plus two bits) is usually OK, additional tag bits can be stored in the objects after that. The pointer designator and tag bits are stored in the low bit of the word.

It might also be nice to allow an integer box to be reinterpreted as an integer value, this is a no-op if the wasm implementation can prove the box is an integer box, and ditto, to allow an integer to be converted to an integer box by the wasm implementation just masking off the pointer bit. This probably requires pinning down which bit is the pointer bit. Anyway, this provides wordsize-1 bits for integers, the "tag" is just a bit field within the larger value.

@lars-t-hansen I think type test operators are needed so the code could hoist a if(is_int(p)) ... and then the compiler would know that p is tagged as an integer and not a pointer and could optimize valof() without the compiler having to do the hoisting. I don't see a need for ptrof() as the runtime needs to check the type on uses anyway and an integer is just another type to test.

Not sure about calling the tagging 'boxing', as 'boxing' often means allocating in a heap box.

There is an opportunity to also test or mask the high address bits, at the same time that the low tag bits are masked, proving that the index is within the linear heap. I've been battling to get this recognized for two years now, it needs more attention to the type derivation improvements which are currently a P5 in the Mozilla code, could you give that some thought please.

[lars-t-hansen]

@Wllang, yes, I left off type test opcodes because I had not worked that out in my head yet, in particular, whether there would be any performance guarantees associated with such tests. is_int(x) is equivalent to eqz(ptrbitof(x)) which is not a terribly hard pattern to recognize, for starters; is_ptr(x) is just ptrbitof(x). Since it's a stack machine there's a fine line indeed between a hypothetical one-byte operation "i32.isint" and a two-byte operation comprised of two unary single-byte ones, "i32.ptrbit; i32.eqz".

But the exact form does not matter, what matters is the effect. It seems clear that within "if(is_ptr(x)) { ... } else { ... }" the compiler may assume x is a pointer in the then block and an integer in the else block, if it can prove value equivalence of x within those blocks to the x in the test. This does not seem hard for an SSA-based system. But would you require the omission of a tag check within those blocks?

Supposing we allow a bytecode to result in two values; abusing syntax, an operation ptr_i32.ptrof would return a pointer (or null) and a boolean. Then there wouldn't be any question about what the compiler would have to "know", it would just have a value which is a pointer by construction. (There's also a question of a type system for these typed objects and in what sense pointers are typed, but I think that's probably orthogonal to tagging.)

(Digressing slightly, there are additional interesting ideas about whether arithmetic and bitwise operations should be allowed on possibly-int boxes with certain simple tags, with some sort of status code return, comparable to the tagged add instructions on SPARC. i32x2.add k, a, b would result in (a+b, 0) if both a and b are int boxes with lower k tag bits == 0 and there is no overflow, otherwise (garbage, 1). i32x2.or k, a, b ditto a|b. These operations are hard to express efficiently at the wasm level but easy to implement at the hardware level. But it's possible these are too specialized to be worth it -- the case would have to be made that it's interesting to target Lispish languages to wasm.)

As for high address bits... I don't know what you've written about this before. Do you want to implement some type of BiBoP scheme or are you wanting to use the high bits for tags?

(Reference to the mozilla bug you're mentioning?)

[qwertie]

the case would have to be made that it's interesting to target Lispish languages to wasm

If you think that WebAssembly should not attempt to support all programming languages in an effective manner, I think you're underestimating Wasm's importance. Done right, Wasm will take over the world. Wasm will decrease the lock-in power of operating systems, of CPU architectures, and (I hope) of programming languages. Everybody is going to use it, for offline and online apps alike, and for client and server alike.

That world should not be one in which certain programming techniques and programming languages and are doomed to be inefficient and impractical because the WebAssembly designers thought those languages were not "important" enough to support. A lot of the things we take for granted now, as well as features of new languages, started in obscure academic languages and/or Lisp.

Our goal should be to support all languages and all programming techniques with decent performance, say, always within 2x memory and CPU time of the optimal implementation of a given technique. For starters, a high-performance Wasm implementation should be able to efficiently host another high-performance Wasm implementation or the JVM or CLR running inside it (all of which would leverage the outer Wasm engine for code generation), or a Lisp VM or a Stackless Python. Beyond all that implies, I'd like to see continuations (or at least some sort of microthread system), "first-class" labels for fast gotos within a function... well, basically everything in Future Features and then some. While the work has to be prioritized, let's not forget that all of it is important.

[qwertie]

@lars-t-hansen I'd love to get a better grasp of your design ideas for the GC/opaque heap (as well as everyone else's ideas.) What would the effect of the tag bits be in relation to the WebAssembly VM?

How do we make an "all purpose" VM? something that

• Supports precise, compacting, generational GC
• Supports array slices, and pointers that refer to the middle of an object or array, not just the beginning
• Supports object systems based on both "thin" and "fat" pointers - or both! (thin pointers rely on type information stored in the object pointed to, while fat pointers store that information in an extra word or two alongside the pointer)
• Allows "maybe pointers" that can dynamically switch between being pointers and integers
• Supports union types efficiently (pointer to A or B or C - it must be one of those, but which one is dynamic)
• To the extent possible under our security constraints, allows client control over memory allocation and GC.
• Supports opaque references - even though this seems to be in tension with the general goal of putting Wasm client code in the "driver's seat" such as letting the client perform its own GC algorithms
• Supports other stuff I haven't even thought of

[distransient]

Disclaimer in that this comment isn't particular to the issue in OP.

If you think that WebAssembly should not attempt to support all programming languages in an effective manner, I think you're underestimating Wasm's importance. Done right, Wasm will take over the world....

I don't think "take over the world" is a great goal to shoot at for Web Assembly (literally and figuratively 😉). Standards are moving more quickly in the world now that a majority of browsers are evergreen, and Web Assembly as it is, is designed to fill a gap in those standards, in a quickly serializable and transport-optimized instruction set for processor-sensitive applications. Focusing on fulfilling that requirement as fully as possible by sacrificing some niceties that would make handling languages that require runtimes and garbage collection easier seems like the reasonable thing to do for me, given that newfound malleability is allowing us to more easily approach new problem domains more quickly and improve our solutions to existing ones as collective insights and experience accumulates.

I don't personally think WebAssembly doesn't have the wherewithal to fulfill these grandiose breadth of applications; I personally grew interested in WASM from the perspective of the concepts of non-browser-oriented internet-based virtual applications that could be shared and enjoyed safely like html and css, without the attachment to the document publishing reality of web browsing. Particularly, I don't think that WebAssembly's core obligations completely remove it from discussion that progresses the possibility of an ISA that fulfill all these kinds of possibilities, whether or not that ISA would be WebAssembly for your given problem domain.

[qwertie]

I don't think "take over the world" is a great goal to shoot

Just my prediction. I'm not saying taking over the world is the goal - I'm saying WebAssembly is uniquely positioned, such that there's a good chance it will take over the world without anyone specifically trying to make that happen.

So, what would the effect of the tag bits be in relation to the WebAssembly VM? What are they for?