Recent work has shown how to augment any CAS-based concurrent data structure to support taking a snapshot of the current memory state. Taking the snapshot, as well as loads and CAS (Compare and Swap) operations, take constant time. Importantly, such snapshotting can used to easily implement linearized queries over any part of a data structure, such as range queries.

In this paper we make two significant improvements over this and similar approaches. The first improvement, which we refer to as indirection-on-need, removes a subtle and hard to reason about restriction on how pointers are used that is needed to avoid a level of indirection. Using our approach indirection is almost always avoided and with no restrictions. The second improvement is to efficiently support snapshotting with lock-free locks. This requires supporting an idempotent CAS. We show a particularly simple solution to the problem that leverages the snapshotting data structures.

Based on these ideas we implemented an easy to use C++ library, VERLIB, centered around a versioned pointer type. The library works with lock (standard or lock-free) and CAS based algorithms, or any combination. Converting existing concurrent data-structures to use the library takes minimal effort. We present results of experiments that use VERLIB to convert state-of-the-art data structures for ordered maps (a b-tree), radix-ordered maps (an art-tree), and unordered maps (an optimized hash table) to be snapshottable. The snapshottable versions perform almost as well as the original versions and far outperform any previous implementations that support atomic range queries.