Lock-Free to Wait-Free Simulation in Rust (part 2)

Channel:
United States Jon Gjengset
Subscribers:
97,800
Published on ● Video Link: https://www.youtube.com/watch?v=tNzCj8691LE


Duration: 5:24:49
10,777 views
217

In this stream, we continue implementing the concurrency algorithm from the academic paper "A Practical Wait-Free Simulation for Lock-Free Data Structures" by Erez Petrank and and Shahar Timnat in Rust. The paper details a general way to turn lock-free concurrent data-structures into wait-free ones (we also talk about what that means), and you can find it at http://cs.technion.ac.il/~erez/Papers/wf-simulation-full.pdf.

0:00:00 Introduction
0:01:18 Rust for Rustaceans
0:02:54 Code Recap
0:12:03 Naming the CAS list type
0:33:05 Versioned CASes
2:05:38 ExecuteCASes
2:09:46 Cat interlude
2:10:52 Paper vs. Code
2:20:03 Contention detection
2:36:22 It compiles!
2:36:40 PostCASes
2:50:45 Intermission
2:53:11 Paper vs. Code
2:56:06 Tidying Up Nested Result
2:59:46 The Wait-Free Queue
3:04:35 Per-Thread Handles
3:35:45 Porting the Queue
3:54:40 Weird Head Semantics
4:16:56 Pop and Push
4:32:40 Implementing Helping
5:15:37 State of Affairs and Next Steps

You can find the current code at https://github.com/jonhoo/bystander.

Live version with chat: https://www.youtube.com/watch?v=OqnZpVufTtg.



Other Videos By Jon Gjengset


2022-06-19Day in the Life of Open Source Maintenance 2022-06-19
2022-06-11Post-Crust of Rust Q&A
2022-06-11Crust of Rust: Send, Sync, and their implementors
2022-03-05Implementing and Optimizing a Wordle Solver in Rust
2022-01-15Implementing Hazard Pointers in Rust (part 4/4)
2021-10-31Implementing Hazard Pointers in Rust (part 3)
2021-10-08Crust of Rust: Functions, Closures, and Their Traits
2021-08-31Crust of Rust: async/await
2021-07-10Implementing Hazard Pointers in Rust (part 2)
2021-06-26Implementing Hazard Pointers in Rust
2021-06-13Lock-Free to Wait-Free Simulation in Rust (part 2)
2021-05-22Lock-Free to Wait-Free Simulation in Rust
2021-04-30Crust of Rust: Dispatch and Fat Pointers
2021-04-02Crust of Rust: Atomics and Memory Ordering
2021-03-13Crust of Rust: The Drop Check
2021-02-20Crust of Rust: Subtyping and Variance
2021-01-23Q&A January 2021 (now with cat)
2020-12-12The Unsafe Chronicles: Exhibit A: Aliasing Boxes
2020-11-21A Cool Generic Concurrency Primitive in Rust
2020-11-14Crust of Rust: Sorting Algorithms
2020-10-23Thesis: Partial State in Dataflow-Based Materialized Views


Tags:
rust
live-coding
wait-free
lock-free
data structures
concurrency