Applicative 2016 / Speakers

Paul McKenney


High-Performance and Scalable Updates: The Issaquah Challenge

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.


Paul E. McKenney has been coding for almost four decades, more than half of that on parallel hardware, where his work has earned him a reputation among some as a flaming heretic. Over the past decade, Paul has been an IBM Distinguished Engineer at the IBM Linux Technology Center. Paul maintains the RCU implementation within the Linux kernel, where the variety of workloads present highly entertaining performance, scalability, real-time response, and energy-efficiency challenges. Prior to that, he worked on the DYNIX/ptx kernel at Sequent, and prior to that on packet-radio and Internet protocols (but long before it was polite to mention Internet at cocktail parties), system administration, business applications, and real-time systems. His hobbies include what passes for running at his age along with the usual house-wife-and-kids habit.

Twitter: @paulmckrcu

© 2016 ACM.