MSpec: A design pattern for concurrent data structures

摘要: Speculation is a well-known means of increasing parallelism among concurrent methods that are usually but not always independent. Traditional nonblocking data structures employ a particularly restrictive form of speculation. Software transactional memory (STM) systems employ a much more general—though typically blocking—form, and there is a wealth of options in between.We explore data-structure-specific speculation as a design pattern for concurrent data structures. Using several different structures as examples, we consider issues of safety (sandboxing), validation mechanism, and granularity of locking. We note that it can sometimes be useful to perform validation and locking at different granularities. Through experiments on UltraSPARC and x86 platforms, we demonstrate that MSpec can lead to highly efficient algorithms, particularly in methods with a significant search component.