Saturation in Lock-Based Concurrent Data Structures

For over three decades, computer scientists enjoyed a "free lunch" inasmuch as they could depend on processor speeds doubling every three years. This all came to an end in the mid-2000's, when manufacturers ceased increasing processor speeds and instead focused on designing processors with multiple independent execution units on each chip. The demands for ever increasing performance continue to grow in this era of multicore and manycore processors. One way to satisfy this demand is to continue developing efficient data structures which permit multiple concurrent readers and writers while guaranteeing correct behavior.

Concurrent data structures synchronize via either locks or atomic read-modify-write instructions (such as Compare-and-Swap). Lock-based data structures are typically less challenging to design, but lock-free data structures can provide stronger progress guarantees.

We first develop two variants of existing lock-based concurrent data structures, a linked list and a skiplist. We demonstrate how we can {\em unroll} these data structures to support multiple keys per node. This substantially improves the performance in these data structures when compared to other similar data structures. We next demonstrate how lock-based data structures can {\em saturate}, or plateau in performance, at sufficiently high thread counts, dependent upon the percentage of write operations applied to that data structure. We then discuss how we can apply a new technique involving {\em group mutual exclusion} to provide a lock-based data structure which is resilient to saturation. We then demonstrate how this technique can be applied to our implementations of linked lists and skiplists to provide scalable performance to 250 threads and beyond.

Our implementations provide excellent throughput for a wide variety of workloads, outperforming many similar lock-based and lock-free data structures. We further discuss how these techniques might apply to other data structures and provide several avenues for future research.