The Benefits and Limitations of Rust for Implementing Concurrent Data Structures - Comparing Concurrent Skip Lists in Rust to C

Abstract

The Rust programming language has become increasingly relevant to the software industry for its memory safety and performance, especially since memory safety issues have been seen as a prevalent source of security vulnerabilities in recent years. Rust has also been praised for its "Fearless Concurrency", with concurrency being essential for achieving better performance in modern computers. The "Fearless Concurrency" of Rust has been shown to primarily help with regular parallelism as opposed to the parallelism needed by complex concurrent data structures with intricate access patterns. This leaves many open questions of how Rust handles these access patterns. This thesis will investigate the validity of the claims of "Fearless Concurrency" in Rust for implementing complex concurrent data structures, and see how this compares to languages like C. In particular, skip lists will be investigated since they are important for many concurrent systems and make use of many intricate concurrent programming techniques.

We implemented several state-of-the-art skip lists in Rust, and created a comprehensive benchmarking framework used for comparing our implementations against existing Rust and C implementations. We also qualitatively analysed the experience of implementing performant concurrent data structures in Rust. Our findings show that skip lists in Rust performed comparably well to those in C and sometimes even outperforming them depending on workload. We also found that many of the existing implementations in Rust had problems or did not work. Lastly, while Rust provides many safety guarantees, Unsafe Rust may be needed for many complex concurrent data structures limiting these guarantees such as in our lock-free skip list implementations. In these cases, the safety guarantees of Rust are not applicable to the entire application, but rather for the parts of the application where safe Rust is used.