The Future(s) of Shared Data Structures.

The Future(s) of Shared Data Structures.

Alex Kogan, Maurice Herlihy

15 July 2014

This paper considers how to use futures, a well-known mechanism to manage parallel computations, to improve the performance of long-lived, mutable shared data structures in large-scale multicore systems. We show that futures can enable type-speci c optimizations such as combining and elimination, improve cache locality and reduce contention. To exploit these bene ts in an e ective way, however, it is important to de ne clear notions of correctness. We propose new extensions to linearizability appropriate for method calls that return futures as results. To illustrate the utility and trade-o s of these extensions, we describe implementations of three common data structures: stacks, queues, and linked lists, designed to exploit futures. Our experimental results show that optimizations enabled by futures lead to substantial performance improvements, in some cases up to two orders of magnitude, compared to well-known lock-free alternatives.


Venue : PODC 2014