rust

Classical concurrent data structures such as FIFO queues are foundational in many different applications. It is very simple to implement such a queue by wrapping a sequential implementation in a mutex. However, lock-free designs are often preferred, as they can give better scalability and progress guarantees than ones relying on locks. The classic lock-free FIFO queue is the Michael-Scott queue (MS queue), which is a neat lock-free linked list. Lock-free designs are inherently tricky to implement, and linked lists are known to be troublesome in Rust, so this post details my journey of implementing this MS queue in Rust.

I don't think I will ever completely understand Rust lifetimes. Every time I think I get them, they come right back and hit me in the face. The other day I wanted to implement scoped variable bindings for my new programming language Zote, and it took me several hours to figure out why it did not work as I expected. So let's talk a bit about lifetimes, for both of our sakes.