A new WG21 paper is available. A copy is linked below, and the paper will also appear in the next normal WG21 mailing. If you are not a committee member, please use the comments section below or the std-proposals forum for public discussion.

Document number: N4037

Date: 2014-02-14

Non-Transactional Implementation of Atomic Tree Move

by Paul E. McKenney

Excerpt:

1 Introduction

Concurrent search trees are well understood [9, 2], as are concurrent search trees that use lightweight read-side synchronizations mechanisms [10, 11, 17, 16, 7, 1, 8] such as read-copy update (RCU) [14, 12].

However, non-transactional-memory-based algorithms that atomically move an element from one search tree to another, while avoiding delaying lockless readers, are lacking. Such algorithms are known for hash tables [18, 19]. A challenge to find such an algorithm for trees was put forward at the 2014 C++ Standards Committee meeting at Issaquah, WA USA, and this document describes one solution. As such, it is a work in progress: Future work will implement multiple solutions and compare their performance and scalability. ...

6 Summary

This paper has demonstrated a prototype solution to the Issaquah challenge of atomically moving data between two search trees without unnecessary contention.

Future work includes efficiently balancing the trees, evaluating other non-TM implementations, and comparing against TM implementations.