We present a code transformation for concurrent data struc- tures, which increases their scalability without sacrificing correctness. Our transformation takes lock-based code and replaces some of the lock- ing steps therein with optimistic synchronization in order to reduce con- tention. The main idea is to have each operation perform an optimistic traversal of the data structure as long as no shared memory locations are updated, and then proceed with pessimistic code. The transformed code inherits essential properties of the original one, including linearizability, serializability, and deadlock freedom.
Our work complements existing pessimistic transformations that make sequential code thread-safe by adding locks. In essence, we provide a way to optimize such transformations by reducing synchronization bot- tlenecks (for example, locking the root of a tree). The resulting code scales well and significantly outperforms pessimistic approaches. We fur- ther compare our synthesized code to state-of-the-art data structures implemented by experts. We find that its performance is comparable to that achieved by the custom-tailored implementations. Our work thus shows the promise that automated approaches bear for overcoming the difficulty involved in manually hand-crafting concurrent data structures.
mobile