Hi folks, welcome back to another like live coding stream. We haven't done one of these in a little while. And part of that is because it's really hard to find good topics for these like long form live coding streams because it has to be something that like I think is interesting and I care about because otherwise I'm not gonna put like some of these end up being like three videos of six hours each. And it's just like a lot of time to sort of stay focused on. But recently someone sent me this paper called the practical weight-free simulation of lock-free data structures. And we'll go through what that actually means. And it sort of piqued my interest. I sort of got nerd sniped into this is really interesting. I wanna read the paper and while reading it, I was like, this could be really interesting to try to encode in Rust. And so that's what we're gonna do today is sort of walk through this paper, try to understand what it is that it's proposing and then try to like implement some at least skeleton of it in Rust. I don't know exactly how far we'll get. And there are some holes that I can sort of see already will be present in the code that we write. But I think it's gonna be a really interesting sort of adventure in translating academic work. And in particular, like sort of algorithms and data structure work that wasn't written for us in the first place. And in many cases, we don't even have the code for and turn that into like actual real Rust code. I wanna prefix this with the fact that this is academic research. And one of the artifacts of that is that there are open questions. Like there are things here that there just won't necessarily be an obvious solution for. There might be places where we get stuck. There might be places where we sort of write the initial implementation. It turns out to be wrong or subtly incorrect or it doesn't scale the way that we want it to. And that's okay. We're sort of doing this a bit as an exercise in trying to understand this academic work as well. And in sort of understanding how to model the sort of abstraction that they're presenting in the paper in the context of the Rust type system. And just sort of similar to how most of the other live coding streams work. My guess is that this stream will probably be around four to five hours. And I mean, if you're watching this after the fact, you can see how long it is at the bottom. But for those who are live in chat. And I'm guessing we're gonna do a couple of videos on this because I could totally imagine that once we have the sort of architecture up and running, we might then go and implement multiple different data structures on top of it. We might do some like benchmarking and debugging and whatnot. I also already have another stream that I think we're actually gonna end up needing fairly soon for implementing this paper. And that's implementing something called hazard pointers which I wanna see if I can actually dig up this paper. I don't have it open here. But Facebook has this open source library called Folly. It's a C++ library where they've implemented a really neat variation of this concept of hazard pointers. And I wanna try to port that to Rust. And that might be the next stream. So it might be that what we end up doing is this stream is gonna be on sort of getting the initial model setup for this kind of algorithmic abstraction that the paper lays out. The next stream is gonna be implementing hazard pointers which is sort of a completely separate topic. And then the third stream is gonna be using hazard pointers in the context of this paper because I think the two are gonna tie together. But we won't actually talk too much about hazard pointers today. I just sort of want to give that as a sort of context for something that is gonna come up later in the stream and make up up in the future too. All right, so back to the paper. I'm gonna put, there's a link in chat now. I'll also put it in the video description. This is also the same one that I tweeted out. There's a shorter version of the paper as well for those who don't wanna look through everything around it. But I'll be working from this one that's sort of labeled the full version. And this is sort of the extended technical version that has a bit more detail, a bit more performance analysis and appendix that includes some code and a bit of that. Before I try to explain what this paper actually is and like what the words mean. Is there anything that you have that are sort of meta questions about what we're about to embark on? Like I know that many of the people watching are probably coming from the sort of crust of Rust Streams and this sort of live coding stuff might be a little weird or do you just have questions about how going from an academic work into code is gonna work? Like these sort of meta questions to handle those at the top. Weight-free, yeah, where I'm gonna talk about what weight-free means, I'm gonna talk about what lock-free means and I'm gonna talk about simulation means and I'm gonna talk about what practical means. So the title I promise you we're gonna go through in a lot of detail. Where's Chai? Chai is downstairs staring out the window looking for suspicious things on the street. Let's see. Well, you give a tutorial on how to read academic papers along the way. That's a good question. The way that we're gonna approach this paper is a little different than how I normally read academic papers because here our goal is to implement it rather than, I mean, we are trying to understand what they're doing, but we're not really trying to understand the work in the sense of like why its performance characteristics are what it are, which is what I often look for when I read a paper to sort of understand the approach and be like evaluating the paper more formally, whereas here we're taking a much more practical approach of like we're sort of assuming that this paper is a good idea and now we're gonna go and implement it. So it's a little bit of a different type of reading, but I'll give some pointers about how I generally go through these kinds of papers. Is there any specific background knowledge we should need to be able to understand the stream? So in general with these live coding streams, I assume that people are familiar with Rust beyond just sort of having read the book. I expect that you sort of know how the Rust language work. You have written some like Rust code that wasn't just like a little world example, but I don't have any expectations that you necessarily know how like concurrency and atomics work in great detail. Much of that will go through as I sort of go through the paper and also as we start writing the code. I won't spend as much time explaining exactly how things work as I do in Crust of Rust. Instead what I'll do is sort of when we get to a topic that there's already a video on, I'll probably say, if you're feeling stuck at this point, go watch this video and then come back later because I'll upload the video at the end. The llama supervising, that's true. So we just blindly believe it. Sort of for the purposes of this stream, I'm not really looking at like, is this a good idea? Like should all your production systems be using this approach? And there are a couple of reasons for that. One is this is very much academic work. It's not clear that it's something that you would use in production in its current state. It might be at some point, but we'll talk a little bit about what the sort of advantages and drawbacks of this kind of algorithm is. We don't necessarily care about the performance results for this particular paper or like the higher level argument of like, should you prefer wait-free or lock-free or lock-based or obstruction-free data structures and algorithms? We won't really get into that detail here because really what this stream is about is about teaching you how to, or one way to encode academic papers into Rust code. More so than evaluating whether this particular algorithm is one that you should care about and use. It will be on the test, yep. I will push this to a GitHub repo, both the code that we end up writing and some of the source code that I managed to get from the authors of this paper that we'll be using for reference. Great, all right. I think that's enough prefixing. So let's first start out with just the title of the paper. The title very often gives you a good summary of the paper. And part of the reason for this is because, well, or to rephrase slightly, the title has to be short. Doesn't have to, but in practice, paper titles are short. And this means that as authors of papers, you spend a lot of time thinking about exactly the words to use in the title of your paper. And so in general, any given word is just like not unnecessary. And so what we'll find out is to sort of start out the stream by understanding what does this title mean? Why were all these words chosen? If you've read the paper or read some part of it, as a result of me sort of tweeting about it early, you might have sort of read the abstract and some of the introduction of the paper that goes into a little bit of detail. But at a high level, data structures that are concurrent, that is data structures that allow concurrent access to the data structure from multiple different threads, can generally have one of many different properties. So the weakest one of these is something called lock-based concurrent data structures. So these are the ones that you're probably most familiar with, where you have something like a standard library hash map and you just like put it behind a lock. And so there is only one thread accessing the data structures at any given point in time. So you can use any data structure you really want and the mutex, the lock is what ensures that you don't have problems where two threads both try to say, remove a key at the same time. There's a variation on lock-based data structures that use what's often referred to as fine-grained locking where there's not necessarily a lock over the entire data structure, but the sort of sub parts of the data structure are protected by locks. An example of this would be, you could have a hash map where every bucket of the hash map is like a linked list, but the buckets are themselves protected by a lock. So if two threads try to access different keys, they don't take the same lock, they take different locks because they're in different buckets and therefore they don't contend with one another and they can both proceed in parallel. So it's sort of the advantage of fine-grained locking. But ultimately, these have a couple of challenges. There are a couple of reasons why you want to avoid lock-based data structures, even the ones that are fine-grained. One of them is that they are sort of by nature blocking. That is, if one thread is trying to do something and another thread is trying to touch the same resource, whether that is the whole data structure or say a hash map bucket, no other thread can make progress on that bucket at that time. And this has some implications. So first and foremost, this means that if some thread, just like panics, like it crashes and doesn't release the lock, or it like hangs, like it deadlocks while still holding the lock, or it goes into some kind of infinite loop. It issues a syscall where it waits for like a TCP packet that might not arrive for a long time. In all of these cases, the thread that has the resource locked is blocking all other threads from making progress. There's a more extreme version of this if you're doing a little bit lower level programming where you might be dealing with stuff like CPU exceptions and interrupts or slightly higher level like signal handling, where these primitives can interrupt the execution of a given thread, right? So imagine you have a single threaded program that's like running through its code and at some point it takes a lock and then it's in the critical section of using that lock and then an interrupt comes in or a signal comes in, that causes that thread to jump to executing some entirely other code without sort of finishing up the work it was doing here. So one thread stopped in the middle of a critical section and jumped to some other code. If that other code tries to access the same resource, you now have a deadlock within one thread because it is holding the resource, but it's also trying to acquire the resource. And so it can't release the resource because it blocked trying to acquire the resource. And so this is another example of where these like lock-based data structures have some issues. That's not to say they're never useful. In fact, they're quite useful in many cases. Very often you like know that you don't have a signal handler. You know that you don't have interrupts or exceptions that come in that you have to deal with. You know that none of your threads issue blocking system calls while they're holding a lock. And so you can sort of work your way to system settings where it's okay to be using something lock-based. And the advantage if you get into that space is that you can design algorithms that are simpler because locks in general allow you to write simpler code. And in some cases, more advanced data structures that have better properties. In general, when you try to design things without locks, it constricts the designs that you can use. And so you might end up with data structures that don't have as many optimizations in them because the optimizations are just too hard to make lock-free. Whereas in the lock-based approach you might be able to sort of have more optimized data structures. And so there's only a trade-off space there. So then we get to the distinction between things that are blocking, so this is lock-based programming, and data structures that are non-blocking. And non-blocking algorithms include things that are wait-free, things that are lock-free, and things that are obstruction-free. And these are all slightly different in terms of exactly what they guarantee. So the weakest one is something called obstruction-freedom. And this was actually announced fairly recently. So obstruction-freedom, I think this paper is from 2004, 2003. So obstruction-freedom just means that no thread can prevent other threads from making progress. So that is, if some thread gets stuck, it doesn't prevent other threads from making progress. That doesn't mean that other threads will make progress, and this is where the distinction is important. So obstruction-freedom sort of guarantees correctness but doesn't guarantee liveness, is one way to maybe think about it. Obstruction-freedom sort of dictates that something else has to make sure that the other threads make progress. So an example of this would be that in sort of obstruction-freedom, you could say that this data structure makes progress as long as every thread gets to execute some instructions. Like basically you have a fair scheduler is one way to think about it. That's an assumption that's not generally okay in something like lock-free or wait-free data structures. But in obstruction-free data structures, you sort of say that we don't guarantee progress, we just guaranteed that no thread can prevent progress. And then you make assumptions that enable progress to happen anyway. Lock-free is a slightly stronger guarantee that dictates that at any given point in time, one thread can make progress, or rather some thread can make progress. This could mean that you end up with starvation, that one thread is just doing work over and over and over, and it's making progress, like it's doing everything it wants, but all the other threads end up sort of, like you can think of it as, they end up trying an operation, realizing that this thread that's just like spinning, doing things has changed things in some way that causes them to retry, they retry, they do the same thing. And so ultimately only one thread ends up making progress. And then you have wait-free, which is the sort of extreme case of this. So in a wait-free data structure, you have to guarantee that every thread makes progress in a finite number of steps. So that is if you have lots of threads, then even if, well, you basically, you have to design the data structure in such a way that even if one thread like dies and goes away and never does anything again, it can't prevent other threads from making progress. So this is sort of the obstruction of freedom. You have to guarantee that at any point in time, some thread is making progress, but even more strongly, every thread has to be making progress sort of at all times. You can think of this as like, you can't say that, oh, this thread will get to make progress when it next gets scheduled, for example. That's not good enough for wait-freedom because that assumes a fair scheduler, which you might not have, like the operating system might not implement a fair scheduler and now suddenly your algorithm doesn't actually guarantee that everyone makes progress. And so generally what you see with wait-free data structures is that there's some notion of helping where if a thread sort of can't make progress, it stores the fact that it can't make progress and then the other threads are sort of required to come help it. And so that way, as long as any thread makes progress, all threads make progress eventually. And then this is obviously not the formal definition, but just to give you a sense of what these different categories are and what guarantees they provide.  Does this roughly make sense? Does the distinction between these make sense and to some extent does it make sense when you might want these different ones? I'll add to this that in general, the stronger the guarantees you want, the more complex the data structure is likely to be. So lock-based data structures can be very simple, very often that it's just a mutex, which is a fairly simple data structure in and of itself, and an existing data structure that is not concurrent, that you just like stick them together and then it works. As you go towards wait-freedom, you end up with stronger guarantees about progress, but you also end up with much more complicated data structures and algorithms and generally worse performance. And performance here is weird, right? So the performance is sort of single threaded performance is one way you can think about it. Like there's more stuff every thread needs to do for a given operation. So the operation is more costly, but also more threads can make progress. So you might scale better with say the number of cores. So that's often the trade-off you make. All right, let's do some questions on that because that was a lot of stuff. Are there domains where lock-free and wait-free is commonly used? So lock-free constructions you will usually see in cases where you really want scalability to many cores. An example of this could be like GPU programming, although I don't know that they use a lot of lock-free data structures there, but it might be a good case. The other one is when you're doing very large computations where say you want to make sure that your workload can scale nicely to say like 64 cores or 128 cores or like the thousand core processors that Intel or Wattnard are developing, right? Once you get to that point where you actually want a thousand cores to make progress at the same time, a lock could be really problematic because even if you have fine-grained locking, the chances the two threads are actually trying to access the same fine-grained lock is decently high. And so you end up with your concurrency being limited by basically the number of hot locks. That's the maximum parallelism or concurrency rather you can achieve as opposed to the number of cores. Whereas a lock-free implementation will generally give you the guarantee, this is not quite true, but will generally give you the guarantee that your performance scales with a number of cores, not just with a number of non-shared resources. Weight-free takes us a step further and says that even in the case where you have say uneven resource use, like one thread is spinning and other threads are trying to make progress every now and again, the spinning thread can't keep up the work that you need the other threads to achieve. This comes up particularly in things like real-time programming and in some cases embedded devices, but generally anytime you need to give a strong bounce on how long a given operation can take, you might start to tend towards weight-free things because with lock-free you can end up with starvation. And so you might end up with some thread seeing like a, I don't know, a hash map insert, take a very long time. You end up basically with very high tail latency because it might be stuck trying to make progress when some other thread just like keeps getting in front of it. And so that's sort of the scale. What is the difference between non-blocking and weight-free? So weight-free data structures are also non-blocking. Weight-free is strictly stronger of a guarantee than lock-free is. Traditionally, I think lock-free was called non-blocking and then now we're sort of favoring the term lock-free over non-blocking because non-blocking sort of covers everything from obstruction freedom and onwards. Like obstruction freedom is also non-blocking, but it's sort of only non-blocking. Let's see, how can you have a weight-free data structure in an OS environment where you can't guarantee your whole program is going to progress? Nevermind all the threads. So the basic idea with a weight-free data structure is that as long as some thread progresses that thread is going to be forced to help the other threads. And that's how you guarantee progress. So as long as something gets to execute, progress will be made on the sort of tasks of every thread. So even if a given thread doesn't execute, other threads are gonna execute on its behalf. That's sort of where you get this helping mechanic that's often needed for weight-free stuff. Left, right would be classified as lock-free. Yes, I think that's true. Well, it's lock-free for reads. In fact, it is, I think it's even weight-free for reads and it is, maybe lock-free for writes, it's unclear. Yeah, as long as no, a writer can be held up forever by a reader who doesn't release. So I don't think it's lock-free. I think it's actually, it's not non-blocking. I think it's like obstruction-free maybe, but even that's unclear. Like imagine in left-right, right? If a reader crashes while having the epic incremented once but not twice, the writer will never make progress. So left-right is blocking for writes, but it is, I think even weight-free for reads. Are atomics allowed in weight-free?  The question is more how you use them, right? So with something that's weight-free, you can't have a thread like, you can't have one thread spin on like a compare-and-set loop, because that compare-and-set might never succeed if other threads end up running and then you don't get weight-freedom. So you need some additional mechanism and we'll actually look at how that works in the context of this paper. Is work stealing a form of weight-freedom? Not really, sort of. So work stealing does have this property that if I can't make progress, someone else will make progress on my behalf. I don't think it's generally weight-free in the formal sense. All right, so let's try to move forward a little bit. So now we have this rough notion at least of what weight-free and lock-free means in this context. Data structure, I sort of assumed that you know what is. And then we have this word simulation. So what does it mean that this is a weight-free simulation for lock-free data structures? And this is something that the paper talks a decent amount about in its abstract and introduction, which is basically that it's actually fairly hard to design weight-free algorithms. Designing lock-free algorithms is complicated. Designing weight-free ones is even more complicated. In fact, I think it was only, this paper is from 2017, although I think the original version came out in 2014. And I think it was only like a few years before that that we started seeing like a binary tree implementation that was weight-free. Like it's complicated to get here. Like weight-freedom is hard to achieve. And what this paper manages to do is take a lock-free data structure or lock-free, call it a lock-free algorithm maybe. There's sort of synonymous terms in this context. And run that lock-free algorithm using a weight-free implementation in such a way that, so you take a lock-free algorithm and you run it using machinery that is itself weight-free. And this guarantees that the overall thing that you've combined is also weight-free. It's sort of the magic of this paper. And this ties into the word at the beginning, which is practical. So there was actually a paper many years ago that I think it's linked down here somewhere. Yeah, by Hurley. And then this paper is sort of a classic in the literature. But basically the idea here is that there's such a thing as a universal simulation. And a universal simulation, the paper has a lot more details, but basically the idea is that there's been a proof that you can take any lock-free algorithm and you can run it in a weight-free way. The problem with it is that it, like what that means is any of the operations in the lock-free data structure complete in a finite number of steps for any given thread, which is all that's required for weight-free them, that every thread makes progress. The problem with this universal simulation is that while it is a finite number of steps, it's a really large finite number, right? Like if it took years for any operation to finish, but every operation does finish, like even if that thread never gets to run, the operation will finish, then the algorithm is weight-free, but that doesn't really help you. You don't actually want to use this for anything because the overhead of the simulation is way too high. And so that's why this paper has this practical word in here because what they came up with was a way to simulate certain lock-free data structures in a way that's weight-free, in a way that's practical. That is that the finite number of steps that's sort of the upper bound for how long any given operation will take to complete for any given thread is not just finite, but also a reasonably low number. And in fact, if we scroll down to the performance evaluation part of this paper, if you look at this, for example, let me go ahead and zoom in a little. This should probably say top and bottom. Oh, left and right, yeah, that's fine. Yeah, so if you look at this, the red line is the weight-free, the blue line is the lock-free version that we're simulating, and the y-axis here is in seconds, and then the x-axis here, I think, is a number of cores, if I remember correctly. And so what you see is actually, the weight-free version is slower. It takes longer time for any given number of cores. And that is, again, because it has to do more things, but you see that the difference is still fairly small. As the observation here is that the weight-free implementation is slower, but it provides stronger guarantees about how long operations will take. So one thing that would be interesting, and I'm actually a little surprised the paper doesn't include this, is sort of a histogram of the time per operation. Because what I would expect to see is that for the lock-based algorithm, you end up with some operations taking a much longer time because they get stuck behind other threads or making progress, and so you end up with this like, most things are fairly fast, but some things are really slow. And in the weight-free case, you see that whole curve move a little. So all operations are slower, but you don't have a tail, or the tail is sort of bounded, which is what weight-freedom guarantees. Stream conferred to be weight-free because we're trying to move forward. That's funny. Is it just about risk, or will weight-free actually catch up for some very high core count? This one's hard to answer because I don't think we really know. I don't think we expect weight-free to outperform lock-free for any given core count in average performance. And part of the reason for that is because the operating system actually gives fairly strong guarantees around things like fairness. Like it's not gonna leave a thread not running for a long time. It's just like going to try to avoid that really hard. But when it happens, that's when you see really poor performance changes. In practice, I think where this matters more is that real programs are a little bit different from benchmarks in that a benchmark usually spins up like the same amount of work per thread and just every thread just spins doing an operation. And so all of the threads sort of do the same amount of work. In a more realistic situation, you might have one thread that's like spinning and doing a lot of operations and one that is time-sensitive. It's like maybe a user clicked a button and the other stuff is all automated. And the time it takes for that one user button click to happen actually matters a lot more than the average time it takes for these automated operations to go through. And that's where the weight freedom sort of matters more because if you look at the average, it doesn't make a difference, but in some ways like the actual customer experience, if you will, that depends on the tail latency, not the mean and weight-free algorithms tend to do better in the tail. There's an interesting paper by, I think it was Facebook a few years ago called Tail at Scale, which looks a little bit at this effect as well. The same thing comes up in things like real-time operating systems where you have some operations that are important, they're high priority, they need to finish in sort of a certain amount of time. Like imagine that, I don't know, you're flying a rocket and you need to make sure that you control like the pressure in the fuel tank and that can't be held up for a second. Like that's not okay. Even if it happens once, the whole rocket might blow up. Like this is a big problem. And that's the kind of cases where this sort of theoretical concern about some things are just gonna be slow and it's fine becomes a very real concern because you actually have hard deadlines you need to hit. And a less extreme example is something like gaming where like your time budget is until the next frame draw. And it's not okay if you have an operation that happens to take longer because of contention, right? But of course the flip side of this is even in a weight-free algorithm, like the weight-free algorithm just says that there's a finite number of steps to make progress for any given thread but you might not necessarily know what that finite number is, like what the upper bound is. If the upper bound is really large it might still be too slow. The hope of course with this paper is that the actual upper bound they achieve is low enough that it actually meaningfully reduces the tail. And so one of the things that I think we'll do probably like a couple of streams down the road is sort of benchmark this and look at the histograms of latencies for operations and look at the distribution and see does it meaningfully reduce the tail or is the upper bound set by the weight-free algorithms like so high that it doesn't meaningfully impact the tail or phrase differently, the slowest that the lock-free version ever is is still below the upper bound set by the weight-free implementation and therefore the weight-free doesn't buy you anything. Our weight-free algorithms use for things like machinery that can't risk hitting a worst case scenario or incanses in operations, yeah, so that would be an example.  In some sense it's similar, right? Like a garbage collection pause is sort of similar to encountering contention during concurrency.   Like if you have lots of threads that need to do stuff, the contention is sort of determined by factors that are like timing-based that you can't necessarily control in a good way. The tree use case seems to hit on some kind of worst case scenario. So the tree use case is actually really interesting because what you see there is the weight-free version is much slower than the lock-based version. It's not that it's better, it's worse. This isn't performance given number of cores, it's seconds, which is, so a higher is worse. So the tree example is one where the lock-free version does much better than the weight-free version or phrased differently, the weight-free version introduces a bunch of overhead. And I think they talk about that. Let's see, where is the discussion of figure nine? This is most vividly displayed in the tree data structure on the AMD. About one in 64 operations ask for help and completes in the slow path. This means that roughly during half of the execution time, there's an operation running in the slow path. We'll talk a little bit about this notion of a slow path, but the basic idea is that in the tree case, you much more often end up with threads having to help each other. On the flip side, like, yeah, and you see, as a result, all threads help this operation, sacrificing scalability for this time. And so you get worse performance, but again, my guess is that you would see this actually impacted in the tail latency. Then for the lock-based one, you end up with some operations just taking a lot longer, but it sort of gets amortized, if you will, in the measurement because the thread that wins still gets to measure a load time. Doesn't weight freedom still imply that all threads will get a CPU slice eventually? No, so that's one of the reasons why weight freedom is so cool is that even if a thread doesn't get to execute any steps, other threads are obliged to do work on its behalf. And that's how you guarantee that in a finite number of steps, like of the machine, every thread makes progress. Great, all right, I think we're now, I think we now understand the title of the paper, which I think is an achievement in and of itself. So let's then start to talk about what we're actually gonna implement. So let me find where they start talking about this here. So recently we've seen some progress with respect to practical weight-free data structures. This is what we talked about, that many weight-free data structures weren't even known until fairly recently before this paper was published. And in general, like there have been some practical designs of weight-free cues that rely on this compare and swap operation that is very common in atomic and concurrent algorithms. There's been independent constructions of weight-free stacks and cues, linked list and a red black tree, which is sort of the most recent weight-free implementation at least prior to this paper. And one of the techniques that was employed in much of this work is this idea of the fast path, slow path method. The basic idea is to have a fast path, which is like, if I'm not contending with anyone, if I can make progress without having to retry, then I should just do that. And because that should be the common case, we're gonna make that case as efficient as possible. And then what you do is you have a slow path where if you detect that there's contention, basically if you're like, I have to retry, then you take a much slower execution path where you like carefully coordinate with the other threads so that all of you end up making progress. Think of it as like, you, I don't know, what's a good example of this?  And your goal is to get through the most number of balls per second.   So this is an instance of you can take the fast path, which is get the ball, throw the ball. It's a very simple instruction. If there are say, as many balls as there are people, chances are if everyone follows that instruction, everyone throws the ball roughly at the same time or at least in a very short time period.   And no one actually makes progress. And so the way that you can try to get around this is if you detect that there's contention, for example, if you see that your ball bounces off of someone else, your instruction now changes. It moves from the fast path, get the ball, throw the ball, to the slow path, which is a more carefully considered approach to throwing a ball. This might be, you could imagine the slow path being something like look around. If anyone else is currently holding a ball, then shout out to them and say, I throw on one, you throw on two, and then count one, two, right? So this would be an example of the slow path being definitely slower, but it ensures that you get more balls through the hoop in any given period of time because you're coordinating with the others.  Let's say they fall unconscious for a second. So rather than that ball just like lying on the floor, you're actually gonna help them throw it. And that way they make progress even though they're unconscious. This would be sort of an example of the slow path being a thing that ensures that everyone is making progress, that is the balls are continuing to further, or rather every ball is going through the hoop at some rate is the other way to think about this.  You want to make sure that not only is a some ball going through the hoop frequently, but every color ball is going through the hoop over time. All right, I don't know if that analog made sense, but that's the kind of thing we're going for where the fast path is don't think, just do. And then if you notice things being weird, you go to the slow path where everyone tries to work together. Yeah, it's a brutal game. Death is no excuse. The game must go on. What if everyone is dead? Well, then I don't think it matters whether you make progress. Yeah, don't play basketball with John. Me and my 31 friends frequently throw multicolored balls. That sounds about right. But so that's the kind of thing that we're going for. Or rather, that's what most of the actual wait-free algorithms that people had implemented before this paper were implemented in this way where there was a fast path, which was basically sort of the lock-free version, right? Of just do this thing, and if it doesn't work, retry. And then the wait-free version becomes, if it doesn't work, then coordinate with everyone else and then make progress. And what the authors of this paper realized was that there's sort of a pattern here where as long as the algorithm has a particular structure, which is what they call the normalized form in this paper, as long as it has this particular structure, we can actually say, you just give us sort of the definition of the fast path, a definition of the slow path, and a definition of how to detect when you need to move from one to the other. And then we can implement, we can sort of take that description of a lock-free version and simulate it efficiently using a wait-free implementation. Think of this as like, you can sort of define a trait for a lock-free, a simulatable lock-free algorithm. And then you can write an implementation that is wait-free that uses the implementation of those methods to run the lock-free algorithm in a wait-free manner. And that's basically what we'll be encoding today. It's a long path to get there, but. And as you can see, the authors sort of get at this by saying, the process of designing a fast wait-free data structure for an abstract data type is complex, difficult, and error-prone. And as they say, one approach to designing them is to start with a lock-free data structure, work possibly hard, which I think is like understatement of the paper to construct a correct wait-free data structure by adding this helping mechanism that we've talked about, right? So you add a helping mechanism, and then you work again to design a correct and efficient fast path, slow path combination of the lock-free and wait-free version of the original algorithm where lock-free here is sort of code for the fast path and wait-free is sort of code for the slow path. And again, understatement, designing a slow path, fast path data structure is non-trivial. And yeah, it's really hard. And so in this work, what they're looking at is basically, can you mechanize this process of saying, as long as you give us a description of the algorithm in some sufficiently normalized way, we can sort of standardize the reasoning for how to run it wait-free. And as they say, we present an automatic transformation that takes a linearizable lock-free data structure in a normalized representation and produces a practical wait-free data structure from it. And the resulting data structure is almost as efficient as the original lock-free one. And this paragraph is really like the thing that made me excited about this paper because I haven't had a need for wait-free data structures. I think lock-free data structures are cool. I was like, this is a really cool transformation if they can actually deliver on the promise from this paragraph, like this is really neat. And when I started reading this and when I went through the sort of normalized data structure, I realized that this automatic transformation that they talked about and the sort of normalized representation is something that I think we can represent in the Rust type system in such a way that you can have a wait-free simulator type that is generic over a normalized lock-free algorithm type or trait rather, and then just have that work. And that would be really cool if we can get to that. And that's what we'll try over the course of the stream to get to. And they sort of give this, they have this argument for the normalized representation that they have is one that can actually be, you can represent a lot of different lock-free algorithms and data structures in this normalized representation. And therefore, this is not just like, we did this for these three data structures and it worked fine. It's actually a more general thing which makes it all the more attractive try to encode it in Rust. So that in theory, you could sort of take other lock-free data structures you can think of, use this basically as a library and say, now give me the wait-free version. And if we can get there, that's really neat. In the context of this paper, they transform a linked list, a skip list and a binary search tree from lock-free to wait-free using this sort of algorithm, this mechanized transformation. I think what we'll probably get to today just because there's a lot for us to cover, I think we won't actually implement any of these three today. Instead, what we'll do is sort of implement all of the mechanization, all the automation today and sort of the modeling of the problem and of this like normalized representation and stuff. And then next time we'll deal with, probably with memory reclamation, which will be the sort of hazard pointer stream. And then the next stream after that we'll actually try to implement like the linked list, the skip list, maybe we even get to the binary search tree on top of the mechanization that we built today. Wait, I have a cat meowing at the door which sounds like a good timing. She's very concerned about wait-free data structures. Hi, do you want to come in? You can come in. Hi, do you want to come say hi? Yeah, say hi. Where are you going? Where are you going? You're going. What?  Well, we have a cat on stream now. I'm sorry, did you don't want to be up there? All right, she's leaving. So this is not a way to implement any lock-free algorithm in a wait-free way, but a way to design lock-free algorithm in a way that makes it possible to run it wait-free at some performance cost. Sort of. So they're not claiming that this is a way to take any lock-free data structure and make it wait-free. They're claiming that if you can structure your lock-free algorithm in this way, that is if you can encode it in their sort of normalized representation, or rather if you can represent your algorithm in their normalized representation, then they can make it wait-free at minimal cost. Yeah, derive wait-free is sort of the coolest thing we would get to. Can't this be described as they invented a way to create wait-free algorithms that can be made just lock-free if you don't run the simulation? Well, I mean, if you have a wait-free algorithm, it's already lock-free. Like, there's no simulation that's needed there. The hard part is going the other way. Chai is not wait-free. Chai is lock-based. She definitely blocks progress sometimes. All right, so, hi, what's up? I'm sorry, are you suffering? Wow, she just collapsed on the floor asking for scratches. What? It's okay. There you go, there you go. You can refill on scratches. She's like grumbling. She's a very vocal cat, grumbling about not getting enough pets. Right, so let's take a look through the transformation overview, which is sort of where we'll start getting into how do we actually encode this in Rust? So the move from the lock-free implementation to the wait-free one is executed by simulating the lock-free algorithm in a wait-free manner. Simulation starts by simply running the original lock-free operation with minor modifications that we'll assume we discussed. A normalized lock-free implementation has some mechanism for detecting failure to make progress due to contention, right? So this would be the example of all the basketballs are colliding. Clearly we're not making progress. So for any given lock-free data structure there has to be some mechanism to detect that there is contention. Basically something to inform us that we need to move from the fast path to the slow path. When an operation fails to make progress it asks for help from the rest of the threads. A thread asks for help by enqueuing a succinct description of its current computation state on a wait-free queue. So we can already see that the transformation, the mechanization, the automation is going to require a wait-free queue sort of at the bottom. And so this is something we're going to have to implement. It's going to be, it's not that we're gonna simulate a wait-free queue, it's that we're actually gonna implement a wait-free queue that is then gonna be used in the mechanization. And so this might even be what we get to sort of second in today's stream. The first one being like sort of defining the trait because I think it's useful to have that mental model of what we're trying to get at, but then we're gonna have to implement this wait-free queue, because it's sort of the building block for the whole system. So yeah, so when some thread detects that it's not making progress, it has to sort of put a description of what it failed to make progress on into this wait-free queue. And the fact that it's a wait-free queue means that the enqueuing operation is wait-free, which is sort of helping it to make the overall thing wait-free. And then one modification to the fast lock-free execution is that, so this is to the fast path, is that each thread checks once in a while, which is sort of undefined. I'm guessing we're gonna run into some weirdness here of what exactly does once in a while mean. And you can imagine this once in a while sort of is the sort of scaling factor for how much, like how finite is the finite sequence, right? So we're saying every wait-free operation has to terminate in some finite number of steps. Well, this once in a while is gonna dictate how many steps that actually is, because if a thread won't make progress until someone helps it, then how long it takes until some thread tries to help dictates the overall time. So in the fast path, we're gonna have each thread check once in a while whether a help request is enqueued on the help queue. If it notices an enqueued request for help, then it moves over from sort of executing the fast path to helping that single operation on the top of the queue. And that includes reading the computation state of the operation to be helped, and then continuing the computation from that point forward. So this is the idea of we're trying to help this other thread that is currently stuck make progress. So eventually, like all, if one thread is sort of stuck and all the other threads sort of notice that it gets stuck, they're gonna start trying to help it. And eventually maybe even all the threads start helping. And at that point, there should be no contention and therefore progress will be made. But even if just one thread helps, that might be enough to make progress. But ultimately, what these other threads are gonna do is sort of look at what did the thread that enqueued this request for help? What was it trying to do in the first place?  And then pick up the computation that was enqueued and it will also try to do that same computation. And so ultimately what you'll end up with is if all the threads end up helping, all of the threads are trying to execute the same operation and so someone must succeed because they're all trying to do the same thing. And so yeah, continue the computation at that point until the operation completes and its result is reported. The major challenges are in obtaining a succinct description of the computation state. So this is basically if a thread can't make progress, how does it tell everyone else what it needs help doing without having to write gigabytes of memory to somewhere that's shared? You want a concise thing saying, I got stuck on this, please help. And also how do you achieve the proper synchronization between the potentially multiple concurrent helping threads so that they don't just all contend with each other and therefore no progress is made there either? Like again, with the basketball metaphor, if all of the people who are not unconscious walk over and all try to grab the ball from the unconscious person at the same time, none of one, no one is gonna get the ball and therefore no progress is gonna be made. So you need to ensure that the helping mechanism itself is wait-free. And this is in all likelihood where the wait-free queue is gonna come into play. And then also in the synchronization between helping threads and threads executing other operations on the fast lock-free path. So this is sort of the jumping back and forth between I'm gonna execute my operations in the fast path sort of sequence and I'm gonna go help other threads. And there has to be a balance between the two and sort of a way to determine whether to do one or the other. And so you say, I see that the normalized representation is enforced in order to allow this succinct representation and to ensure that we can detect when a thread isn't making progress and to minimize the synchronization between the two. Hello? Do you wanna smell the microphone? She's walking across my keyboard. You can see the tail right here. No, don't drink my tea please. Okay. Oh, you're scared of the Roomba. Why did the Roomba start? There's an enemy downstairs. It's the Roomba, it's driving around in her space. Let me stop that. She's funny. Pause. There we go. Could a thread that needs help just pin up a closure of what it wanted to do with the lock? So there isn't really necessarily a lock here. That it's more that, and you don't really want it to be a closure because we need some amount of control in order to guarantee weight freedom. It's not like it can be any operation that someone else can help with. If it was a closure, you can imagine that you encode all sorts of weird stuff in that closure. Instead, you want something where the other threads can help knowing that they themselves won't also be blocked by executing that code. So we probably want something a little bit more principled than just saying a closure. What does a thread do after it detected that it can't make progress, just spin? No, so if a thread detects that there's contention and therefore its operation failed, it's going to retry. And the sort of key insight here is that as long as other threads start helping, eventually the retry will succeed. In a lock-free system where there is no notion of this kind of helping, a thread might retry forever. And that's bad. That means it's not making progress or at least retry for a very long time. If you know that help is gonna come in some finite amount of time, you know that you'll also make progress in some finite amount of time. But isn't the original waiting thread completely dead at this point? The original waiting thread itself will be killed after some other thread succeeds with this helping operation. There's no thread killing involved here. Like when I say that an operation fails, it just means that the most trivial example of an operation failing and sort of you detecting contention that way is like imagine that you're trying to append to a linked list, right? The atomic operation that you do is you try to do a compare and swap of the head of the queue, the head pointer of the queue to a new node that points to the immediate successor like the first node in the list, right? And that is a compare and swap. That compare and swap will fail if the head has changed since you last read it, right? And so your compare and swap failed. Now, the way that you sort of recover from that, the way that you retry is you read the head again, you construct a new successor node that's gonna be injected and then you retry the compare and swap. So there's no death of a thread because it failed. It's just the operation failed because of contention. And so it's going to eventually succeed as long as you sort of redo the stuff that got you to that operation in the first place. How can a non-progressing thread ask for help? Ah, so the point here is that the thread sort of endures the need for help when it detects that it has to retry.  So it doesn't have to make progress, but that means all the other threads, like basically think of it as all live threads have to make progress. Yeah, this will probably make more sense when you start seeing the Rust code. This is currently somewhat abstract. Why are you eating my glasses case? Weirdo, she's a weirdo. All right, so I know we're reading through the text here. We're not gonna do that for the rest of the stream, but it is useful particularly for the sort of transformation overview because that's basically what we're gonna be encoding. And so it's worth looking at this in some detail. So the helping threads, this is if you detect this contention, you go to the slow path, you try to help some other thread. The helping threads synchronized during the execution of an operation into critical points, which occurred just before and just after a modification of the data structure. So assume that modifications of the shared data structure occur using a compare and swap primitive. So this is very common, right? So the linked list example I gave where you do a compare and swap of the head of the list. This is very common for lock free data structures, basically that the way that you ultimately sort of commit an operation almost, like actually change the data structure is you do a bunch of work and ultimately like there's a compare and swap that like commits the change. So you sort of stage the change and then you commit the change and that commit is usually like atomic in the sense that not just that it's a compare and swap but it's a single operation most of the time. And the idea, right? Is that if it wasn't a single operation, then you would need some larger mechanism for like arranging for multiple threads where if imagine you're doing two compare and swaps to commit or you're doing two operations, then now what if a thread sees one of them but not the other? What does that mean? And so generally lock free data structures are gonna have this structure where they do one compare and swap and then that is the commit point. So a helping thread is gonna run the operation by a helping thread runs the operation and attempts to help independently until reaching a CAS instruction that modifies the shared structure.  This is like the staging the commit. This might be again in the context of a linked list constructing the node that you're about to inject, right? And that work can happen concurrently on multiple threads because it's really read the head pointer, construct the thing and now you're ready to do the actual like commit point, the actual compare and swap. So the helping threads all execute that sort of pre compare and swap operation. The stuff that is entirely independent and sort of isolated doesn't need to be synchronized. And then when it gets to, I wanna execute this compare and swap, it coordinates with all helping threads which CAS should be executed. So before executing the actual compare and swap instruction, the helping threads jointly agree on what the CAS parameters should be. So remember a compare and swap is like, at this address change from this value to this value. And the operation fails if the expected value, the old value no longer matches the old value that you pass in. And so if all the threads end up sort of agreeing on what operation to do, then as long as they're all doing the same compare and swap, they can't really be a failure because no one else is changing the value that's in place and therefore the CAS should succeed. Again, and I think this will be clearer once we start looking at the code, but trying to convey the theory is pretty important. And the simulation ensures that the CAS is executed exactly once so that we don't get weird properties where like because of helping, you like inject the node twice into the linked list or something. And then each thread continues independently until reaching the next CAS operation. So the idea here is if there was a data structure, a lock free data structure that required multiple compare and swaps to actually commit, what you do is all the threads do the stuff that they can do independently before the CAS, then they agree on which CAS to execute, and then they all do the steps until the next CAS which they can do independently because there's no atomic operation in there, and then they all agree on what the next CAS could be. So there's sort of this like, execute in parallel, agree, in parallel, agree, and ultimately that guarantees that you make progress because they all agree on the CAS and so they will succeed with the CAS. And then upon completing the operation, so this is like after all the CASs have completed, the operations result is written back into the computation state. It's removed from the helping queue and the owner thread, the one that put the help request in there can then return from whatever operation it inserted, right? So to sort of give the full overview here, and maybe I should actually try to draw this. Let me see what drawing this might look like. So let's do like light blue is probably good. So what we have is what's a good way to draw this. We're gonna have some thread over here. This is the owner thread in like turquoise. So the owner thread is let's say trying to do an insert into a linked list, right? And as part of that, it does like a, it sort of constructs the new node. Yes, new, right? It constructs a new node and then it does a CAS to try to inject it into like the, into the head of the linked list, right? So that's how it's gonna try to make progress. If that fails because say some other thread, thread two, also updated the head pointer at the same time, if there was like a conflict there, then this CAS is gonna fail because of that conflict. And at this point, what the original thread is gonna do is it's gonna say, it's gonna sort of encode the information that is needed to do this operation. It's gonna stick that into this shared queue of help, right? Help. So it's gonna sort of stick its insert in there. It won't actually be the insert, but we'll look at the sort of how to make a succinct representation to stick in that queue, but you can sort of think of it as the insert. And then at some point, the other threads in the system, so let's say there are three other threads, right? Because we said that on every fast path, every thread is gonna check the help list every now and again, so this thread is gonna sort of see this. And eventually this thread is gonna see this, right? And whenever they see it, they're gonna also try to do the sort of insert, which is gonna be a new node. And they're gonna run it in parallel, right? When they see it, they're gonna do new node. And in fact, the original thread, this thread, after it enqueues, so it does, I guess, one, two, three is when it observes the failure, four is when it enqueues the help, right? And then five, it's going to retry the operation as well. Like it's gonna try to help itself as one way to think about it. So notice that at this point in time, this thread and this thread and this thread are all executing in parallel. They're all constructing a new node for this one same insert. So they're all sort of doing the same work. And then all of them are gonna try to do this compare and swap in order to insert it into the head. And because there are no other threads in the system, the operation has to succeed because a CAS only fails if the expected value is different, but the expected value would be the same because no other thread is updating it. So we're gonna have some mechanism for them to sort of coordinate on the CAS and therefore this CAS is gonna succeed. And then regardless of which thread succeeded with the CAS, the owning thread is the one that's sort of ultimately going to now return from the insert, right? And these other threads are gonna like continue doing what else they were doing at this point because now they've like done their one help per fast path or whatever the actual ratio ends up being and now they get to execute their own instructions, but they did help the blue thread here make progress, which is what is required. So yeah, you can sort of think of this as consent, like the slow path is sort of consensus in a sense, but it's not, I mean, it's among threads. It's not sort of over a network. So you have some slightly stronger guarantees. This sounds like it would degrade to single threaded execution all the time. So the hope is that it doesn't, right? So this is why you have this fast path, slow path mechanism where if there isn't any contention, then they can just proceed in parallel. But okay, take them the linked list example, right? If you have multiple threads that are all trying to append to the queue, the best you can sort of do is like one and queue per cycle. Like you can't have multiple in queues per cycle because they're all updating the head pointer. This is like a limitation of linked list, right? That there is only one head pointer. And so if you can achieve one insert per cycle, depending on however you define long a cycle should be, then that's great. Even though that is, you're right, that single threaded execution, but the alternative is that no thread makes progress. That would be way worse. In the linked list example, it's hard for that to actually happen, like a linked list is actually fairly easy to make weight free or not to make weight free, but to make lock free. But you sort of want it to degrade to single threaded performance if the alternative is that no one would make progress because what you can do with the single threaded execution here is to make sure that every thread makes progress. Because as long as you do the help list in order, then like if I try to do some operation, I stick it in the help queue, then I know that it will get executed in some like finite amount of time.  It's a bit of a combination. Some of the work recently I think has been looking at like sort of model checking and formal verification and stuff. In this case, I think that there's like a formalized argument a little bit later in the paper that actually goes through like here's the actual formal reason for why we can guarantee that everything terminates in a finite number of steps. In practice, you also do benchmarks. But as you saw from the paper, like weight free is a little weird in that your performance results will at least naively not generally reflect the benefits of weight freedom. Which might make you think like maybe there are no benefits to weight freedom and there are people who argue that that it's just never worthwhile. In fact, if you read the paper on obstruction freedom, that's basically what they're saying that you should just write things that are obstruction free because it's good enough in practice. And this is where you sort of need to develop more advanced benchmarks to figure out whether it's actually worthwhile. I'm hoping we can look at that a little bit later too. How is this better than just normal CAS? I thought the point of atomic operations with the OS would make sure that operation was synced on all threads. So then what's the point of this transformation? The point of the transformation here is that if you didn't have all this machinery, then what does it thread do if it's CAS fails? It retries, right? But you could imagine that it has to retry forever because every time it does a CAS, some other thread wins the race with it. Like some other thread is doing an NQ and it happened just like a microsecond sooner.  What this algorithm does is it ensures that your operation will eventually succeed when you retry and not just eventually but with an even stronger requirement that in some finite number of steps, some upper bound, your operation will succeed. I think in practice, the way the finite steps are recovered is like the number of finite steps is like linear in the number of cores and entries in the data structure. I forget exactly that the paper says, but basically like the finite number of steps is like finite as in it's some known limited quantity. That doesn't necessarily mean that it's like three seconds. Like it's not quite that finite. It's not that all threads go to the slow path if there's any contention. That's not quite right either. It's that if the thread gets stuck, then it adds something, it adds the operation it got stuck on to the help queue and then it tries to help itself. It might succeed before any thread even tries to help it. All we're requiring is that threads that are going through the fast path occasionally check the help list and then try to help the top thing in the help list. And it might be that the moment any thread tries to help, progress is made and so the next time some thread is executing a fast path, there's nothing on the help list anymore because it succeeded. And so it's not necessarily all threads. It's not like if anyone has contention, they start like a blocking consensus algorithm. It's more the sort of dynamic detection of if someone needs help, I'll help. Otherwise I'll do my own thing. Aren't you effectively wasting a bunch of time because surely only one thread's cast will actually be committed? So what you're trying to do with this algorithm is to ensure that it's not just some cast that succeeds, it's sort of the cast that's been waiting for the longest time. That's not quite accurate either, but basically you don't want the scheduler to determine who wins the race because that can easily lead to something like starvation which is where you get the tail latency from and that wouldn't give the guarantees of weight freedom. If there's other stuff in the queue at five, does the blue thread only help itself? We'll look at that. The paper talks a little bit about this too. In general, threads are executing on the fast path only help one operation and then proceed with the fast path. Threads that are themselves stuck will help the entire queue in order until their own operation has completed. Is the help queue a solved problem? How does it not also cost contention? So this is where the, I think this was in the text too, the help queue is a weight-free queue. So enqueuing and dequeuing from the help queue is itself weight-free. So this is where we're sort of building this tower of things that are weight-free all the way from the bottom to ensure that the overall thing is also weight-free. And this is why I said, we're probably gonna have to implement the weight-free queue fairly early on because it is such a fundamental building block. Who clears the insert from the help queue? They actually all try to clear the insert from the help queue once they realize that it's finished. We'll look at that in a second too. Yeah, so we will implement the weight-free queue in this stream. If you wanna look at it, it is appendix A of the paper that I just had open and sent the link to to chat. So for weight-free instead of exponentially backing off CAS attempts in case of failure, we pass our work to other threads so that we get the work done by another thread. That's almost right. So in the case of this weight-free simulation, what we're doing is if a CAS fails, we ask for help from other threads and then we keep retrying. And because threads will eventually help, there's a guarantee that even if it keeps failing, at some point, every thread, every single thread must be trying to help. And therefore the operation must succeed because there is no contention anymore. In general, the operation should succeed far before every thread comes to help. But there's a guarantee that there's a finite upper bound. So what if the first thread dies before it puts insert in the help queue? How does that work? If a thread dies, then it's gone. There's no requirement for you to make progress on it anymore. What you need to guarantee is that every thread that has more instructions to run, or has more operations to run, gets to run those operations, you're not required to resurrect threads. That's not a thing. You can think of it as if a thread crashes, it has no more operations because its execution sequence has ended. Why can't the other thread not just do nothing until the original thread has helped itself? I mean, they could do that. You could imagine that helping is just do nothing. It requires the same amount of synchronization. So I don't know it really benefits you. And also it's not clear how you do nothing. Is that a spin loop? Because if you do a spin loop, then you might be taking up the core that the other thread could execute on to make progress. Imagine you have one core, but a thousand threads, right? The owner thread, the one that needs help and queues the help operation. And then all these other threads start getting scheduled on that core. And they all see that some thread is trying to make progress, so I'm gonna wait. I'm gonna just like do nothing. It can go to sleep, but then you need to specify how long it sleeps for.  So that's not good. So the alternative is that you spin waiting for it to finish. But if you spin, you're taking up the current core and there's only one core, so the thread that could actually make progress never gets to run. As you need to wait for in a fair schedule or a thousand or 999 threads to finish spinning before you can actually make progress. Whereas in the help case, the first thread that comes along on that core sees the help operation, executes, succeeds, and now can go on with its own thing. So waiting wouldn't actually benefit you. It would hurt you. This applies even if there are multiple cores. When do helper threads actually try to help? Do they have to help every time after the first fast path operation or is it heuristic based? Like help another thread for every end fast path operations. This is where the paper says once in a while, they have some more details later on the paper that we'll get to once we actually do the implementation. Great. So I think now we have a sense for what this helping business is doing and sort of what the algorithm is getting at. So there's this notion of the lock free algorithm has some notion of things you do before the CAS, the CAS, which is the actual commit operation that you might contend on, and then maybe stuff you do after the CAS. But the CAS is sort of the point of contention. And that's basically what their normalized representation is. We'll look at this in a second. There's the stuff before the CAS, the CAS, the stuff after the CAS. So yeah. So this is where upon completing the operation, so that is when all the CASs in a given help have executed, the result is written in the computation state. It's removed from the helping queue. And then the owner thread, the one that initiated the operation can finally return whenever it gets to execute next. So its operation got to complete, even though it didn't actually run. And as they say, there are naturally many missing details in the above simplistic description, but for now we'll mention two major problems and these are kind of relevant for the implementation we'll do. The first is that the synchronization that we need for the helping threads before each CAS and after each CAS so that they all learn whether one of them succeeded on the CAS is like fairly complicated. There's a lot of, it's basically consensus among the threads that decided to help around that CAS. And consensus is hard. And there's like ABA problems and versioning. We'll get into all of this when we get to the actual implementation. And the second problem is, as we mentioned earlier, like how do you represent, like in the drawing, right? I have the insert operation in the help queue, but in reality, you don't want the help queue to actually contain like all of the parameters to the function that originally came in. Like that's probably overkill. And the observation they make is that for a lock free algorithm, there is a relatively lightweight representation of its computational state. Let's see, so what are they getting at here? This is because by definition, if at any point during the run, a thread stops responding, the remaining threads must be able to continue to run as usual. This implies that if a thread modifies the data structure, leaving it in an intermediate state during the computation, then other threads must be able to restore it to a normal state. So the idea here is that we're basing this algorithm on, or we're basing this simulation on an algorithm that is lock free. And that means that the algorithm as it already exists must be able to cope with some thread executing and then that thread dying and that thread dying is not allowed to prevent us from making progress. It's like one of the guarantees of lock freedom, which means that there has to be some concise description in the algorithm already for how do we undo what that other thread that didn't finish do? Or how do we help it finish? Like we need to restore the data structure in order to keep operating. So some notion of this like compact state must already exist. The information required to do so must be found on the shared data structure and not solely in the inner thread state because otherwise the dead thread would be required to talk to the living threads to tell them what it failed to do. And that can't happen because the thread is dead. So basically what they're arguing here is that any lock free algorithm you come with, there must already be some succinct description of the operations of the algorithm stored in the data structure somewhere, somewhere shared. And so we can just reuse that representation for what goes in the help queue. Again, we'll see a more practical example of this once we get into the code. Yeah, so section five has this normalized representation. We'll look at that when we start writing the trade. Yeah, and this also, this is not terribly important in our case, but basically you might have lock free algorithms that have multiple CASs. In general, like think of something like a link list. The way that removal usually works in a lock free link list is that you're not, you don't actually, like you don't free the item the moment you remove it from the link list because if you did, there might be other readers who are currently accessing that thing and that's not okay. So generally there's some like two face process where you like mark the node, actually it's not even about freeing, it's about if I try to remove a node and someone else tries to add a node before it at the same time, you end up with a broken link list and that's bad. But the observation is that during say an insert operation, what most of the lock free algorithms do is there's like a, there's an important CAS which is the one where you actually insert the node that the user gave you. And then there are unimportant CASs which are you sort of walk the list a bit and look for nodes that have been marked as to be removed and then you actually remove them. But those auxiliary CASs as they call them are ones that any thread can do them. And in general, they're also idempotent but that's not terribly important in this context but generally like this is just like CASs that anyone can do at any time, they're not something that you have to synchronize on because if you fail, it's not the end of the world, you could always just do it again later. And therefore these can be run by the helping threads without any synchronization. And so in general, the assumption here is that any lock free algorithm has some notion of like the critical compare and swaps and those are the ones we have to build consensus around but the other ones we don't. So again, for insertions, critical one is the insert auxiliary ones are like actually doing cleanup from removals for example. All right, so we now have... How do I wanna talk about allocators yet? No, I don't think so. Okay, so section three is just like talking about what is the sort of assumptions of the computational model like basically what do they assume about the machine and the context in which this code is running? This is important because once you start to give a formal argument for why something is or is not weight free, you have to rely on assumptions about how the underlying machinery works, like how the CPU works, how the instructions work, how the scheduler works, how memory reclamation works. That's not terribly important for our case because we're just trying to implement running code. We don't necessarily care about the formal model. One thing that is important here is that they assume automatic garbage collection is available and it's not in Rust. This is going to be something we're gonna run into in our implementation where there's just like not a mechanism in here for how to deallocate memory safely. We have some options there. We could use something like Epic-based memory reclamation, which we talked about back when we did Flurry, the port of the Java concurrent hash map. You could do something like, something called hazard pointers is a very common implementation. And in fact, something that they also talk about, you see here, they like refer to section 11.1. And in that section, they talk about, oh, you can just do it with hazard pointers and it's fine. Hazard pointers are not entirely trivial. And there aren't, as far as I know, there aren't any very reliable Rust implementations. There are some, but they're either a little simplistic or haven't been maintained for a long time. And so this is why I'm thinking, for the next stream, we might actually implement those so that we can use that to implement memory reclamation and what we built today. And then here, they talk about sort of some of the typical lock-free algorithms. So let's see, this is some definitional stuff. What they do here is they talk about existing data structures. So this is stuff like the Harris's linked list. So this is a wait-free linked list. Someone asked in chat, like, can you give a brief introduction? Like the brief introduction is basically this paragraph and what follows, which is sort of, how does a wait-free linked list work? How's that implemented? And they talk about sort of this notion of deleting nodes, what are auxiliary CASs? Like this section is worth reading just because it gives you some intuition for how do the existing lock-free algorithms work? And how does that sort of tie into the model that you're trying to establish for their normalized form?  This is something that I recommend you read on your own time if you want to get a better understanding for how these fit together. One of the things that they talk about in here though, which is worth talking about is they talk about this idea of counting the number of failed CASs as a way to indicate contention failure. So the idea here is we need to have some mechanism as we talked about earlier on for detecting when is there a contention, which in turn informs when do we move from the fast path to the slow path? And what they're saying is one good way to measure contention is if a CAS fails, add one to the contention counter. There are more complex cases, like if you look at appendix B, they talk about more cases where you can have contention that doesn't manifest in the form of a failed CAS, and it's important for the weight freedom of the overall algorithm to include those. And so that's something that we're not gonna worry too much about for our implementation here, but it's something that does become relevant down the line and is very important for their formal reasoning for why this is always weight-free. We're not gonna talk too much about it. The other thing they introduced in this section is the notion of a CAS description. So this is sort of a description of a CAS that you want someone else to help you execute. And it's just like the address of the thing to do the CAS on, the expected value, and the new value. This is what a CAS, the arguments to a CAS is. And we'll see this come up in a bunch of algorithms later on. And now finally, we get to this notion of the normalized data structure. And this is where we'll try to encode this in basically a rust trait and sort of a structure around it. Let's pause there though for a second because again, I've been talking a bunch sort of getting to this point. And if they're unclear, un-clarities, if it's unclear how we got to this point or if anything is unclear about what I've said so far, now's the time to sort of re-synchronize no pun intended before we dive into the actual code. And I know that some of you are like get to the code and we're about to, I promise. Let's not use blockchain for consensus. No, please no. If this is based on CAS, does this still apply on ARM? That's a good question. This is, so you can emulate compare and swap with load locked and store exclusive, store conditional on ARM. So that's one way to get at this. There definitely are sort of assumptions in here that you have access to compare and swap. I don't think it's necessarily, I think it would still be wait-free if you used LL and SSX as E, like the ARM equivalent to implement the CAS, this would still be wait-free. It might be a little bit less efficient. Like you could imagine that there's a slightly optimized ARM version of this encapsulation. I think they talk about this a little earlier on the paper too of how this translates to sort of the sort of load locked construction, but it's not something we'll talk about too much here. I don't think they assume sequential consistency. I think acquire or release is sufficient for what they need, but I forget. This is also, so the actual code they implemented for this algorithm is written in Java and Java has its own sort of special memory model. And so some of that is probably implicitly encoded in some of the algorithm. I think what we'll probably do here is start with just writing it using sequentially consistent ordering. And that should be okay because the sequentially consistent ordering shouldn't remove the guarantees of weight freedom because really what the sequentially consistent thing does, well, it does two things. It requires a bit more synchronization among the processors for deciding who gets to go next. Like they need to mediate the axis a bit more, but that should be finite number of steps. I don't quote me on that, I could be wrong, but I don't think that matters. And the other is you lose out on some like pipelining and compiler optimizations. That too shouldn't impact the sort of algorithmic complexity or the whether the number of steps is finite, even though it might increase the sort of absolute quantity of steps. Two hours and still not code. I know, I know, I know. But it's important. I think if we dose straight into the code, I don't think we'd get very far. I think we'd have to refer back to the paper a lot. Let's see, are there bathroom breaks? Yes, in fact, I think this is a great bathroom break right now. In fact, I'm gonna go take one right now. I will, actually, I'm gonna use my new pause screen. I guess it's not new. Some of you have seen it before. There should be a pause screen on screen now. I'll be back in like two seconds. So we could take a short bathroom break before we actually dive into the code here. The topic is wait for you, but we still have to wait. That's funny. Let's see, let me bring this back here. Programming is more reading code and less of writing code. Yeah, it's true. I mean, I think you're also right that if we dove, just check that you can still see my screen video, just that I pressed the wrong keys. But yeah, I think it's important to go through this paper in part because what we're actually encoding and modeling is fairly complex. And I think if we complex, if we dove straight into the code, I think we'd basically have to refer back to the paper a lot anyway. And I mean, we still will, but at least now we have this sort of shared understanding before we go into the code, which I think is gonna make that a lot nicer. Yeah, the bathroom break does have a guaranteed upper bound, actually. I know it's amazing that I can guarantee that. Remember really funny, is someone else just sat down and finished it? It's true. I'm gonna get rid of the stream. Go help John, that's very funny. All right, so what I actually wanna do here is I'm gonna, instead of starting to go through the normalize data structure chapter and then write the code, I'm gonna try to go the other way around. Even though I've read this section like once before, but what I wanna do is start writing what I think this trait will look like based on what we've discussed so far in the stream and then check it against what they actually describe in this like chapter five. And the reason I wanna do that is because doing it that way I found is a great way to like check your own understanding. It like, hi cat. It forces you to like face your own misunderstandings. If you make a prediction and then the prediction is wrong, this is like science, right? You make a prediction and if the prediction is wrong, you learn something. Whereas if you just sort of follow the stuff and then write the thing, you might not explicitly realize that you have the wrong mental model. And so I think this is gonna be interesting. Okay, so we have the biggest problem of the stream which is what do we name this? We're gonna create a new library and this is gonna be important because this is gonna be a library that everyone's gonna be using for simulating lock free algorithms using wait-free implementation. Basketball is pretty funny, but bystander is good. Ooh, I like bystander. It's very subtle. Bystander is a subtle name, but it is pretty nice. Hi cat. Do you have a suggested name? Chai, what do you think? Here, let me give her the mic. Chai, what name do you wanna give? Why are you climbing on the printer? Climbing on the printer to be next to the microphone and smelling it. Dodgeball, non-stop, also pretty funny. Hurry, meow, meow. Cueless is like cute, but it's false is the problem. Submaritan, also pretty funny. Unstoppable, also very good. Oh, freeway, that's too silly. Okay, I think it's between bystander and unstoppable. All right, what do we think? Bystander or unstoppable? I have some plus ones for bystander. I have one plus one for unstoppable. All right, it seems like bystander is the winner here. All right, let's go with bystander. I like that. Just imagine in 10 years from now when you can tell your grandkids about how you were there for the naming of this legendary library that is used everywhere now. All right, we don't need no test yet or we don't have anything to test yet. So we're gonna trade and this trade is going to be called. Let's start out with the boring name and then we can come up with a fancy name for it later. So this is a normalized lock-free, normalized lock-free. This is not generally the way that we name traits in Rust. Why are you eating my pen? Chai, excuse me, excuse me. You're looking very cute in there, but what? Those are my keys, thank you. Are you bored or something? Come here. Hi. Chai, what do you think it should be called? Huh? What do you think the trait should be called? Okay. It has a normally in Rust, traits are named by verbs. And like they're sort of named by what the thing enables you to do. Most of the time at least. There are some exceptions. Like extend is a good example, right? Of if something is extend, it allows you to extend the thing that implements extend. Iterator is a little weird because it allows you to iterate, but it's not called iterate. Append has a normal name because it allows you to append to things. Future is weird because it doesn't allow you to future. Like that's not really a verb.  In this case, I do think we want a more descriptive or more rusty name, the normalized lock free. The reason I chose this name for now is because I think it'll help put in context all the things that we're gonna put inside it. And then we can figure out a better name for the trait afterwards. So the reason I don't wanna call this, someone suggested like transform to wait free is because the trait itself is not a transformation to lock free. Basically what we're gonna have is sort of like a struct that's gonna be wait free simulator. And it's gonna take a normalized lock free. All right, like this is the sort of situation that we're gonna run into. We're gonna have a wait free simulator that is gonna be generic over the lock free algorithm that it's going to simulate as long as the lock free algorithm is in this normalized form. So this is sort of the construction that I'm imagining. And so the idea would be that if you wanna create say a wait free linked list of type T, then what I'm imagining is that this internally really just contains a simulator which is gonna be a wait free simulator over a like lock free linked list over T. And then this is just sort of pseudocode at this point, but I'm imagining that there's like methods on this, like this has like an insert method which takes not me itself because it's gonna be concurrent. And some T, I guess push front would be a more idiomatic name. And that's gonna do like self.simulator. I don't even know what this is gonna end up looking like. Like I don't know how the API of the simulator itself is gonna look like yet, but think of this as like NQ insert T, probably something along those lines. That's gonna be like let I, and then we're gonna do something like self.simulator.wait4I. I don't know yet. Well, we'll see how this turns out. But yeah, so lock free linked list is gonna be like a we're gonna implement normalize. So let's say we have a struct lock free linked list over T and we're gonna do something like implement normalized lock free for lock free linked list T. All right, so this is the kind of structure that I'm imagining and I don't quite know yet what methods will have on wait4I.simulator and what methods will have on the trait. That's sort of what we're trying to figure out on how to model this, but this is the construction that I'm imagining, right? That the actual like public type of someone who like this, I guess this is gonna be in bystander, right?  This is gonna be in a consuming trait, wait free linked list trait in consuming trait, right? So we provide this, which is basically everything that's in the paper, and then for each data structure, we implement a wrapper around the simulator and we implement the inner lock free type and the simulation between the two is provided by the bystander library. Does that construction make sense? Oh, someone said, wouldn't it be try push front fast forward someone said, wouldn't it be try push front fast path? Joe, I'm imagining that actually Joe, in this consuming trait, this will be public, but the wait free simulator is not public. The lock free linked list, inner implementation is not public. So it's only really this API that's public and behind the scenes is sort of in queue operation that maybe there's no in queue, like maybe it's just run, right? Or maybe it's just that, I don't know yet, but run is going to first try the fast path for the inner lock free implementation, detect contention and fall back for the slow path, all internally in the simulator. That won't be something that's a part of the caller, like the public signature of whatever uses bystander internally should be sort of a standard interface to say a linked list. As for it being derivable, I don't think the inner type I don't think is derivable because that's really encoding a lock free algorithm, which like you can't derive that, but you could totally imagine deriving the sort of, the wrapper type is sort of trivially derivable, like you can imagine having like a derive wait free on this that generates this type and also these wrapper methods. There might have to be some annotation on like which operations you can do, maybe it's not quite a derive but some other like wait free and then like push front equals insert. Like you could imagine something like this that generates this. So I think you could conceivably have a wrapper. I don't know that the wrapper adds too much. Like I don't know that a procedural macro will really benefit you very much here, but I think you could still imagine something like that. Someone asked in chat, yeah, the streams are archived. I upload all the videos to YouTube afterwards. So we still have this question of sort of fundamentally, what is in the normalized lock free trade? And the way that we've described it so far, right? There's like a pre-cast. I guess all of these probably take self. There's a like help cast. We're probably more arguments here and there's a post cast, right?  There's the stuff that can be run independently leading up to the cast and then the stuff after the cast that all the helping threads can also execute concurrently. And so the lock free algorithm needs to dictate all of these because that separation is sort of a property of the algorithm itself. And there probably has to be something else like this probably has to return like a cast descriptor. So remember we talked about this in the model, but the cast descriptor probably varies per data structure. Right, so maybe there's a cast descriptor associated type. And the reason this is an associated type is because I don't want to get warnings for this quite yet, thank you. In fact, let's just get rid of this stuff all together. For now, I don't care about these warnings yet. And let's make this pub. And let's make this pub. Just stop yelling at me compiler, thank you. That's fine, great. Yeah, so precast is gonna have to generate a cast descriptor and in fact we know that they sort of mentioned that there might be multiple sort of commit castes even though there's usually just one. So here I could totally actually imagine using something like arrayVec, which is a crate where it's an array up to a certain number of values and beyond that it's a vector. So I could imagine using something like an arrayVec of descriptor of one. And then helpCast probably takes in like a, maybe like a slice of cast descriptors and maybe even which one to help with. Maybe something like that. So like these are all the castes that came out of the precast. And I want you to help with this one. I guess we don't have an arrayVec here yet. So let's just say that this is an array of length one for now. And we can always optimize it later. This to me is like, at least a start. Oh, cast descriptor probably has to be executable in some meaningful way, but might not be something we have to do in the simulator. There also has to be a contention failure counter here, right? Like we have to have some way, actually maybe this is not help. Maybe this is execute cast. And maybe this is not even pre, maybe it's just, maybe it's just pre-executed in post. So maybe this is prepare, this is execute and this is cleanup. Oh, they're all the same length. Very nice. Yeah, so remember there has to be some mechanism for say like detecting contention so that we know when to switch from the slow, the fast path to the slow path. So maybe there's like, this is also given a contention, which is gonna be a contention measure or something. And so we're gonna have a pub struct contention measure, which is gonna have some API that I don't quite know what it looks like yet, but maybe just detected. And maybe this is just a use size. And all that does is self.zero plus equals one. Hi, what's up? So we're gonna pass this into the execute so that we have some way of learning about the amount of contention that's going on in the system. Oh, yeah, tiny back is maybe the one I'm thinking about. It's not terribly important. What's up? Hi. What, do you want lunch? It's not lunch time for you yet. Well, she disagrees. No, it's fine. She'll survive. Yeah, so I feel like something like this is roughly what we're looking at. And then the other question becomes like, how do you actually like enqueue an operation? Like there has to be a sort of operation here, right? In fact, maybe operation is an argument to the trait. The reason I make this a type parameter to the trait itself is because you could totally imagine that some algorithms, some lock free algorithm is able to be sort of normalized in multiple different ways, depending on the operation. Like the trivial example of this is if the, whoop, shy, I'm sorry, are you feeling neglected? Yeah. Yeah, so for example, for our linked list, right? It sort of wants to implement the trait for each T. Maybe. I don't know yet. Let's leave it as an associated type. In general, I think the recommendation is like, if it can be an associated type, then make it be an associated type and only sort of promote it to a generic type parameter of the trait, if that ends up being necessary. And I'm not sure whether it needs to be necessary yet. And I think the idea is like, prepare is gonna take a description of an operation, maybe a self operation. Right. So that's sort of what I'm thinking. And then for info, wait for simulator.  Maybe there's a result as well. Maybe it's input and output. And maybe it returns LF output. Cause you can totally imagine, like if you want to do a get operation, it has to be possible to get an actual return value out of the operation, right? This isn't done yet, of course. And I'm imagining that run does something like self. I guess this is like algo or inner or yeah, algorithm. Algorithm.prepare the op. So that's gonna be like, this is gonna be essentially encoding the fast path, right? So this is gonna be CAS and then we're gonna do self.algorithm.execute. I guess the CAS is, let's leave out the I for now. Doesn't seem immediately necessary. We're gonna need a sort of contention, which is gonna be a contention measure starting at zero. We're gonna give it in like, I guess this has to be a mutable reference to one. So we're gonna have this pass in a mute to contention. And I guess execute probably needs to have some way to say that it failed, right? So maybe this returns a result cause we need to know whether we succeeded or whether we failed. And if so, there's probably some kind of contention. So either it returns nothing or it returns a use size maybe, which is which one failed. So we're gonna match on this. If it's okay, then we sort of succeeded on the fast path. If it returned an error of I, then this is gonna be the slow path, right? So this is gonna be ask for help. And the fast path we just do self.algorithm.cleanup. I don't know, maybe cleanup needs to take in the CASA somehow or take in the operation. I feel like probably not.  But I think this is the sort of structure I'm imagining that this ends up having. Mm, yeah. And for the slow path, I guess is gonna be something like, well, so what I drew, right? It's gonna be something like this has to have like a help which is gonna be a weight free queue. Or I guess it's gonna be a help queue. We don't actually have help queue yet. We're gonna have to implement that. And I don't know what it's gonna hold yet, but help queue, it's gonna be a weight free queue. And it's gonna have a sort of add. It's gonna be weight free, so it's gonna be concurrent. It's gonna take immutable references self. And it's also gonna take, I guess, a description of help. I don't know what help looks like yet. It's gonna have this. And we're gonna have to figure out what does help look like. We don't know yet. And it's gonna have a sort of, I guess, a peak. It's just gonna return an option help. And we're gonna have a, I guess, pop front. Or remove front. Right, so I think the idea here is that for the help queue, right, you want to, if you're trying to, if you're in the fast path, for example, you're gonna look at the head of the queue. If there's nothing there, you keep going. If there is something at the front of the queue, then you try to help this operation. And then at the end, if some to be helped operation completes, then you like sort of, I guess try remove front, and you pass in the help that you tried to remove, maybe? And it does something. I don't know exactly how this is gonna pan out yet. I'm imagining something kind of like this for the help queue. And I guess, like if false, currently we're not being very helpful, but if sort of, okay, what was the phrasing in the paper? Once in a while, which we're gonna define as false, then we're gonna, if let some help is self.help.peak, then do something to help, I guess, help, help make progress. If, and then there's gonna be something there to sort of remove it if we actually ended up completing the operation.  I don't know what the help actually looks like yet. And then I guess while, actually, maybe what we do is we create a help. We add like a reference to the help, maybe. Maybe we stick on here as like a, not a static, but it's like a raw pointer to the help. What this gives you back is a raw pointer to the help. This is also a raw pointer to the help. And then what we'll do is like, we're gonna pass in, we're gonna stick the help on the queue and then while like help.help.help.help completed. And we don't know how completed it's gonna look yet, but you can imagine that whichever threads end up like helping it pass the finish line is gonna set this completed flag. And so while it hasn't completed yet, then we do like help, which I guess maybe we factor out help into its own method. And that's gonna be this like whatever we do to help help make progress. And maybe this takes like a one. All right, I guess maybe it's always just one. So this one is gonna do self.help, self-help, nice. And this one is gonna do while my help hasn't completed, I help out whoever is at the head. And I guess this means that help is gonna have to have something along the lines of completed, which is probably gonna have to be an atomic bool, I'm guessing because it might be modified by multiple threads. So we'll need standard, standard sync, atomic, atomic bool. Probably gonna need a bunch of things from atomic, but that's sort of the start. So our help here is gonna have completed be an atomic bool of false, because it hasn't completed yet. This needs an ordering. So we're gonna bring in ordering. And notice that this is still just sort of based on our rough understanding of like the organization of the code, like what has to happen when. I haven't actually figured out like what does help do? How do we describe operations like that? I think it's gonna be described much more in the paper, but it's more like the outline of the algorithm. All right, so we don't know how we help something yet. This is gonna help until our help has completed, which is all we really care about. And I guess the help is probably gonna have to say like at, which is like, where are we helping from? And that's probably gonna have to be an atomic use size because we're gonna make progress on it over time. Right, so initially we need help from the very beginning of the list of like CASAs, but as we make, as we succeed on some of the CASAs we're going along, we no longer need help with the earlier one because they've already completed. So maybe this has to be like an atomic use size that initially starts out at the place where we started failing. And that might be the zero of CAS, like imagine that for a linked list, right, there's only one commit CAS. So if it failed, I will always be zero, it'll be the first CAS. And so we'll ask for help starting at index zero of the CAS list. Yeah, that seems about right. And we still don't really know how we get the output from this. We don't really know how the input ends up going into the algorithm or into the help. So there's definitely some stuff we're still figuring out, but I guess this is at least a start. Maybe help just has a pointer to the T or to the input. I don't know yet. All right, the structure that we've set up so far makes sense before we start looking at the paper and seeing all the things that we got wrong. Is it safe to peek if the queue is constantly changing? Yeah, so this is one of the things that we need to figure out, right? Which is it should be safe. This is one of the places where memory, like freeing memory becomes a challenge, right? Because peak is always gonna return you, like think of it as a pointer to the help at the head of the list. And that pointer, like if someone frees it, it's a problem because our pointer is no longer valid. And this is basically the sort of heart of concurrent memory reclamation. There needs to be something that ensures that the help doesn't go away. I think what we'll actually do in the context of this stream is just not worry too much about memory reclamation and just be willing to leak memory. In which case, if nothing's being freed, all the pointers remain valid. And then we'll deal with the actual memory reclamation issue probably in a later stream. The formatting of the false is really confusing. Yeah, you're right. Help just look like a real word anymore. Can you talk a bit more about our associated types and their intended usage? Yeah, so the associated types here are the cast descriptor is gonna describe which castes still need to be done. And maybe this isn't an associated type. Like maybe this is just a type that we define. I'm not sure yet. It's a good question. This might have to do with versioning. Might be the reason they have to be different. But that's sort of getting ahead of ourselves. It might be that the cast descriptor doesn't need to be something that is sort of provided by the implementation. It might just be the same for every implementation. I'm not sure yet. The input type is like, what is the operational type for this data structure?  Those are the inputs. And so we need to be able to represent that somehow. In practice, the input type is probably always going to be an enum. And I don't think we can get away from that. Like it would be nice if there was a way to not have it be an enum. But I think ultimately we need a single type to represent the operation that is to be executed because we're gonna have to stick that operation maybe in the help struct for example. And so it can't have, we can't stick multiple types in there.  And similarly, the output is going to be the sort of operational, the output of the given operation. So the output for say, a lookup is gonna be like a reference to the inner T or something similar. The output for a remove might be the element that was removed. In practice, I think there's an argument for input being, yeah, I mean, it's a good question. Like output here will also be an enum in the way that we've currently structured it. And that's a little weird because it means that illegal states are possible to represent, which is generally a bad thing, right? So imagine like if input and output are both enums, you can imagine input being like the lookup variant and the output enum being like the remove return type variant, that would be bad. We might be able to tidy this up a little by having like input needing to implement some other trait operation. Maybe that has an associated type output. And so if input implements operation, then like whatever is using the output is actually gonna be LF input output as operation output, maybe, like something like that so that we, but even then that doesn't really get you very far because the input type is an enum, right? So the output type here is still an enum. So this still doesn't give us the sort of type safety that we want, but I don't have a good way for us to represent that. Maybe that will come to me later. But I think for now we're just gonna keep it sort of simple and say input and output are both gonna be enums. Where are we using raw pointers here? Well, the reason I'm using raw pointers for help is because what else would I put in here? I don't wanna put the help itself because I still need to check whether my help has completed. So I need to retain a pointer to it. I could put an immutable reference there, but if this is an immutable reference, right, what is its lifetime? If it's lifetime is tick A, if it's lifetime was static, then we would have to leak every help. We could never free it, which is not okay. If it's just like a tick A, that tick A is gonna be this lifetime, but that's gonna differ for every operation. And so what is the lifetime of the help queue that holds many of these? There's no well-defined lifetime. So there's no statically known lifetime. And so that's why I'm making this a raw pointer. And the idea here with peak is that if we know that the pointer will only be freed after the thing has already been removed from the queue, then we know that if we peak that it'll still be valid. It's not quite true either, but yeah. The reason, technically, these will probably be something like guard of help, right? Where guard is something that ensures that the help won't go out of scope, that won't be dropped while we still have a handle, a reference to it. And this is where something like hazard pointers is gonna come into play. I think for now, we're just gonna have it be raw pointers. And I suppose, yeah, it could be non-null, technically. But I'm gonna have it be const now because ultimately this is not the real type it's gonna be. But you're right, it should be non-null given that we know that these are non-null. If input was a generic type rather than associated, we may be avoid the enum. So the problem here, right, if we did this, is that it would mean that you would have a, where's our little code down here. When you implement normalized lock free for lock free linked list, what you would end up with is multiple different implementations of the trait one for each input type, which means that you can't really construct this sort of thing that just holds a lock free linked list because it would have to also specify the input type, which is a little weird. Maybe we can have a second trait here where like, yeah, I'm not sure. There might be a way to express it. I think what I want to do here is start with having it just be the sort of enum construction and then see if we can make it more typesafe afterwards. The reason I want to do that is because I don't have a good sense for the actual code is going to look like here. So I don't know what the best way to represent it in a typesafe way will be. And so I think for now we're going to stick with it like this. The lifetime problem is not solved by existential lifetimes because the lifetimes are actually different. It's not just one lifetime. It's different lifetimes. They're distinct. They can't be RC because, well, basically because concurrent memory reclamation is hard, if it's an arc, then imagine that we try to remove the arc from the head of the linked list. At the same time, someone else reads the arc from the linked list. The reference count is still one until the person who peeked clones it and increments the reference count. But imagine they peek, we remove, we drop the thing we removed, the reference count now goes to zero. So we drop it and then the other threads gets to execute, which is after it peeked. So it still has the arc, but its reference count is now zero and it's been dropped. So it's illegal memory. So it can't increment the reference count. There's a race condition there. And this is why reference counting is actually, it's actually kind of hard to get reference counting to solve the concurrent memory reclamation problem. Not impossible, but it's not quite as straightforward as just making this be arc help, sadly. All right. Yeah, so I think we have like a sort of structure that represents at least kind of what we want or what we imagine this protocol or this algorithm to look like. So it's now, weak references have the same problem. Dropping the last weak reference drops the, there's still a heap allocation that holds the weak reference count. And so you end up racing on dropping that. It doesn't solve the problem, sadly. Weak references count would only help solve cycles. It doesn't help solve concurrent reference counting. Unfortunately. This is where you basically need something like hazard pointers. Okay. Oh, sorry. I should have warned that this is a bright screen. So now let's look at what the paper actually says for what this normalized structure looks like. And you see that this section specifies the sort of normalized structure. And then the, there's like a little bit later in the paper where they show, given a normalized lock free algorithm. So given some, in our terminology, given something that implements the trait, how do you simulate it in a wait-free manner automatically? Even if the peak clones, you have the same race, the race is just inside peak. A normalized lock free data structure is one for which each operation can be presented in three stages, such that the middle stage executes the owner CASs. The first is a preparatory stage and the last is a post-execution step. Using the linked list example, the delete operation runs a first stage that finds the location to mark a node as deleted while sniping out the list, out of the list all nodes were previously marked as deleted. By the end of the search, we can determine the main CAS operation, the one that marks the node as deleted. Yeah, so the pre for delete in this linked list is walk the list until you find the thing that you want to delete.  But these multiple threads can do them in parallel. There's no problem if it fails. It doesn't prevent you progress because it's not the main operation you care about. And ultimately you get to, okay, this is the node I'm actually going to delete. And then the CAS descriptor that you output is going to be mark this node as deleted, which is going to be a compare and swap. Now comes the middle stage where this CAS is executed, which logically deletes the node from the list. And then finally, in a post processing stage, we attempt to snip out the marked node from the list and make it unreachable from the list head. Right, so the post CAS operation is now that it's marked as deleted, try to actually remove it, like unlink the next pointer of the previous node to point to the next node. But that one, multiple threads can do in parallel too. That's not a problem because if they fail, it probably just means someone else did it already. And so that's not actually a challenge. The only problem is if multiple threads try to update a given node at the same time. All right, in a normalized lock-free data structure, we require that any access to the data structure is executed using a read or a CAS. The first and last stages must be parallelizable. That is they can be executed with parallelizable methods. And each of the CAS primitives of the second stage be protected by versioning. All right, so this versioning is something that's gonna come back to bite us later. It's like I have a, I know this from having read other bits that this will be a problem later, but we're gonna ignore it a little bit for now. Yeah, let's discuss more later. That's fine. Okay, so the idea is that the pre and post methods are gonna be executed in parallel by multiple threads, whereas the main CAS operation is not. A lock-free data structure is provided in a normalized representation if any modification of the shared memory is executed using a CAS. Every operation of the data structure consists of executing three methods, one after the other, and which have the following formats. There is a CAS generator, whose input is the operations input, and its output is a list of CAS descriptors. The CAS generator method may optionally output additional data to be used in the wrap-up method. Okay, so that sort of matches the prepare we had except they call it generator. And because it has to be executed in parallel, I assume that it's fine for it to take a reference to the input. It doesn't actually want to consume the input. It returns a list of CAS descriptors and may optionally output additional data to be used in the wrap-up method. So there's some like additional, right, where this returns this and additional. Now, at this point, I would probably simplify this a little and say that there's like an associated descriptor and we're gonna require that the descriptor implements a slice index of u-size. We're gonna say that this has to return self descriptor and exact size iterator. No, we don't care about that. Yeah. And I guess we're gonna have to use standard ops slice index. Is that not where it lives? So we're actually gonna just, all we really care about is that we can like look at the individual elements of this and maybe some notion of like a length maybe. And then this is gonna take a descriptor and this is also going to be given the descriptor performed. Something like this. So the implementation can choose what it's like descriptor representation is because all we care about is the fact that we know which like operations we can do inside of it that we can slice into it. And maybe something like the output of this has to be a CAS descriptor that we can execute. Not quite sure yet. They call this the executor and this the wrap-up. So let's call this wrap-up as well. This is sort of have a consistent phrasing. CAS executor which is a fixed method common to all data structure implementations. Okay, so CAS executor. Ah, so CAS executor is actually not a thing that is implemented by the algorithm. It's one that's provided. So we could have a default implementation but it sounds like we actually don't want this to even get overridden. It sounds like the CAS executor is actually something that is part of the simulation. Its input is a list of CAS descriptors output by the generator method. The CAS executor method attempts to execute the CAS' in its input one by one until the first one fails or until all CAS is complete. Its output is the index of the CAS that failed. All right, so and it says its output is the index of the CAS that failed which is minus one if none failed. That's our representation here. It's either a result where we succeeded or I guess this is a U size which is the index of the one that failed. So there we're kind of right except that it's not a property of the trait.  I guess to do is better. And it's going to take, what do they say, the list of CAS descriptors. So it's going to take the LF descriptor and it's gonna run them start to finish and return the first one that failed. So that's then not actually a part of the API. That's interesting. This is not a website, it's a PDF. So dark mode wouldn't help. And also I don't like dark mode. I only use it for streams. Yeah, Sly's index might not be right here especially now that the executor is a part of the simulator. I think we might actually want to have like a pubtrate CAS descriptor which has a LEN. So this is gonna, we're gonna require that this implements CAS descriptor. It's gonna have to implement, it's gonna have to be able to tell us the length. It's gonna have to be able to tell us the nth, which is, I mean, this is arguably like, maybe not Sly's index, it's just, maybe it's just index really. Like maybe what we really want here is just standard ops index. What's the definition actually of the index trait? The index trait. So we want where self as index use size output. In fact, I don't think that's even what we want. I think what we want is output equals CAS descriptor. So maybe this is descriptors. So this is CAS descriptors. And then there is a struct CAS descriptor which we don't really know what is yet. So what we require of whatever it uses as its descriptor of the operations is going to be like, we can find out how many there are and we can index into it to get CAS descriptors. And each CAS descriptor is then something that we can execute in the CAS executor. I already have the PDF open in the browser. I don't think dark mode readers change the PDF that gets rendered. Shouldn't CAS descriptor be the same for all implementations. I'm also sort of imagining that being the case. And in fact, that's sort of what we're saying, right? By saying that the CAS descriptor, like any individual descriptor is the same across all implementations. The reason I want this to be generic is because for like the linked list, there's only, you only want to execute one CAS as the commit operation. But there are other, like for the binary tree, I think they say, you actually need two CASs. And so by having this generic, we can actually have like when you implement normalized lock free for linked list, you can have type descriptor be just CAS descriptor, or if you will, this, right? But when you implement it for BST, you can have it be this. Does that make sense? So rather than us sort of dictating here that you're gonna use Tinyvec or something like that, the implementation can just say, for me, the descriptor is two descriptors. And I think that's a nice, nice way to be able to delegate that to the implementation to choose how it represents its collection of descriptors. So they say, back to the paper, the CAS executor method attempts to execute the CASs in its input one by one until the first one fails or until all CAS is complete. Okay, so the CAS executor is gonna do like Len is gonna be descriptors.len and then we're gonna do for i in zero to Len. I guess we're gonna do like we're gonna execute a CAS which means that we're gonna do a, I guess really what this means is that the CAS descriptor needs to hold like a reference to some kind of atomic. Let's say atomic pointer for now. See, this is where it gets weird, right? Because the descriptor might be the commit point for a given algorithm might be different. Like some might be changing an atomic pointer, some might be changing atomic Boolean, some might be changing something completely different. And so maybe it's weird. Maybe it really does need to be generic because the actual underlying descriptors is gonna be different. Now, so maybe CAS descriptor really needs to be a trait as well that has to like have an execute, I guess, and it's gonna return a result of nothing. And so here what we're gonna require is that where self as index use size output implements CAS descriptor, right? Where does this error come from? I will see about that later. So here, I guess we're gonna do something like if descriptors i.execute.isError, then we return error of i. Otherwise we return, okay. So that's sort of the CAS executor loop. And my guess is that here maybe we want to like record contention. Yeah, so the other reason why I want descriptor to be generic here is so that we can, the generator can generate arbitrarily complicated extra data that then gets passed to wrap up. That's a good point. What am I doing wrong here? I'm doing something silly. I guess this actually needs to be generic over the output type. I wish this was a, I guess really what we're saying is you might have a collection type that, like the collection type and the descriptor types are different. You could have two different users of this that use the same collection type with different descriptor types or you could have them use different descriptor types with the same, different collection type with the same descriptor type. And so therefore this needs to be generic over the descriptor. This is gonna be output equals D and this is gonna be D implements CAS descriptor. And see this is not pretty. I wish this didn't have to look like this. I think there are ways for us to clean this up. I'm just choosing to not do it quite yet because I still feel like there's still a lot of motion in these traits.  And so the idea is that for any given normalized lock free algorithm or data structure, it has an input type which is the operation you wanna do. It has an output type which is what those operations return. It has a CAS type which is what kind of CAS operations can it execute. And it has a CAS this operation which is a wrapper around those CAS types. So that is like, for example, an array of length one. And those are all sort of distinct types that are associated with the particular implementation we're using. Why does this complain? Because it needs to take CASs. Normalized lock free. Why is it complaining about this? Have I written something silly somewhere? I've definitely written something, oh, down here. Right, there's still a bunch we haven't, right. So this is gonna be generator. This is gonna be self.cas execute. And I guess that means CAS executor is also gonna take our contention measure, right? So our contention detected. Something like that. So now this does CAS execute. Does that know what we called it? Oh, CAS, let's make it CAS execute. Reads nicer. And so the generators should return CAS. See, CAS reads as cases which is its own kind of problem. I think this should take probably an immutable reference to that. We'll see how that's to rate it later. And then this should call wrap up with CASs, right? Because wrap up, let's have this be this too. Wrap up. All right, so now it's happy again. It could require an iterator instead of index and then the for loop run over the iterator. We could do that.  Yeah. You could also do with this could be, like there's a lend on exact size iterator. This just feels like the slightly nicer way. I understand your point. I honestly don't quite know yet. I think it depends on how helping ends up working. All right, so let's head back to the doc. Wrap up whose input is the output of the CAS executor method plus the list of CAS descriptor output by the CAS generator plus optionally any additional data output by the CAS generator method to be used by the wrap up method. Okay, so there's output from the CAS executor and the output from the CAS executor is the index of the CAS that failed. Oh, I see, so wrap up gets called regardless and it gets, so it also gets a sort of executed, which is gonna be the result use eyes. So it sort of gets the outcome of the execution. So wrap up runs regardless of whether we succeeded or not.