CppCon 2016: D. Dechev & D. Zhang “High Performance C++ Concurrent Transactional Data Structures"

http://CppCon.org — Presentation Slides, PDFs, Source Code and other presenter materials are available at: https://github.com/cppcon/cppcon2016 — In the session, we will discuss two strategies for implementing scalable transactional data structures using both locks and lock-free synchronizations. The locking strategy employs MRLock, which is a novel shared-memory resource allocation lock for multi-core processors. It uses a lock-free FIFO queue to manage locking requests in batches, which minimizes memory contention among threads. It is fast and designed as a drop-in replacement for the two-phase locking methods in C++11 and Boost library (std::lock() and boost::lock()). When combined with existing lock-based transaction synchronization techniques such as semantic locking and transaction boosting, it can be used by programmers who prefer lock-based code to implement high-performance transactional data structures on familiar grounds. The lock-free strategy is based on lock-free transactional transformation (LFTT), which uses transaction descriptor object to announce the transaction globally so that delayed threads can be helped. It is applicable to linked data structures such as linked lists and skip lists. The logical status of any node in the data structure depends on the status of the transaction descriptor that was embedded in it. Conflict transactions do not need to revert their operations as required in some of the existing methodologies. We will demonstrate the application of this strategy to existing lock-free lists and skip lists. We will also introduce a lock-free logarithmic search data structure based on multi-dimensional linked list. This brand new data structure is designed from ground up to achieve full potential for concurrent accesses. It has a distributed memory layout which alleviates contention. Write operations modify at most two nodes so interference among operations are brought down to a minimum. This data structure implements the collection/dictionary abstract data type, which is ubiquitous in modern applications. When combined with the above mentioned transactional strategies, this work could greatly benefit application developers who deal with data intensive scenarios such as in memory databases. Preliminary version of source code can be accessed from https://ucf-cs.github.io/tlds/. The research work mentioned in this presentation can be accessed from http://cse.eecs.ucf.edu/bios/delizhang.html. — Damian Dechev Associate Professor, University of Central Florida Dr. Damian Dechev is an Assistant Professor at the EECS Department at the University of Central Florida and the founder of the Computer Software Engineering - Scalable and Secure Systems Lab at UCF. He specializes in the design of scalable multiprocessor data structures and algorithms and has applied them in the design of real-time embedded space systems at NASA JPL and the HPC data-intensive applications at Sandia National Labs. Deli Zhang Software Development Engineer, Microsoft Deli Zhang received his Ph.D. in Computer Science at the University of Central Florida. He worked as a research assistant under the guidance of Dr. Damian Dechev. Deli specializes in developing non-blocking data structures and algorithms, applying non-blocking synchronization in existing performance critical applications. He has also collaborated with Sandia National Laboratory on large scale performance monitoring and simulation analysis. — Videos Filmed & Edited by Bash Films: http://www.BashFilms.com Work at Hudson River Trading (HRT): https://tinyurl.com/safxfctf