A Contention-Friendly Methodology for Search Structures

In this paper, a new methodology for writing concurrent data structures is proposed. This methodology limits the high contention induced by today's mutlicore environments to come up with efficient alternatives to most widely used search structures, including skip lists, binary search trees and hash tables. Data structures are generally constrained to guarantee a big-oh step complexity even in the presence of concurrency. By contrast our methodology guarantees the big-oh complexity only in the absence of contention and limits the contention when concurrency appears. The key concept lies in dividing update operations within an eager abstract access that returns rapidly for efficiency reason and a lazy structural adaptation that may be postponed to diminish contention. We illustrate our methodology with three contention-friendly data structures: a lock based skip list and binary search tree, and a lock-free hash table. Our evaluation clearly shows that our contention-friendly data structures are more efficient than their non-contention-friendly counterparts. In particular, our lockbased skip list is up to 1:3 faster than the Java concurrent skip list, our lock-based tree is up to 2:2 faster than the most recent concurrent tree algorithm we are aware of, and our lock-free hash table outperforms by up to 1:2 the Java concurrent hash table. We also present contention-friendly versions of the skip list and binary search tree using transactional memory. Even though our transaction-based data structures are substantially slower than our lock-based ones, they inherit compositionality from transactional memory and outperform their non-contention-friendly counterparts by 1:5 on average.Ce rapport présente une approche méthodologique pour les structures de recherche concurrentes avec des applcations aux listes á saut (skip list), arbres et table de hachage (hash table)