High-Performance and Scalable Updates:  The Issaquah Challenge
Channel: Linux.conf.au 2015 -- Auckland, New Zealand
Date: 16/01/2015

Paul McKenney
http://lca2015.linux.org.au/schedule/30142/view_talk
Highly performant and scalable techniques such as RCU have been quite successful in read-mostly situations.  However, there do come times when updates are necessary.   It would be convenient if there was some general update-side counterpart to RCU, but sadly there is not yet any such thing.  Nevertheless, there are a number of specialized update-side techniques whose performance and scalability rival that of RCU.  This talk will discuss several of them and provide an outlook into the future of low-overhead scalable updates.

One technique is the solution to the Issaquah Challenge, which was put forward at the C++ standards committee meeting in early 2014 at Issaquah, WA, USA.  This challenge requires a performant and scalable technique to atomically move elements back and forth between a pair of search trees, but without using transactional memory.  This talk will give an overview of a solution to a more general problem, that of atomically moving groups of elements among a group of several different types of linked data structures, while still permitting lockless searches before, during, and after this atomic move.