  Correct concurrent programs are difficult to write; when multiple threads
mutate shared data, they may lose writes, corrupt data, or produce erratic
program behavior. While many of the data-race issues with concurrency can be
avoided by the placing of locks throughout the code, these often serialize
program execution, and can significantly slow down performance-critical
applications. Programmers also make mistakes, and often forget locks in
less-executed code paths, which leads to programs that misbehave only in rare
situations.
  Rust is a recent programming language from Mozilla that attempts to solve
these intertwined issues by detecting data-races at compile time. Rust's type
system encodes a data-structure's ability to be shared between threads in the
type system, which in turn allows the compiler to reject programs where threads
directly mutate shared state without locks or other protection mechanisms. In
this work, we examine how this aspect of Rust's type system impacts the
development and refinement of a concurrent data structure, as well as its
ability to adapt to situations where correctness is guaranteed by lower-level
invariants (e.g., in lock-free algorithms) that are not directly expressible in
the type system itself. We detail the implementation of a concurrent lock-free
hashmap in order to describe these traits of the Rust language. Our code is
publicly available at https://github.com/saligrama/concache and is one of the
fastest concurrent hashmaps for the Rust language, which leads to mitigating
bottlenecks in concurrent programs.
