Hello, EmacsConf. My name is Troy Hinckley, and this is my
talk on Rune, a Rust implementation in Emacs. We strive to be
bug compatible with Emacs, so you can use the same Elisp.
It's still a fairly early stage experimental project, and
we have some basic things implemented.
Before I get started, I want to talk a bit more
about what the core is.
So the Emacs core, it includes the runtime, the interpreter,
garbage collector, everything used to run the code.
It includes the GUI. It includes all the data structures.
If you look underneath all the Elisp data structures,
there's C code underneath there,
as well as the auxiliary functions
of which there's about 1500. In making this talk, I don't
want to give the impression that I'm saying the core is
outdated or that needs to be replaced or that it can't be
evolved on its own, because clearly it has continued to
evolve. If we look in just the last few years, we can see that
we've added native compilation, we've added tree-sitter
support, we've added color emoji, and there's work right
now to add a new garbage collector to Emacs as well.
Why create this project? Emacs has a long history.
It has a lot of users. It needs to support a big community.
Because of that, it has to be very conservative
about what things it can allow into the project.
Forks like this create an
opportunity to experiment and try new approaches.
This is particularly a good use case for Rust because the C core,
it's pretty well tested. It's been around for a long time.
A lot of the bugs have been ironed out, but when you're doing a
new greenfield project, it's very easy to introduce new
undefined behavior and memory unsafety
and stuff like that. Rust protects us from most of that,
but it also gives us the ability to be fast
and has a strong ecosystem behind it.
Rust is also really good at multi-threading.
Their phrase in the community is fearless concurrency.
They should be able to write concurrent programs without
having to worry about data races. It's also really high
performance. It has a really good regex engine. It's known
for its non-copy I/O as well.
How does this compare to other
Rust and Emacs projects, whether there's been a couple? The
first is Remacs. This project was the first. It took an
outside-in approach. Basically you could take a C
function and replace it with a Rust function and build it
together as one executable. This is pretty easy to do
because they could both talk over the C ABI. You could
swap out functions once at a time. They made really good
progress at first, but eventually they ran into the problem
that as you get down to the really core parts of it, you can't
just replace one function at a time anymore, because some of
that functionality is connected to other things. Like for
example, you can't replace the garbage collector without
replacing the entire garbage collection system. So the
progress really kind of slowed down. Another issue with it
was, is that they were doing a one-to-one rewrite, so they
weren't adding any new features or functionality, just
taking the same code and replacing it in Rust, which doesn't
add any advantages in and of itself.
This spawned Emacs-NG, which was kind of the spiritual successor to
Remacs, where they decided to add new functionality,
the biggest one being a JavaScript runtime,
as well as some new renderers to Emacs.
This is no longer actively developed though.
In this project, one of the big focuses we have is
on multi-threading. The C core itself is, everything is
designed around being single-threaded, all the data
structures and everything like that. Rust has a great
concurrency story. In Rust, everything is intended to be
multi-threaded. That doesn't mean that everything has to
run on multiple threads, but you can't write something that
is limited to only running in a single-threaded
environment. So this makes it really easy to use all the
existing packages and build something that is
concurrency safe. which is what we've done here,
and that was relatively easy to do.
But adding it to Elisp is the hard part,
because we've got to come up with a good model
for Lisp, and Elisp is just a giant ball
of mutable state. We need to find some
way to tame that so we can make workable concurrency
out of it. There's really two ways you can do this.
One is what I call the no-GIL method.
This is what Python is doing, where
you take all of your data structures, you make them
concurrency safe, and then you just leave it up to the
programmer to decide what they're going to do with it.
They've got to build safe abstractions on top of that.
One of the big downsides with this is that
it comes with a pretty high cost.
The last benchmarks I've seen is that by making
everything concurrency safe in Python, single-threaded
code is about 20% slower in some benchmarks.
Since most code is single-threaded, this has a big
performance impact for most code that isn't taking
advantage of the multi-threading. The other thing is this
introduces a lot of nasty concurrency bugs because you can
have anything mutating any part of the data from any thread,
even if you can't have memory unsafety per se.
The other option is actors,
which are a really known way to approach this,
where you trade some of that flexibility that you get
with fully concurrent for more control and. Code and
functions are shared between all the different threads,
but data has to be passed along channels between different
actors.
We want the functions to be shared, and this
should be pretty easy because we don't mutate functions
like we do data, except when we do. In Lisp, functions are
just lists like anything else. So you can mutate them
just like lists. Even if you're not talking about
interpreted code, like if you have a native compiled
function, you can still mutate the constants inside the
function. For example, here we have a function returns a
string. We take that string out, we mutate that string, and
now the function returns a different string. In Rune, we
enforce that all functions, their constants are
immutable. You can't mutate the insides of a function. You
can still swap out functions and redefine them, but you
can't mutate the inside of a function. This enables them
to be safely shared across threads.
However, there are some caveats to this.
For example, some functions actually do
need to mutate their own data. The example that we run into is
cl-generic. It uses a method cache. So it has to be able to
update that cache. In this case, we just made a special
case for this particular situation, but we don't know what
more of these we're gonna run into the future where this is
needed behavior to be able to mutate a function.
Okay, so functions are pretty easy.
They just can be shared between
threads, but data can't be immutable, at least not into the
model that Emacs currently has. We have two different
ways to handle this. One is we require whenever you're
calling some other code in a different thread, you have to
send all the variables that it's going to need over to that
thread. This is how you traditionally do inside actors.
Any data that needs to go to a different actor needs to be sent
over a channel. It's relatively easy implementation, but
this is difficult in the Emacs case because everything is
going to be accessing different variables. That means
when you call something, you have to know ahead of time, all
the different variables that are gonna be accessed inside
that other thread and put those in when you call it.
The other option we're using is we're copying values to the
other threads on demand. If you're running a thread, it
tries to look up a variable. It doesn't have any value for
that variable. It will go back and ask the main thread and it
will copy that value into that thread and it can continue
execution. This is nice because you can just launch some
code and it'll take care of handling all the data transfer
for you.
But we don't want to be copying around is buffers,
because they can be really large. In this case, we have a
mutex. Each thread could only have one current buffer that
it has an exclusive lock to. This comes with some
trade-offs, big one being that if the user tries to access
some buffer, they want to type something, and a background
thread is holding onto that buffer, what do we do in that
situation? And we still need to hold an exclusive lock, even
if we're only going to read a buffer. If you have multiple
readers, they each still need to take turns because we can't
determine if at some point a thread is going to try and mutate
the buffer. It has to be an exclusive lock. The other issue
is buffer-locals. This is less of a implementation issue
as much as it is a technical issue. Because you think about
when we switch to a buffer, it has some buffer-local data and
we have some thread-local data. As we go through, we're
mutating everything. Those can get intertwined and
pointing to each other. Then we switch away from that
buffer. We need some quick way to be able to separate those
out. The buffer-locals can go with the buffer-locals and
the thread data can stay with thread data and make copies of
anything that was pointing to the other side. But we don't
have a good method to determine how to separate those two,
like what data belongs to this and what data belongs to this,
so that we can do that quickly. We haven't found a good
solution to that yet, but it's something we're still
working on.
The question is, would this actually be
useful for doing real work inside Emacs? I would say,
yes, there's a lot of things you can do with this. You could
handle process output in the background. You can do syntax
highlighting. You can do buffer search in parallel. You can
do LSP. You can do fetching your mail in the background. You
can have a window manager that doesn't block your window
manager when Emacs is blocked. You could do
something like a file system watcher that keeps up on files
without blocking Emacs. This wouldn't be so great for
building concurrent data structures or operating on
shared data or building your own abstractions, because of the
trade-offs that we've made here. Okay. That's talking
about multi-threading.
The other thing we're going to talk
about is precise garbage collection. In Rune, we have a
safe, precise garbage collection because of the Rust type
system. Let's look at what the problem is with garbage
collection in the first place. Really, the tricky part
about garbage collection is rooting. How do we find out what
the roots are? These are all the values that are on the
stack or inside the registers. In this example here, we
allocate an object. We call garbage_collect, that object's
collected, and then we try and return it.
It's no longer valid.
Let's look at how Emacs used to deal with this
problem way back in the day. There was a system called gcpro
or GC Protect, which is basically designed that every time a
value needed to survive past a garbage collection point,
you had to try and protect it. In order to do this, you had
to declare a struct, you had to put a macro around it to root
the object, and then you had to unroot it when you were done--
past the garbage collection. Now the value is safe. You
can see down here, I pulled these eight rules out from a
really old version of the Emacs manual about all the things
you had to keep track of when you were trying to use this
system. All right, so there was a special handling for
nested GC protects. You had to make sure the memory was
initialized. You had to make sure that traps couldn't occur
between allocating and when GC protect would happen. It
can be tricky because you don't always know when a function
that's getting called could potentially call garbage
collection. So if you got something wrong, you also
might not catch it for a long time because garbage
collection may only get called one out of 99 times. The other
99 times is just fine. That one time it happens and you
can't reproduce the issue. When you do get this wrong and
some, something doesn't get rooted and it gets
overwritten, it generally doesn't show up right where the
problem is. It gets showed up way later when you actually try
and access the value and the value is invalid. You've got
to track it back to where that thing did not get properly
rooted. It's a huge source of bugs and very hard to
maintain.
Emacs decided to go with a different path,
which we call conservative stack scanning. Basically,
the garbage collector just looks at the stack and all the
registers and any data inside there that looks like it could
be a pointer, it treats it as a pointer. This is nice because
you get really easy root tracking,
but it also comes with some trade-offs,
mostly that your objects are no longer movable.
Why would we want movable objects in Emacs?
There's a couple of different reasons. One is compaction.
You can take all your heap, you can pack that on down because
you can coalesce all your objects together. Another is that
it's easy to implement generational garbage collection.
You can just copy everything out of your minor heap into your
older heap. Really, Emacs is kind of uniquely ideal for
generational collection, because the typical way we
interact with Emacs is as a series of commands. You execute
some command, you'd execute the next command, you execute
a command. It could be happening every key press, it could be
happening with M-x. However long that command is, that is
the ideal length for the minor collection generation, the
first generation. Because once you're done with that
generation, anything that's still existing is going to be
around for a very long time. So that works out really well
for Emacs. We want to make this a generational collector.
The other thing is with object layout. We use a lot of lists
inside Emacs Lisp. Every time you go to the cdr, you've
got to be chasing a pointer around the heap and following
that. That can potentially result in cache misses and
all sorts of other things like that. So it can take a long
time. It can be quite slow. But if you have the ability to move
objects, you can just relocate an entire list and lay it out
in an array right next to each other inside memory.
So iterating over it is just as fast as iterating over an array.
But you can only do that if you have movable objects.
I'll point out here too, that with conservative stack scanning,
it's not that all objects are immovable. It's only ones that
are pointed to from the stack or from the registers that have
to become immovable.
Let's look at how Rust makes precise
garbage collection easy. Here I have some Rust code to
show kind of how the lifetime system works and what we call
XOR mutability, where we can only have one mutable
reference or multiple immutable references to the same
thing. Here we declare a vector, we take a reference to the
first element of the vector, and then we mutate the vector.
Now this could potentially resize the vector and move it to a
different location in memory, so that reference is no
longer valid. The nice thing is, Rust catches this for
us. It says, hey, this is no longer valid. This reference
can't survive past when you mutated it. Okay? That's
exactly what we want for a garbage collector. You can see
here, we take this in a garbage collection context, we
create a new context object, we add an object, we call
garbage_collect, then we try and access that object. It's no
longer accessible, and Rust will prevent us from trying to
access that variable. So, how do we solve this? We have a
root macro. We declared this root macro, it lets us take the
object and let it live past garbage collection, and
everything works out. The nice thing is, this root macro
will get dropped when it's out of scope, so we don't have to
worry about the un-gc-protect step of this. Statically,
Rust will verify and tell us any object that needs to be
rooted. If we try and access it, it'll tell us it's invalid.
We have this root macro and then we can access it. So in
that way, we have safe, precise garbage collection without
any chance of introducing undefined behavior, which is
really, really powerful. It's really easy because the
type system will catch it all for us.
There's some other Rust niceties I want to kind of
talk through that are useful, but
are not, you know, star features. One is proc macros. You
can see up on the top, you can see how you declare a function
inside the C core. All right. You have to use the macro. You
have to put the list type, the function type,
the struct type, the different types of arguments
or different number of arguments, the doc string,
and then you can put your argument listing down inside there.
On the Rust side, we just write this like we would
any other Rust function. And then we put
the defun proc macro on there
and it takes care of everything for us behind the scenes.
A couple of cool additional things we can do with this
is that we don't have to make everything just an object.
We can actually make things
more specific types. Here we have symbols. As well as
you can see subfeature, it's an optional parameter, and we
just make it an option inside Rust and it automatically make
it an optional inside Elisp.
This makes them really easy to write.
I can't take credit for this is because this is
something that I saw inside Remacs and I stole from them, but
it makes the functions really easy to call from each other
and really easy to write as well.
Another thing that's really nice is sum types.
In the C core, if I wanted to get a
string out of an object, I would first need to check that it's
a string and then dereference it as a string. But if it's not a
string, I may introduce undefined behavior. So in
complicated code, I have to make sure that I have always
checked what type it is before I try and dereference that
type. We don't have to worry about any of that inside Rust
because we can untag a value and we can use their some types,
basically create an enum and we can match on what the
different values can be. Then we only get out the types
that are viable or are actually there. So we never
accidentally get something out of an object that we didn't
mean to, or dereference it as something that doesn't
really exist. We can just match on it and we can get out the
values that we need, which is really, really powerful.
So there's some other Rust niceties as well working with here.
One is the regex engine inside Rust is really fast, high
performance. We are using that for the Elixir regex
engine to give it high performance and worst-case
guarantees.
The other is that Rust has a lot of really good
parsers for things like JSON that are no copy parsers that
are high performance. We can use those inside Rune as
well.
There's a handful of other changes we're working on
that are not Rust-specific, but we'd like to see. The first is
being GUI first, terminal second. This means two things.
First is that we have all of our key bindings. Right now
inside Emacs, C-i and TAB are bound to the same key
binding by default, because that's how it works inside the
terminal. In the GUI, you shouldn't have that limitation.
The second is that the GUI should not block when Lisp is
blocked. It should be independent of that. Your GUI can
still continue to operate when Lisp is running.
The other is the ability to have an off-screen cursor
so that you can be typing on something,
you can scroll up and down and the point
doesn't have to follow you where you lose your place where
you were before. You don't have to intentionally set a mark.
You can just scroll and then start typing and it'll go back up
to where it was before, like it works in most applications.
And this can be optional.
The other is image flow. We want it
so that you can easily flow images and you can have large
images and scroll past them without jumping and you can flow
text around images.
How are we testing this project? Because there's a lot of
things that you could get wrong here. One thing we're doing
is we're using ERT. Emacs ships with over 7,000 built-in
tests--Elisp tests. We are using this test suite to test
our project as well. We can kind of use this as a dashboard
of saying how close are we to getting to parity with GNU
Emacs. The other thing that we have is a tool called elprop,
which is an external utility that basically tests for
correctness. Because really, the correctness of Rune is
whatever Emacs does, because there's no official spec on
how things should behave. To do this, we can go look at
the Rust function signature. We know what the arguments
are, we know how many they are, and we know what types they
should be. Given that information, we can generate a
whole bunch of random functions feeding those types in. And
then we send a copy over to Emacs, we send a copy over to Rune.
They each evaluate it and they return the result and we make
sure the results are the same. Then you do that for
thousands of different implementations of the function.
And it helps us find corner cases really easy without having
to handwrite a whole bunch of different cases to test things
and say, where are these two functions different?
So the current status: we already have a multi-threaded Elixir
interpreter and bytecode engine inside there. There's no
actual text editor in there yet, but the primitives are
there. Like you can insert text, move point around,
delete text, do different things like that. But we don't
have a GUI hooked up to different key bindings to actually
type on. There's just a REPL to operate in. We have about
250 of the 1500 built-in functions already implemented
inside there. There's a lot of low-hanging fruit inside this
area to still be implemented.
The next directions we're
working on is we're optimizing the GC. We want to make it
generational. Like I said, right now, it's just a simple
semi-spaced copying GC. We want to add a proper GUI. We need
to implement text properties, overlays, process and job
control, all that goodness right there.
How can you get involved? This is hosted on GitHub.
You can come on over.
If you have any ideas about how to implement something or
something you'd like to see done, go ahead and just open an
issue so we can have a discussion about it. We've had lots of
interesting discussions with different people coming in
to the GitHub repo. If you're interested in contributing,
the easiest way is probably to run elprop, pick some
function, run elprop on it. I promise it won't take long to
find some issues, some discrepancy between Emacs and Rune,
and that lets you dive into the Rust code and figure out, and
the C code, and figure out what the difference is between the
two. or come along and help implement your favorite
functionality. This has been a really interesting project
so far, and we've had a handful of different contributors on
it who just kind of want to learn Rust or get more into
systems-level programming. Thank you.