Eliza Weisman
Appearances
Oxide and Friends
Crates We Love
Brian, it is with a heavy heart that I must inform you that if you have, any time in the last six months or so, made a typo in an idle RON file and gotten an error that has some RON source in it, that's thanks to Miette.
Oxide and Friends
Crates We Love
This is amazing that Eliza, you also read Choose Your Own Adventure. I am just old enough to remember save scumming in a book. Yeah. Okay.
Oxide and Friends
Crates We Love
On the subject of finding crates, I was thinking a bit this afternoon about, you know, I have personally had a lot of experiences with, there are many categories of crate where... There are a bunch of implementations of basically the same thing with basically the same API and wildly different performance characteristics. My classic example is like async channels like MPSCs.
Oxide and Friends
Crates We Love
There's the Tokyo one, there's the Futures one, there are a bunch of crates that are just channels. And having done a bunch of benchmarking and digging into their implementations a few years back when I was writing my own channel, they all have very different performance characteristics and they're not really, there isn't a good one.
Oxide and Friends
Crates We Love
You know, you don't just pick the good one, you pick the right one for the job. And it depends pretty substantially on the usage pattern. And I think kind of the big lesson that I learned from that is that as a crate author,
Oxide and Friends
Crates We Love
I found it very useful to sort of up front, like at the very top of the readme, front and center when you've gone and done something that there are, you know, four different versions of on crates.io, like a channel. Why should you use this? Why should you not use it? How does it compare with other crates that maybe implement something similar? And I found it really useful to do that.
Oxide and Friends
Crates We Love
And I hope that when people go searching for these libraries and encounter something that I've written, they read this section and know when, you know, maybe this is actually not the appropriate implementation for the specific problem they're trying to solve or when it is. And I want to kind of encourage others to think about doing this because I think it's a really valuable exercise.
Oxide and Friends
Crates We Love
I can maybe scare up some of the examples of times I've written that.
Oxide and Friends
Crates We Love
Well, so my Bitfield crate, actually, I know I promised you some Bitfield crate opinions. My Bitfield crate has such a section in its readme, and it basically leads with there's no reason you should choose this. I wrote it for fun because I wanted to write it for fun. And the one interesting thing about it relative to other Bitfield crates is that mine is a declarative macro rather than...
Oxide and Friends
Crates We Love
I'm a big fan of the bit field crate called modular bit field, which allows you to sort of have a struct and annotate various fields in the struct with attributes and you generate this very nice, you know, packed within one word bit field thing. And I think that it presents kind of the nicest interface for doing this.
Oxide and Friends
Crates We Love
And mine is just kind of worse in every possible way, except that it doesn't use a procedural macro, because I thought that it would be fun to see if I could get it to work without using a procedural macro.
Oxide and Friends
Crates We Love
Yeah, I think it's really nice. It's by far the nicest interface to this sort of thing that I've seen. And I just pasted in chat the comparison with other crates section for my sort of Cgeneris bit field crate that says basically don't use this, use modular bit. But I've used my own thing in all of my projects because I wanted to make my own things. I thought it would be fun.
Oxide and Friends
Crates We Love
It's also, it's very nice as a maintainer to not have to like respond to the issues of people who are just constantly showing up to say, can you make this other crate? Well, no, I can't because I didn't set out to do that. And, you know, not to sound too much like a member of a cult, but Brian, this is why it's important to have upfront values for one's technical projects. I, yes.
Oxide and Friends
Crates We Love
Yeah. Yeah. And the big lesson from the channel thing that I learned from doing a bunch of benchmarking of channels is that there isn't really just a box that says performance on it that you can click, right? Because, for instance, in the readme to my channel crate, which I posted in Discord chat, I discuss, you know, there's this question of like,
Oxide and Friends
Crates We Love
An MPSC channel, an async channel, has to store the messages in the queue someplace.
Oxide and Friends
Crates We Love
And there are channel implementations that will allocate and deallocate chunks of buffer as you are sending and receiving messages so that the memory usage of the channel is proportional only to the number of messages currently in the queue versus channel crates that will allocate the whole buffer once when you make the channel. Yeah.
Oxide and Friends
Crates We Love
There isn't necessarily one of those is not good and the other is bad. It's a question of is this channel like something that is structurally integral to the program and it lives for the entire time that the program exists and all of the messages go in that channel. And is the bound on that channel like extremely large and the message very big?
Oxide and Friends
Crates We Love
And that means that if you keep it fully allocated all the time, that's like a very large amount of memory. Or is it something where you are making these channels and you're having a bound of like eight or 10 messages and now there's just extra overhead of doing this? Like I'm going to allocate another chunk of buffer as I need it.
Oxide and Friends
Crates We Love
And it really depends pretty substantially on the usage patterns, and there is no sort of the right move. So it's useful to document those sort of performance trade-offs and the ways in which this might be suitable for one type of use but not for another.
Oxide and Friends
Crates We Love
I want to point out that Lexopt has in its readme a very nice why and why not section in which it says basically everything the range has told us.
Oxide and Friends
Crates We Love
Well, I do really feel like I will be sad if I don't get the opportunity to plug what I feel is the crate that has had the biggest and most profound impact on my life personally. And that crate is Loom, which is pretty different from everything we've discussed so far. This is a crate that Karl Lerka wrote while he was working on the Tokyo scheduler.
Oxide and Friends
Crates We Love
And what Loom is, is a model checker for concurrent Rust programs. And the way that it works is it gives you sort of a set of all of the primitives in standard thread, standard sync atomics, and standard sync mutex, and so on, and a sort of simulated unsafe cell. And the way these things work is that they have basically the same API as the standard library functions,
Oxide and Friends
Crates We Love
But rather than actually being like you're spawning a real thread or you're just creating a real single word that you're doing atomic compare and swap operations on, instead what they do is they deterministically simulate all of the potential interleavings of concurrent operations that are permitted by Rust's memory model or the C++ memory model which Rust inherits.
Oxide and Friends
Crates We Love
And this is sort of based on a paper, I believe, that describes a sort of model checker like this for C++. And so what you can do is you can have, like, using some conditional compilation, you can say, normally I want to actually spawn threads or use real atomics or what have you, but when I'm running my tests...
Oxide and Friends
Crates We Love
I want to be able to write these deterministic models that will exhaustively explore all of the permitted interleaving, like the Rust compiler is allowed to emit or allowed to allow the operative scheduler to emit.
Oxide and Friends
Crates We Love
then if you use the loom unsafe cell, it will check like, okay, if I have a immutable access from one of the simulated threads, and then this thread yields, and now I'm executing some other thread, and now there's a mutable access to that same unsafe cell, it will then generate a reasonably nice panic,
Oxide and Friends
Crates We Love
And when you do this, you sort of have to sit and run this task for tens of thousands of iterations because this is sort of a combinatorial explosion of potential paths that the model permits through this test that you've written. But the reward for that is that if you've written complex concurrent code like a log-free data structure, you get to learn all of the ways in which you've done it wrong.
Oxide and Friends
Crates We Love
Which is, I would say, deeply and profoundly humbling. You learn the ways that, like, perhaps you were executing this code in real life on an x86 machine, and you've never seen any of these possible data races because you're running on an x86 machine. but someday your code might be cross-compiled for ARM, and it just so happens that you've used sufficiently relaxed atomic orderings that...
Oxide and Friends
Crates We Love
when compiling for arm you will actually see like loads and stores reordered in ways that will result in this data race that you've never seen in real life and so you've used loom it sounds like to actually debug weight and lock free data structures i have learned used it not to debug weight and lock free data structures so much as to learn that my weight and lock free data structures are wrong
Oxide and Friends
Crates We Love
it's like it will log um you know i'm doing this operation at this time and it will try to tell you it it's logging is like somewhat useful it will try to use track collar a lot so that it like captures like where was this mutex constructed in the program at what line uh where was this atomic constructed at what line was it accessed at what line was this um this unsafe cell accessed
Oxide and Friends
Crates We Love
And which thread did that? Or which simulated thread in this test that you've written? and it will try to sort of give you some helpful information about that.
Oxide and Friends
Crates We Love
But honestly, it also is just sort of very useful as a trial and error mechanism that sometimes you just sort of end up going, oh, I think I understand what the problem is, and I'm going to kind of permute the program a little bit, and I'm going to run it through Loom again, and maybe now this model will actually, you know, after running through tens of thousands of iterations, I've actually not found anything that causes a data race.
Oxide and Friends
Crates We Love
Or a deadlock, it also does deadlock detection, and it has a leak detection facility similarly. If you also use looms, wrappers around box or other ways of allocating and deallocating, it will tell you it leaked a box or an arc. And again, the thing about this is that it sounds at the surface level similar to tools like
Oxide and Friends
Crates We Love
t-san or asan or valgrind but it's actually quite different because it's a model checker rather than a sanitizer that you run your program under and then get back oh while it was executing it did a bad thing but you know it's possible that you'll just never see the bad thing happen during that execution whereas with this sort of deterministic model checking
Oxide and Friends
Crates We Love
Of course, there might be bugs in the model checker, or you might have set bounds on how much it can explore the state space. And you might have missed a bug. But if you set aside those things, you know that you've actually deterministically explored everything that the compiler is allowed to generate. So anything that is outside of that is not permitted by the model.
Oxide and Friends
Crates We Love
Describe a little bit how this comes back to you. Yeah, this stuff is incredibly hard to reason about. And every time you think that you're actually good at it, that's very dangerous, right? Because this stuff is incredibly difficult for us to deterministically explore all of the interleaves permitted by the model in our head.
Oxide and Friends
Crates We Love
And so it's just sort of like it has really kneecapped me every time I've used it. And it just sort of taught me about my own insignificance and how small my mind is relative to what is permitted by this extremely complex memory model.
Oxide and Friends
Crates We Love
And really, the way that it has impacted me is that I will never write lock-free, wait-free, or even concurrent code that uses locks that is of sufficient complexity without using Loom. And I try very hard to avoid... anyone else's code that has not either been tested using Loom or tested using another similar model checking tool. Because I don't think that human beings unassisted do that.
Oxide and Friends
Crates We Love
I think that it's sort of like C versus REST, right? It's sort of like there are plenty of C programs that have run in production and are, you know, thus far we have not seen the lurking memory errors in them. That's great. But This is a way of exhaustively proving the correctness of our programs.
Oxide and Friends
Crates We Love
And it has taught me that I don't like this is not me saying, like, y'all don't know what you're doing, because I don't trust myself to do this unassisted either. I think that it is just fundamentally like you will regret it. not using these tools, and you will regret using any library that implements a complex concurrent data structure that is not tested using a tool like this.
Oxide and Friends
Crates We Love
I'm not saying, it certainly does not have to be Zoom in particular, but something of this nature is just kind of a necessary tool to write this kind of software. I certainly was there for the gradual sort of push to cover all of Tokyo's internals with Loom. Carl developed this while he was sort of rewriting the scheduler.
Oxide and Friends
Crates We Love
And over time, we sort of pushed to get it into more and more of the various synchronization primitives and other Tokyo internals. And we found just a kind of devastating amount of bugs by requiring that any new or changed code have tests. And many of those bugs had not been discovered directly.
Oxide and Friends
Crates We Love
But they probably sort of fixed a lot of the weird, inexplainable behaviors that there were GitHub issues that nobody really knew what the answer to was.
Oxide and Friends
Crates We Love
Yeah. At... It came out of, I believe, between... Some of you might be old enough to remember Tokyo 1.0, or Tokyo 0.1, where Tokyo was split into Tokyo Core and Tokyo IO and various other crates. And in the sort of...
Oxide and Friends
Crates We Love
process of writing Tokyo 0.2 Carl rewrote the entire multi-threaded runtime more or less on his own and in the process of doing that he realized that this was just like extremely difficult and somewhere along the line found the paper I believe the original the paper is called CDS Checker And it describes a very similar thing in C++.
Oxide and Friends
Crates We Love
And Carl basically said to himself, I can't keep continuing the scheduler rewrite without this. I have to stop what I'm doing and go and implement it. And I'm sure Carl can recount this story much better than I can. He sort of stopped everything he was doing and went and materialized the thing.
Oxide and Friends
Crates We Love
Since then, it has been kind of improved substantially, in particular with regards to actually being able to tell you what went wrong in your program instead of just sort of, well, you did a data race. Good luck. And also its performance has been kind of optimized substantially because we might not generally think like, oh, it's a testing tool. Performance is like very, very important.
Oxide and Friends
Crates We Love
But it's a testing tool that will execute a test potentially hundreds of thousands of times. Sometimes you're really sitting there for like an hour waiting for the thing to run one test. So a great deal of perf work was sort of done more recently to try and make it not just mind-numbingly slow. But yeah, that's really, that's its heritage.
Oxide and Friends
Crates We Love
At a meta level, one last note on just how long it takes for this thing to run. At a meta level, I would add that the length of time that the loom model of a concurrent data structure takes to run is sort of a good warning metric too. If it takes an hour to test this thing, maybe this thing is actually too complicated and you could make it simpler.
Oxide and Friends
Crates We Love
Postcard, if memory serves, is very similar to Hubris's sort of indigenous serialization format, but with a couple of key differences. I think that Cliff skipped the varint.
Oxide and Friends
Crates We Love
I had on my list another one of postcards at James Munn's thing. And I had one of his other projects on my list of crates, which is BBQ, which is a queue like the data structure. And BBQ is a multi-consumer, multi-producer byte queue that... allocates exclusively in contiguous regions in memory.
Oxide and Friends
Crates We Love
And the idea is that this is a queue that you can grab sort of a chunk of bytes of a given size off the front of, and then you can do a DMA directly into that lease and release it to the queue, and then you can wake up the other end. And he's got a bunch of
Oxide and Friends
Crates We Love
The interface for it is kind of hairy, but it allows you to say, I want this static region that I've declared as the backing storage for the queue, or I want to be able to dynamically allocate a byte buffer that is the backing storage for the queue so that you can use it really in both embedded projects where you don't have any capacity to do dynamic allocation. You can make them on the stack.
Oxide and Friends
Crates We Love
You can make them on the heap. and they're really nice, and they're DMA safe, so you can just have your NIC or whatever write directly into the region and queue that will then be consumed by somebody else. It's quite nice.
Oxide and Friends
Crates We Love
I do have one last draw. I have a hard stop, 630, so I just really wanted to get this one in. This is a crate that I really like because of its sort of implementation and its sort of cleverness and beauty. And it is also sort of an example of a thing where there
Oxide and Friends
Crates We Love
right design for this category of of data structure and instead you like really have to pick the correct one for your use case which this may or may not be uh which is concurrent hash maps And my personal favorite concurrent hash map is John Gangset's Evie Maps, which is an eventually consistent hash map. And the way it works is it's just sort of got two hash maps. And one of them you read from.
Oxide and Friends
Crates We Love
And that allows you to read from it without acquiring any kind of lock. And then there's one that you write to. And periodically, you swap them. And this is quite nice, because there's actually nothing scary going on in having two maps and a read-write lock. And if you choose to have them be only eventually consistent, you don't refresh the read replica on every write.
Oxide and Friends
Crates We Love
And if you do, you still have something nicer than just naively sticking one hash map inside of a read-write lock, because sometimes doing the write operation to The map will do a bunch more. You might have to allocate something inside the map. You might have to fill up a bucket and have to move things around. And all of that happens in a write lock that's only contended by writers, right?
Oxide and Friends
Crates We Love
And then the lock that also contends with reads just swaps two pointers, right? So the amount of time that a reader... with that lock is substantially reduced relative to just putting one hash map inside of a . But you're still contending with the reader because you have said, I want to do this refresh operation on every write.
Oxide and Friends
Crates We Love
But you also can tune the consistency of the map and say, I actually don't want to do that. I want to do it periodically. And now you have a situation where you've reduced the contention readers substantially by every 5 or 10 or 25 writes you refresh the replica that's read from.
Oxide and Friends
Crates We Love
And this is just kind of neat, because I find it very beautiful in its sort of conceptual elegance, and depending on the particular need you have for a concurrent HashMap, it could be the right one, or it could be wildly incorrect for your use case. I just think it's fun.
Oxide and Friends
Crates We Love
Yeah, the thing that I neglected to mention is I believe there's a way to explicitly say, right now I want to synchronize the two replicas, as well as you can set an interval or a number of writes after which you will refresh. I haven't used this in quite some time. I don't remember the API for it. But the idea of it has stuck with me as long as I've known about it.
Oxide and Friends
Crates We Love
That's most of my list. The rest was... Oh, I wanted to mention the Bytes Crate, which is a terrible name for a wonderful library that many of you probably already encountered, or perhaps unknowingly, because if you use Hyper, you actually are secretly using this. And Bytes is something from the Tokyo Project, and what it is... Oh, Sean's here in the chat. Sean can talk lots about Bytes.
Oxide and Friends
Crates We Love
Bytes is essentially a reference-counted byte buffer. So it's like an ARC VEC U8, except that you can take slices of it, and the slices are also owned objects that participate in the reference count of the whole buffer. So this is very nice if you want to read data from the network and then parse it into something and you want to take slices out of it.
Oxide and Friends
Crates We Love
for, like, here's the HTTP request's path and its headers can all be sub-slices of one buffer that all of the bytes into. And I think bytes is just sort of a really lovely library. Really nicely. And also is the foundational building block under creative that Rain and I collaborated in past, which is buff list, which is just some code that...
Oxide and Friends
Crates We Love
was that I think Rain asked me how to do something, and I referenced some code that had been written probably by Sean MacArthur within an application that Rain just went and turned into a library that he used at Oxide. And I'm going to let Rain talk about that.
Oxide and Friends
Crates We Love
Brian, you might be pleased to know that I got out in front of this a few months ago and ripped out a bunch of string-based code generation from Idle, which may have been Cliff's doing rather than yours. But now that uses quote and pretty please.