CppCon 2016: “A lock-free concurrency toolkit for deferred reclamation and optimistic speculation'

—
—
Paul E. McKenney, Maged Michael, & Michael Wong

This talk introduces the concept of a Concurrency Toolkit that contains the proposed lock-free algorithms on Hazard Pointers and Read-Copy_Update and analyzes their motivation, while showing where they can be useful and their performance differences.
Under optimistic concurrency, threads may use shared resources concurrently with other threads that may make such resources unavailable for further use. Care must be taken to reclaim such resources only after it is guaranteed that no threads are concurrently using them or will subsequently use them.

More specifically, concurrent dynamic data structures that employ optimistic concurrency allow threads to access dynamic objects concurrently with threads that may remove such objects. Without proper precautions, it is generally unsafe to reclaim the removed objects, as they may yet be accessed by threads that hold references to them. Solutions for the safe reclamation problem can also be used to prevent the ABA problem, a common problem under optimistic concurrency.

There are several methods for safe deferred reclamation. The main methods are garbage collection, reference counting, RCU (read-copy-update), and hazard pointers. Each method has its pros and cons and none of the methods provides the best features in all cases. Therefore, it is desirable to offer users the opportunity to choose the most suitable methods for their use cases.

This talk will show why we are considering their inclusion (with the exception of garbage collection) in future C++ Standards under SG14/SG1 into the Concurrency TS.
—
Paul E. McKenney
IBM Linux Technology Center
Distinguished Engineer
Hillsboro, OR, USA
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.

Maged Michael
Facebook
New York
Maged Michael is a software engineer at Facebook. He is the inventor of hazard pointers, lock-free malloc and several algorithms for concurrent data structures. His work is included in several IBM products where he was a Research Staff Member at the IBM T.J. Watson Research Center. He received a Ph.D. in computer science from the University of Rochester. He is an ACM Distinguished Scientist and an ACM Distinguished Speaker. He is an elected member of the Connecticut Academy of Science and Engineering. He received the 2014 ACM SIGPLAN Most Influential PLDI Paper Award for his paper on Scalable Lock-Free Dynamic Memory Allocation.

Michael Wong
Codeplay Software/ISOCPP
VP of R&D/Director
Michael Wong is the CEO of OpenMP. He is the Canadian representative to the C++ Standard and OpenMP Committee. He is also a Director of ISOCPP.org and a VP, Vice-Chair of Programming Languages for Canada’s Standard Council. He has so many titles, it’s a wonder he can get anything done.
He chairs the WG21 SG5 Transactional Memory and SG14 Games Development/Low Latency, and is the co-author of a number C++11/OpenMP/Transactional Memory features including generalized attributes, user-defined literals, inheriting constructors, weakly ordered memory models, and explicit conversion operators. Having been the past C++ team lead to IBM’s XL C++ compiler means he has been messing around with designing C++ compilers for twenty years. His current research interest, i.e. what he would like to do if he had time is in the area of parallel programming, transactional memory, C++ benchmark performance, object model, generic programming and template metaprogramming. He holds a B.Sc from University of Toronto, and a Masters in Mathematics from University of Waterloo.

He has been asked to speak at ACCU, C++Now, Meeting C++, ADC++, CASCON, Bloomberg, CERN, and many Universities, research centers and companies.
—

*-----*
*-----*

[dosomething]

8:15 typo. should be - “...&p, p->next));”