All right, so we have Apple. It's going to give us a really good talk about abusing
reburring for fun, profits, and a safe point garbage collector. Take it away.
Thank you. Hello, everyone. I'm stupid excited to give this talk, so I might be talking
a bit fast, and maybe a bit loud, but I'm Apple. I work at Bulmit Automation over in Finland.
I'm a software architect there building a browser-based automation UI platform, so this
stuff that I work in TypeScript actually can bring plants down in cost millions of dollars
or euros a day if it comes down to that's fun. I'm a quiet singer, I'm an open source
enthusiast and I love Albatross, especially. I'm a data oriented design zealot, and I'm also
developing with some other friends, Nova JavaScript engine in Rust, so I'm a Rust developer
by night, and this is basically going to be about Nova, but not quite so clearly.
Okay, quick refresh on lifetimes and borrowing in Rust, so we have lifetimes and we have
references, and those are two different things. You must remember that. It's important.
Lifetimes, it's when you can access something, when something can be used, and references
is how you access the stuff. With lifetimes we have three types. We have the static lifetime,
works for the whole program, doesn't matter when you use it, just don't mutate it
from multiple threads at the same time. Owned lifetimes, that's like a back or a box, starts
when you create it, and when it ends when it's moved out, somebody else gets that and they get
their own own lifetimes at that point, and then we have generics, lifetimes generics, the
tick A that you take in your function, that is valid for the entirety of the function, for the whole
function called. Some of this might be like not quite correct, but it's good enough at
least. Shared borrows work, or they observe A T for the duration of tick A, and nobody is
allowed to mutate that T while it's being observed. Let's not talk about internal mutation,
that's not relevant today, and then we have exclusive borrows, which basically say I am mutating
T for the duration of tick A, and nobody is allowed to observe that stuff. What is reborrowing
then? Reborrowing is the stuff you do all the time. Whenever you use a reference, you make
a reborrow. Always when you pass a reference to another function as a parameter, it gets
reborrowed for the shorter duration, for the duration of that function called. If that borrow
you give escapes that function somehow, then the compiler will, I assume, anyway, start thinking
how this escapes. Is your longer lifetime, the lifetime that you actually have, is that long
enough to actually encompass that escape? When you reborrow a shared borrow becomes the shared
borrow, when we borrowed. But an exclusive borrow can be reborrowed as shared or exclusive.
And if you reborrow as shared, then as long as the escape doesn't keep used or stay used
for too long, you can then use the exclusive lifetime again afterwards. If it does escape,
then things happen. And you can kind of write a reborrowed signature. We don't have this
in rust currently. We might have it in the future. But a reborrow would be you take the
shorter temporary reference to your reference. Here the T is now your reference, your
longer reference. And you produce a new T, which has this shorter lifetime. That's basically
what reborrowing is. You just don't usually see it until today. Okay. Our challenge today
is to build a safe, exact tracing, safe point garbage collector with unrooted values using
lifetime. A bit of a mouthful, so let's go from the top. A garbage collector is a system
of automatically releasing memory when it's not already used. We could even say that the
borrow checker itself is actually a garbage collector. It's just a compile time one. Reference
counting is another type of garbage collector. But in this case, we are dealing with a tracing
garbage collector, which basically works by following references, whatever reference is, through
items and seeing what items have I traced. And then, at the end, deciding, okay, those ones that I have not seen,
those are unused. They are unreachable. So by definition, then they must be unused. Nobody can
find them anymore anyway. And they can be released. Okay. An exact garbage collector is
then one where the tracing of these items starts from static places. And they follow statically
defined references. The opposite or the kind of other kind of garbage collector is a conservative
garbage collector. In a conservative garbage collector, you start by scanning the stack. You
just go through the stack and try to find things that look like references. You probably have some kind
of an idea what a reference looks like in this case. And then you follow those and you maybe you even
scan stuff there to see if these look like references. And then you keep going with that. An exact
garbage collector knows exactly where it should start. What it should scan and based on what it sees
after scanning, it knows where to continue. And then finally, safe point. A safe point garbage
collector is one where the garbage collection only happens at certain times. And in on our case,
because we have an exact safe point collector, and we have unrooted values,
at when we're coming to a garbage collector's safe point, we must have all of our values
in statically known places. Basically this means that they must be on the heap. We have some kind
of heap where we're allocating stuff. This is a JavaScript engine after all. And JavaScript is like
massively heap allocating. So when garbage collection might be about to occur,
all values that you had on the stack must be put on the heap. And then after the safe point has
passed, now you can read them back from the heap. Does that make sense? So values on the stack
must be rooted before safe point. The way you usually would do this in like C++ or C or something
is by not doing this. You would never ever write this because holy price you don't want to be manually
tracking when a safe point's happening and have you rooted all of your things. So you would just
always have rooted things on the stack. Or you have a conservative garbage collector which will just
scan the stack. Rust gives us lifetimes and we can use that for a great effect. So let's look at
code and now let's hope that my looking at code actually works because I had a system. Oh yes,
good, good. I'm not actually seeing this on my screen. So I will be looking at the code with you.
So we're looking at my code editor here directly. Let's open this. That's not open that.
Step one. We have our arena. That's like a heap allocated stuff. It holds some stuff there and
we get an exclusive reference to it. And then we have some kind of API. This get function which
gives us a value from the heap. It doesn't matter what kind of value it gives us. It doesn't matter
what it is. But in this case, it's giving us references. It's actual honest guard references to
apparently U32s in the heap. And what we want is basically in this case, these are references.
So it's not going to work. But what we would want is that when we get the first item from the heap
that we can print it and then we can get the second value from the heap and print that as well.
And we would still be able to print this first value as well because we're just kind of
we're just making changes to the heap. But the heap guarantees that these items are not
they're not going to be invalidated before garbage collection happens before we enter a safe point.
And the get function in this case. It takes an actual mute self.
So what we end up with is that we can indeed run this code
or go wrong.
Yes, it works. But when I try to print the first value after I've added the second value,
it no longer runs because obviously I'm mutating the arena and the reference no longer works.
Because these are actual references and this is correct that it doesn't work.
So this is not really much of the garbage collector yet.
So let's take the route taken by the talk a couple of,
couple of minutes prior or 10 minutes prior, maybe an hour or two prior.
Let's just take use sizes. So now our first function here just returns a use size.
It still mutates the arena, but it just returns a use size. And we get a second value and now,
with this we can print the first and the second value before we call garbage collection.
But unfortunately, we can also use them freely after we call the garbage collection.
And we see a panic because it's like over indexing.
That's not really what we want.
Okay. Let's try this again.
Yep. So this is a bit error prone and this is like how you would do it in like C++ or something.
You basically just get like values that have no safety to that.
So we don't really want to do this. Where did my mouse go?
Okay. But maybe we can add a lifetime to the value that we take back.
So I have created this arena ref type here and now my get function returns an arena ref.
We can you can see it it just takes mute self and returns an arena ref.
And the arena ref has is just a use size with a phantom data reference inside of it.
And now things will magically work, right?
Let's see. I can't even compile it anymore. I can't even print the first value anymore.
Why? Because the get function it takes a mute exclusive access to the arena.
So it's saying I will be mutating the arena.
Then it returns the first value arena ref.
And that it makes the lifetime of the mute exclusive reference escape to the first value.
Which then means that I think I'm getting echo.
Which then means that the first is saying as long as I live as long as I exist, I keep mutating the arena.
And then on the next line I'm trying to say hey, could you observe the arena while you mutate the arena?
And Rust says no, you can't do that.
No, let's not.
So this is like this seems, this isn't just raw.
In software development there's a rule that anything can be solved with extra in direction.
And I think anything can be always solved with adding an extra lifetime as well.
So maybe if we add like this token thing, this token reference here, it's just an empty struct.
Zero choice type. But I take a reference to it. And now my get function
takes the token by reference. But it takes a shared reference.
The function here takes an actual exclusive reference and then below my GC function here takes an exclusive reference again.
And now now things like this seems like it might work.
On the first line, I've kind of helped fully written these out on the side lines if you have been reading them.
But on the first line, when we get the first item, it's lifetime kind of, it's own lifetime.
And this tick one here starts. And then when we take the second, it's lifetime tick two starts.
And these are both bound kind of to the tick A, but only in a shared way.
So it's fine that they are in existence at the same time. So we can indeed run this code
and get the values printed out at the same time before we do garbage collection.
But then if I try to run garbage collection and then print the values, now no longer works.
Because now Rust is saying, wait, you've you've excluded exclusive access to the token.
And then you're trying to say that I can still but like keep references to it. Not going to happen.
No. So this, this looks like it will work. Now we're kind of, this is basically us getting the garbage
or getting Rust to understand how our garbage collector works, garbage collector works.
Values are valid until garbage collection might happen.
Okay. What happens if we pass these arena refs as parameters? Because I mean, when you have like an
actual function, it would be nice to have actual parameters. Imagine a JavaScript engine where you
can't pass any parameters, kind of useless. Maybe it's not too useless compared to the usual
JavaScript, but I mean, anyway. I don't know how I'm for time. But so what we have here now is that
I've added this Act 2 function, which takes the first and second values. And then if we look at
the Act 2 function, it just does what we did previously in line. It prints the two values and then
does G.C. And I've written out the lifetimes here because obviously like this should be bound together.
Arena refs, they should be observing the token. So like this is how you do it, right? Makes sense.
So if we run this, it's working before I didn't even call Act 2. Now let's do Act 2. And it does
not compile. Why? Because I am passing the arena refs, which say I am observing the token,
to this function. And then I pass the token exclusive. The Act 2 function takes it as exclusive.
So I'm also passing in the mutation. So basically I'm saying, hey, could you observe this
token while you mutate it? And Rust does no, no, I can't do that. I'm sorry, Dan or Dave.
No worries, no worries. I know how to fix this. We can do some UB.
Yes, it's time for the best function in Rust standard mem transmit. Yes, yes, this helps us.
So I take the arena ref and I just say, don't worry about it. It's fine, it's fine. Now Rust
allows me to actually call this function. Yes, Act 2 is on. And now, obviously, if I
uncomment these prints here, then it will no longer, oh. Why isn't Rust help? Why? Why aren't they
binding to that together? That should be an error, right? Rust should be saying you can't
observe the token while you also have it shared. I've added these tick A's here into the
beginning. This should be the same thing, right? Well, it doesn't work that way. As I said,
somewhere in the beginning, the tick A is valid for the duration of the call. For the
entire duration of the call, there is no, these are not bound together somehow. These are not
the same lifetime or not the same borough. They are the same lifetime, the same duration.
But from Rust's perspective, these are no longer connected at all in any way. Well, no worries.
I know how to fix this. Can you guess? Maybe you can.
Yes, it's the second best function in Rust standard, same transmute. So, I take the arena
riff. I don't, at this point, I don't give a damn what kind of a lifetime it has inside of it.
And I take a shared act borough of the token. And I say, hey, arena riff, you're now observing
this token. If you want to be like actually, if you actually want to think about this,
like what is actually happening, I'm just creating a new item, new arena riff. So, I'm creating
a new own lifetime, which then carries on or observes the token. And now Rust will indeed tell
me that you can't do this. I'm sorry Dave, that's forbidden. So, okay, we can, we can pass parameters,
requires a bit of lifetime plans meets, but it's fine, fine. Okay, okay. Well, what about returning
values? Sometimes it would be nice to get some results as well.
I added to the act two function here, just a return of a new arena riff. This is just one more
arena get, get called there at the end. And this works wonderfully. It prints, I had the unbind
stuff in the function already. So, it prints the first and second and now the third value here.
And then I can, I can still add like or get more stuff from the arena. And if I try to,
when I wear it, my cursor go again. If I try to print the third value after GC, it obviously doesn't
work, but it does work before the arena get function there. And then if I print the third value
here in the middle, then it obviously still works. Oh, no, no, it doesn't. Why doesn't work?
Well, it doesn't work. If we ask Rust, why doesn't it work? Mutable borrow occurs here.
And immutable borrow occurs here. Kind of borrow token is immutable because it is also borrowed
is mutable. Mutable borrow later used here. So, the third value here, when I take this, when I call
act two, it escapes the exclusive reference to the token or its lifetime. So, basically the third
value there is saying, I am constantly mutating the token. You are not allowed to observe it.
Damn. No worries. I know how to fix this. Yes, yes, yes.
There we go, much better. Yes, now it works perfectly. It's always fine, always fine.
So, we are actually, have I been going at this like power speed? I don't know.
There is one thing that I don't particularly like with this, and it's the reference. The token
reference is a real actual pointer, which is being passed from function to function, but it's never
the reference. It has no actual real use. The thing we want is the lifetime, only the lifetime,
not the reference. So, what we can do is we just turn the token to a phantom data entirely.
Struct, which contains a phantom data of a borough. In this case, it's an exclusive borough
there inside the phantom data, but the exclusivity there doesn't actually matter. It's just kind of foreshow.
And then this token, exclusive token, struct has a couple of methods. It has a method shared,
which takes a temporary borough of self, shared borough of self, and returns a shared token,
which contains a phantom data of a borough reference. So, essentially that shared token there escapes
the lifetime of that temporary shared self borough.
And then there's another function called a reborrow, which takes an exclusive self reference,
and returns a new exclusive token, which now escapes the lifetime of that exclusive self borough.
And with these two things, the same code that we had before works perfectly well.
No more tricks, no more jokes, no more horrible standard meme transmutes. They're still there, of course,
but I'm just not showing them anymore. This works perfectly. And we no longer have that unnecessary
reference going out. The zero size type that we're passing in, except for one Windows calling convention,
it gets completely optimized out by the compiler. It does not exist at runtime,
which is perfect because this is not runtime stuff, this is build time stuff.
But so far, we haven't really actually gotten to the point of like, how is this garbage collection?
What is, how does this connect with garbage collection? Of course, we kind of see that this is
keeping us from holding the values beyond points of garbage collection, but what if we do need to
use the values after garbage collection? For that, we need a new type and a new lifetime,
because all things can be sold with another lifetime. So I've added here to the token,
it still has the first lifetime, which this, I would be calling it the garbage collector lifetime,
and then there's a second lifetime, which I would be calling the scope lifetime.
And the scope lifetime is never kind of used exclusively, it is always shared, so it is basically
just valid for the whole duration of this call, and then I add this scope function.
And the scope function is a takes the arena ref by value, takes a shared token,
so this says I will not call any garbage collection at this point, and then it returns a scope
arena ref, and the scope arena ref is now bound to the shared tokens second lifetime.
IE, it says that this scope arena ref is valid for the duration of this entire function call,
and maybe even beyond it, that if you return it, it can escape. And now with this scope arena ref type,
it has a get function which can be used to get the arena ref back from inside
the scope arena ref. And what this scope function actually does is that it takes the reference
that you have, puts it on the heap, and then one garbage collection might have run, you read it back
from the heap. Now we have scoped, we have rooted, this is scoped rooting or rooting
or values when garbage collection might, might be happening or is about to happen.
Yeah, that's most of that. Actually this is like a good point, good place to ask some
questions if you have a question about the code. Why? That's kind of a good question.
The why is basically based on my experience from writing a JavaScript engine,
most values don't need rooting, and every time you root something,
you waste a bit of time. So if you can work with unrooted values, most of the time,
you probably should, and a lot of engines will like fire force for instance, has they have an
internal link tool which basically is doing the same kind of thing. It's like a whole program
optimizer which tries to make sure that no function that doesn't expect garbage collection
can ever call into functions that might end up calling garbage collection. So they kind of do this
same thing, but just in a very manual way. But this is pretty ugly, I must admit.
There are things that can be made nicer. So the rebaro and shared calls, those are the
one of the main things that could be made nicer. There's an RFC for auto rebaro trades.
If you can help me push that along, I'm willing to push that along, but I probably need help with that.
I don't know, rust person or rust current, whatever. The unbind calls for method parameters,
that could be done with not too much new stuff, I think. Interprocedural rebaroing is basically
what it would be. I actually have an extra example where this comes up in normal rust code.
And then the returning values having to do unbind and bind again, that needs a whole new feature
which probably requires quite a bit of stuff. The problem there, why we can't, why can't that
happen automatically? Why does it need to keep exclusivity? It's basically because cells exist.
Internal mutation is the root of all evil apparently. Even if you are given an exclusive
reference and then you know you don't use it in a kind of particularly bad way. It's actually
possible that the exclusive reference you were given is created in a particularly bad way,
which if it was automatically kind of released when you return a reference based on that,
you could run into you be with that. This is probably the point where people start standing up
and no one can actually ask questions. So I will just say that on GitHub, the code is there available.
The Nova JavaScript engine which we are developing, we have our own website there where you can find
more or less interesting blog posts about how and why the engine is built and then our code
GitHub is also there. If you have questions, throw them up. If you don't, I don't know,
come forward to me afterwards. I would just say that could we stay seated until the questions are
over. We couldn't do any questions because of it. And apparently I kept timing this at home and
I could not keep it in 40 minutes and now I'm like 33 minutes, one.
Simply in a way to roast and not any other language.
Okay, that's an excellent question and I'm very happy that you asked it because I was actually
telling this to my co-workers just this week. They loved hearing about it. I was telling you.
Roast is basically the only language that I know of where this can be done.
So the unrooted values on the stack with an exact garbage collector is such an insane thing
without the borough checker. With these unbind, bind, that song and dance, it can be made work.
It's manual. It's still somewhat error prone, which is also partially why the engine does not
actually use the lifetime guarantees to do unchecked indexing. All indexes are checked because
you probably make mistakes and we do want to crash with that. But yeah, like the borough checker
is an essential tool here to enable this kind of system. And in a more kind of performance
focused view, the conservative garbage collector's are generally apparently faster.
And I believe one of the reasons is that exact garbage collectors have to jump through a lot of
hoops to get that. I either need to do a lot of routing and so on, where conservative garbage
collector's don't. And I'm kind of hoping that this might actually turn the time.
There's no more questions. Let's thank Apple. One more question, sorry.
So does this work on Nightly Rust? This is entirely stable Rust. We do not have nightly
features turned on at all. And that's basically by design. I don't really want to go to the
nightly train and then never leave.
And, naively, it feels like the unbind and bind sung-and-dance is ever prone and might undermine
most of the benefits you're getting from the borough checker. Do you want to speak to you experience
some practice on that? So, like, yes, it does indeed, it does indeed undermine the kind of the
benefit. Or, it's a necessary evil. I wish we didn't need to do it, but the borough checker is built
with the idea of working with actual references. In our case, these are not actual references.
The values are actually indexes into vectors. And we never compact those vectors. The vector
is never change values. They can only add values before garbage collection doesn't happen.
So that's why we can say that these are valid values. If we make a mistake, the worst things that
can happen is that either we overindex and crash, or your value, your object changes to some other
object. It's still the same type of object every time. You can't change to another type.
So, there is no actual, there is no, like, type safety problems here. No type confusion is possible.
So, that in that way, I'm also kind of not too worried about this. And if you really wanted to,
you could actually write the same code without transmutes. You would just take out the internal
index and put in, like, create a new arena ref, which contains that index. The transmute is
just a bit easier for reasons. Okay, if that's it, then thank you. Our pro for this great talk.