Okay, good to see y'all, my name is Andy Wingo, and this is a talk about a new head of time
compiler for WebAssembly, it's called Wastrel, it's WebAssembly without rentime, and once
you start the talk with a little demo, let's see, it's my terminal, it's where they've
mostly, I don't actually use a terminal inside e-max, I don't use many tools, because
I'm not very smart basically, so we have, I'm in my Wastrel directory, I have to run
inside a little environment, okay, Wastrel, I want to run a little WebAssembly file, and
I don't know if people are aware, but WebAssembly is a list, and it has this set
textual format, which is one-to-one correspondence with a binary, so you can write it
as text directly, and this is called Wat format, or the assembly text format, so I opened
up the Wat, obviously, I don't have my e-max very well configured either, still in the
fundamental mode, I have to go in schema, though, because Wat has parentheses, and I don't
know how to write things with parentheses without par edit and all these niceties, so writing
a WebAssembly module, you start with a module, usually, it's actually optional, but it
expands out to module, and we're going to do a hello-fuzz them here, so a funk hello, we're
going to take no parameters, so you can put no parameters or not if you leave it out, it's
not a problem, no results, okay, we're going to do a hello world here, let me just say
call, and we're going to need to call some sort of procedure that outputs things onto the
screen, and as you might know, WebAssembly doesn't have any capabilities in and of itself,
you have to provide it with capabilities, including the capability to output to the screen,
so we have to import, define a function, and say it's, well, call it pk, actually, it's
kind of a nice name, and we're going to import it from, I don't know, some debug library,
we're going to call it debug stir, and it's going to take as a parameter, and this is the
problem with WebAssembly, it's like WebAssembly 1.0, you have N32 and 64, float 32, float 64, and how
are you going to get a string into that, and this is the new thing in WebAssembly now, is that we
have structured data, which is managed by WebAssembly itself, we almost had a good thing, in
the sense that we almost had the ability to have a string data type in WebAssembly itself,
and we didn't, we haven't managed to get it in yet, but we still have it in the tool chain
that, that WebAssembly uses, this actually lowers down to an array of bytes at some point,
so, has a parameter of a restring and no results, so we're going to import it from some
standard library, so we're going to call pk on string.const, hello fuzz them, new line, all right,
and we're going to start this WebAssembly module with the hello function. Now, if I didn't
fuck up here, then I should be able to run this, let's see, last row, what is this, hello something,
hello fuzz them, dot wet, does that fuck up? Ah, yes, there's one thing,
expose the, talk about this in just a minute, hello fuzz them, oh thank you, y'all are so nice,
that's not a little demo, so I'm going to get back to what the demo is, but I have to start with
some story time, right, so let's go on on this side with me, I'm a long time commentator of the
Gauss game invitation, Gauss uses the boom demo's Weiser Collector, the BDWGC, it's very reliable,
we've had almost no problems with it over the 20 years, I think, that we've been using it, but it
has some limitations, it's performance is not that great when you have multiple mutator threads,
it has a relatively inflexible memory usage profile, you can't really get some very
tight heaps with it, it can't move objects, it can't compact the heap, and there are new things,
and I say new, but I realize that actually the new thing that I saw that I heard of at one point
in was inspired to work on GCs was this design called Inix, it's a design for a garbage collector,
and I'm like, it's a new design, it's 18 years old people, the time pass is really, really fast,
but some of the work, precisely that we build on in this garbage collection work was
happening a bit later, it's a kind of family of papers, but that one was the first one,
so I always wanted to write a garbage collector, and that's probably actually,
it's not one of these three bullet points here, but the problem with Gauss using the
boom collector is that I didn't write it, which is not a good reason, but I've always wanted to
work on a GC, and so I wrote a collection library built around this Inix inspired collector,
and this collection library is called Wipit, Wipit is a embedable GC library, it's designed not
to link to, but rather to include into your project's source tree, it's mainly designed for a
project written in C, for a number of reasons we can talk about, now there's no dependencies,
whatsoever, and the way it works is customizable, it compile time, you choose the collector,
you choose the object representation, you specify how you trace your objects, you specify how you
get your, how you identify the set of roots from which you need to start tracing, and that's
such, it also contains a collector of collectors, collection of collectors, so I have another little
demo here, so this is one of these commands that's kind of like the get sort of interface,
and I have only really two options, I two sub commands right now, I have the run in the compile
commands, so we're going to do a compile. Wastoral compile, and I can specify a GC with which to compile,
oh man, it's kind of wrapping around my screen here, but I need an E equals here, GC equals help,
help us them. Watt, let's compile it to hello, fuzz them, and I don't know, but,
I specify in GC equals help is going to get me this list of available GC augmentations here,
which you can choose, when you compile your, your Wastoral module, actually not all of these are
appropriate for, for this, we'll get into this in just a minute, but I'm going to choose, for example,
BDW, for example, so hello fuzz them, BDW, um, that work, okay, maybe I'll choose another one,
MMC, which is another one of the main collectors in Wastoral, okay,
hello fuzz them, star, all right, so we got the BDW one, compile the 70 kilobytes, and MMC, BDW is
whip it's collector, but implementing whip it's API is the bomb library, so we're dynamically
leaking to the bomb collector, for this one, we can run both of them, hello fuzz them, BDW, and C, okay,
great, let's strip them both to get an idea of the size of them, so hello, I think about a
father it puts in debugging symbols in BDW and C, let's look again, get an idea of what the size
of these things are, so this is about the minimum you can get to with a with a Wastoral binary,
the BDW one's 27 kilobytes, and it links out to the libgc, oh you can see, LDD on your hello fuzz them,
BDW, and because I'm on geeks you can't really see anything, but the important thing is this,
libgc here, so this one's looking to the libgc, and the other one is not, right, it links to
what is this, LD Linux, libgc itself, that you see support library, libm, and I don't know what
Linux video is, we'll see, right, so that's an example of choosing the different collectors,
in whip it, there are three main collectors, right, three main collector variants and main,
my quality collectors, because I've tried many things, but these are the ones that they're actually
good, first one is a parallel copying collector, so semi-space collector, but it's heap is organized
in a block structured way to allow for parallel both mutator and collector threads, it's a very
good collector, but it requires a memory, and it requires the ability to precisely enumerate all of the
edges in your heap graph, so that when collection time comes it can relocate them from from space
to tree space, so it rewrites all the references at every collection, it's much faster than you
would think though, the other one is the in-ex inspired collector, the MMC, and they're a mostly
marking collector, because it mostly marks objects in place, but sometimes can compact them,
and talk about these in some previous files and talks, I'm not going to go too deep onto them,
and the other one is using the bone collector behind, and so I showed an example of using
MMC and using BDW in this case, and the whole pitch here now is that this is what I would like to
believe, and I haven't fully proven this, I'm not going to show a bunch of graphs today, but the
pitch of this collector is that MMC collector improves on BDW, and that allows you to access
tighter heaps, it scales better for multiple user threads, and it can compact the heap, so you
never have that worry that's like, why is my memory like this, what's the reason, and BDW is not
really something you can introspect and find that out, and whip it was developed with the support
of NONET, thank you very much, and also with the Guardian, I have a bit of paper on this, oops,
so if you, I'll share the side link later, but if you search for like,
a whip it isn't in the name, this is going to be hard to search for, anyway, so whip it was made
forgot, right? I designed it in some of the ways so that I could replace the use of the bone
collector in-gile with whip it, and I, last year, from the period of about April to August,
I actually did this, I replaced the bone collector with whip it first, with whip it, but using
BDW, and then whip it, but using MMC, the MX-DRIVed collector, but in a fully conservative mode,
so not precisely enumerating edges on the heap, and then moving to a mode where it scans the stack
and static data, conservatively, but heap edges are precisely enumerated, which allows it to
actually improve on performance, and this took about 300, 350 commits or so, not sure how many of
those are merge commits, because I was merging in whip it periodically on this, and I need to,
I got it to the point where it's pretty good, and I still need to do some evaluations on it,
but I need to do some incremental merging of this work, now that we are on code bird,
and can do like merge requests and proper code review and such, for a push for a gal fore, so
I'd love to talk about this in the next couple of days of the geek states, if anyone's going to
be there, or afterwards, whatever. Right, right, right, but this is like Alice's restaurant,
and so this is a talk about Wastrel, right? Not a talk about whip it. Wastrel is a funny thing,
it's a web assembly to see compiler, right? So you didn't actually see the see compiler
being invoked when I, when I invoked Wastrel before, but it just takes care of that itself.
It's a Wastem to see compiler, but which embeds the whip it collector for managed data types.
Wastem to see compiler with whip it, okay.
I don't believe it was narcissism that I started all of these projects with a W. It really,
Wastem, I didn't name that, whip it was named because it was a work in progress,
garbage collector, and Wastrel because Wastem things are often named starting with the W.
It's what I'm telling you today. So Wastrel is not, it's not like the first,
and I'm sure it's not going to be the only compiler that's like a Wastem to see compiler,
there's a number of them out there, originally there was Wastem to see,
and then there's an update version of this called W2C2, improves on a number of ways.
Our differentiator for the Wastrel project is that we aim to do Gc, so I'm doing whip it,
and it's built in Gile on top of the WebAssembly libraries that were made as part of the
hoop compiler. So all of that Wasm work allowed us, well, allow me to make the first version
of Wastrel in a couple of days, right. The first version of Wastrel that couldn't do anything, of course,
because Wastrel is essentially a baseline compiler in structure, and I've written baseline
compilers before, and I've written things based on the who-wastem libraries, the process,
Wastem modules, but actually getting it to do something, took a little bit longer,
in the sense of wiring it up to other capabilities. A little bit more in that minute.
How does it perform? It's, it's great, right? No, no, no, I mean,
say you can probably, I haven't done a full battery of tests, but say you can pass something like
core mark, right? You compile it native, and then you compile it by a Wastrel or, or Wasm time,
or Wtc2. Wastrel is like a few percent off native, like maybe three, four,
and Wtc2s about there, and Wasm times significantly below that in my tests anyway. So like it,
it is a state-of-the-art compiler in that sense. It, and it doesn't, on the features of Wasm,
for example, memory isolation, and it does so, because it, a lot of the more complicated Wasm
run times allow you to instantiate modules at runtime, but because this is a fully ahead of time
compiler, we can fully allocate everything statically, we can fully allocate all of the memory statically,
and, and, and thus at runtime reserve, a gigabyte map regions for the memory, for example,
so you don't have to do any runtime checks that, that your pointers are in balance, for example.
Yeah, hey, I'm sure a lot of people have worked in C here.
My, my approach to C is, is much, much different than when I learned it poorly 20 years ago.
So I, I just wanted to have a little slide here about if you're working with C, this is what I've
found to work for me in recent projects. So I, I think you want to heavily lean in,
trust the optimizer, for example. Like sometimes we are when writing C or when generating C,
we try to smash everything together, right, because you're like, okay, we're just going to
inline everything in, in, in an expression, because that, that way the compiler is going to do things,
good things about it. We can actually use abstractions in, in terms of static inline always inline
functions, and it, and it, and it works great. It burn away completely a compile time. And, and as such,
you can have extractions without runtime overhead, and, and, and, and, and, and avoid a lot of, like,
the pathological, um, undefined behavior stuff in, and C, for example, about, uh, casts,
completely remove casts from your program, uh, both implicit and implicit, always go through
static inline functions to do so, just to make everything, um, explicit. If you need to read
from memory, you can always mem copy, uh, even if it's four bytes, in the case of web assembly,
and the compiler will rewrite that to a four byte load if it can, but that, that follows, like,
the C memory model. Um, and absolutely avoid, um, like, using any kind of integer data type to represent
anything of semantic value, like, always wrap that in a struct of one value, and it will get
compiled just as well. But that just means, like, you've given a name to what that is, and it won't
get confused with any other U.N. pointer, or, or, or, enter, whatever that, that is, uh, that might
implicitly convert to that value. And, and the goal is, like, so Wasm as a type system is a strongly
typed, and, and, and the type system, like, is the reification of a proof that when run at runtime,
it's not going to do a number of things. And, and if we manage to translate the types from Wasm
into the types and C, then I've also translated that proof, right, like, because I've eliminated
a number of sources of, of errors that GCC can actually, uh, check that, that my compilation is,
preserve these properties for me in a bit. Of course, you know, you also want, like, sanitizers
and things like this, but, but you can lean into, and, and the C type system a bit better than,
at least, at least what I was used to doing, you know, 20 years ago with a bunch of castes and stuff.
Um, right, so the question is, what do we do about a standard library? Uh, with, with C programs,
there's a C standard tool chain called the Wasm SDK. Uh, it's a version of clang plus, uh, a C library,
and you just compile like clang with target Wasm 32. Uh, Wasm 32 wasn't p1, for example.
And, and that runs great in, in Wasm, I can run LVM, for example, uh, with, with Wasm,
takes forever to compile. This is, this is another issue, but, um, uh, but it was really excruciating
implement, um, because, uh, the Wasm interface is essentially what you're given is the, the reified
artifacts of, of an API, API lowering in terms of N32s and floats and stuff. You don't actually
have pointers or meaning when, when you're, when you're implementing Wasm unless you, unless you
implement other tools. So, I, I kind of running in circles here, but that was very, very annoying
The one, the one thing I would note that was that, uh, Wasm can expose a file system interface,
and, uh, I, I do so with Linux namespaces, so it only runs on Linux. Okay, better force.
Uh, if you need access to file system. Okay, get back to GC. Uh, Wasm 1.0 was number of instructions
that can operate on an array of bytes. We're up to 3.0, anomaly, now, which is linear memory,
but also exceptions, manage memory data types. And so, uh, here's, here's, for example, a
definition of a pair type, right, in WebAssembly. Uh, well, I can't actually highlight it. There, uh,
I have a, a cursor. So I have a, a pair type. It's a structured data type, a product type,
and it contains two fields. I didn't give them names here. Um, X is in the type hierarchy of WebAssembly,
values that can be prepared, that can be compared by identity. You can, you can, you can apply
ref X on them. Um, so it's like, it's a pair of any values, essentially. And to const, to make a pair,
I write a function that takes as a parameter A and B, my X refs, and then I return a pair, and I, I,
I return it by, it being the last value in the, in the function, and I just call structure new pair,
and I, and I give it the operands as organs. It's, um, it's a higher level assembly, and it's an
interesting target for for compilers, because you can run this on the web. You can run it on cloud environments,
and you can run it with last row now. Uh, we have, uh, in addition to structs, there are also arrays.
Subtyping is a whole thing, um, recursive types, immediate, uh, casts, and, and it needs stuff.
So it was, it was, um, took me longer than expected to add, uh, Gc to last row, because of subtyping,
because you have, like, um, well, in wasm, you have typing judgments that are formally verified,
and to translate those, like subtyping into C, uh, was, was very annoying. Um, but, uh,
it managed to work, and so Gc can check our work. So here's an example, right? In, in wasm, Gc,
you have three top types. So three type trees, sort of, or lattices, right? Uh, there's any, and
external, and funk. And they are, um, yeah, they're, uh, external, and any can be interconverted,
but funk cannot, and this is based on, uh, reasons of how things are represented in, um, in, in
web browsers. And so under any, you have x, and then under x, you have i31, which is, uh, 31 bit
immediate. You have strokes and arrays, right? And, and we represent them as, you know, uh, C
strokes, which include the parent just, uh, directly like that. Um, and functions, they include just
the function pointer as a value, and I hear I have to use a voice star for reasons. And, and functions
are the, are the pointer type that actually bears the type in the, in the reference itself. But for
objects, their type is in this, uh, tag word initially, and then so you have an object representation
hierarchy as well. Like you have any object, and instructs are any object, and arrays are any object,
but also with a length field. And so, that was a header that's like the sort of base types,
and then last rolled generates a number of, uh, implementations for these types. Uh, uh, this,
there's some, um, routines on the, on the base type. So you have, you have noble types, and non-noble
types, and you can check if something's immediate, and then you can, you can get an object reference
out of a, uh, of an any rough. I'm going a little fast here, because we got, you know, a couple
minutes. So let's step through some, some generated see here. Here we have two types. One is a,
uh, as type 0 is a struct, it has an i31, i32 field. And then we have type 1, which derives from type 0,
which has the same i31, i32, this is supposed to be i32, excuse me. But additionally has a,
uh, a ref to type 1, so there are a cursive type. And so that reason we've, we've wrapped it in
rec here. Uh, what is this generate? We generate, uh, some, the ref types for which we can refer
to these values. So type 1 ref, derives from struct graph. Uh, type 0 ref, derives from struct
graph, type 1 ref, should derive from type 0 ref. You know, excuse me here. Um, and, and the representations
of the actual objects, uh, type 0, directly from struct, type 1, this should be directly from 0, excuse me.
Um, and then we can have our type predicate. Because we're at a header time compiler,
we can allocate type tags continuously, uh, via depth or search, so that a type test can include
subtypes. Like I just have, uh, what are two comparisons in, uh, in the source code, but which
compiles that one comparison, um, here. Because the range of types has a continuous range of, of, of,
tags, um, having sorted the tag values according to the type tree. Um, and then you can, when you
create one of these values, you can pack it into a ref with loads of, of, of, of braces, you know,
so, as you can tell, web assembly is definitely a list here. Um, and, and here's the, the one,
instance of, of, of, of, of, of whip it code here. You pass a mutator around because we're,
static the allocating just one thread currently. This is a global variable. Um, you allocate the size of type
one, we're telling it's a tag allocation, initialized tag word, initialized field 0 in the parent,
because that's how the types work, and then we're, we return the pack value. Okay. Um, right,
one, uh, so we have a currently to get capabilities, uh, we look at the set of imports and provide
imports that we know by name. So for example, debugster is something that who uses, for example,
in, in, in, in, in, in, Wazun couple of hoot artifacts. I implement that, and that's what allows us to
know how the world. Um, I'm going to look, you know, soon to building out the hoot standard
lived, including big norms and other things. And, and Wastrel skin, Wastrel can also, in many
other extensions. So for example, the string wrap support that we saw is actually, uh, an artifact
of the tool chain, not of the, an imitation, but like, because it, because it's built on the, on the
hoot, Wazun lives, we can compile the, the text format to the Wazun format on the fly. And from,
from this code, we can still access the Wazun capability. But it's, it's not really because Wazun
often assumes, uh, that you're passing parameters through linear memory and doing so, uh, via,
via Wazun Gc isn't so nice. The status is that it's, it's somewhat demoware right now, right?
I just got it working, right? Um, but it's up on Wastrel. We have never issues for things that are
still dimmed. We're going to be rolling this out over the next month or two. Um, and next up,
other, uh, language runtimes. There's Kotlin, Skala, OCaml, happy to have been any, uh, any of the
facilities that these run times need, uh, from web browsers. So we get native compiles for them as
well. With hoot, uh, since we can compile a guy, essentially, to web assembly, we now have a web
assembly to native, uh, target as well. Interesting. Uh, benchmarking some more Wazun features.
Um, as you saw, I had to expose the root directory, uh, when I ran things, because the Gc
wants to read proxail from app, and as I need to fix, uh, the file system sandbox,
with regards that you see, some bugs, more Wazun standards, stack switching, which is essentially
fibers and drilling conditions, drilling situations, in the Wazun standard, and to be active,
which is meant in helping evolve Wazun standards. So, and if you're writing a new language,
consider, generally, Wazun Gc, because it's a growing ecosystem. There's not so many things right
now. You'll be the center of attention. If you are targeting Wazun Gc already, then let's talk
about implementing your standard library. And if you are implementing a language runtime,
and you need a garbage collector, let's talk to you. So, thank you for a much, uh, I can take
a question so we can ask you a question. Sure, and note. Sure, and note.
Yeah. Yeah. Good question. The question is, uh, just compile and you see how you
have your head. Uh, on one side note, um, on the other side, uh, some things are unavailable to us.
For example, uh, implementing exceptions, you would like to have a side table mapping program
counter to ranges of of exceptions, and I'm not going to be able to do that, right? Uh,
or because I am not using handles in all of my GC objects, like here, for example,
if, if I had a moving GC, this should be a handle. This type 1ref should be a, uh, should be a
relocatable pointer, because it's present before I allocate a value. And when I allocate,
that can cause collection, invalidating that value. Uh, I could do that, but it's, it's, um,
it's so gnarly to do handles, and I, I don't want to, but it's also a limitation of C, and
that it doesn't really facilitate me, uh, ensuring that each pointer is relocatable, um, in the right
way. So, so the answers have been ambiguous there. It's an okay strategy, I think, but it is not
globally optimum. There are other options.