A Vector Implementation Based On RRB-Tree for Rust

Abstract

Rust is a multi-paradigm system programming language focused on performance and reliability. Its rich type system offers memory and thread-safety guarantees at compile-time. Therefore, Rust forbids simultaneous sharing and mutation that sometimes is a necessary and useful pattern. A way to mitigate this limitation in Rust is to clone a value before sharing it. Naive cloning by copying, however, is an expensive operation both in terms of memory and performance. This thesis presents pvecrs, a project that contributes a vector implementation with efficient clone operation that borrows ideas from persistent data structures. The project explores novel approaches to optimize the vector's performance by leveraging Rust's ownership and borrowing rules, as well as aiming to provide a convenient, idiomatic interface familiar to developers. The proposed optimizations are evaluated and discussed based on the results of sequential and parallel test suites.