287
We define concurrent in this context to be the method of organizing data structures
for access by multiple threads. Such data structures are intended for use in a parallel
computing environment when multiple threads can concurrently call methods of a data
structure without additional synchronization required.
C++ Standard Template Library (STL) data structures can be wrapped in a coarsegrained mutex to make them safe for concurrent access by letting only one thread
operate on the container at a time. However, that approach eliminates concurrency
and thereby restricts parallel speedup if implemented in performance-critical code.
Designing concurrent data structures is a challenging task. The difficulty increases
significantly when we need to develop concurrent data structures for persistent memory
and make them fault tolerant.
The pmem::obj::concurrent_map and pmem::obj::concurrent_hash_map structures
were inspired by the Intel Threading Building Blocks (Intel TBB),
1
which provides
implementations of these concurrent data structures designed for volatile memory. You
can read the Pro TBB: C++ Parallel Programming with Threading Building Blocks book
2
to get more information and learn how to use these concurrent data structures in your
application. The free electronic copy is available from Apress at https://www.apress.
com/gp/book/9781484243978.
There are three main methods in our concurrent associative data structures: find,
insert, and erase/delete. We describe each data structure with a focus on these three
methods.
Concurrent Ordered Map
The implementation of the concurrent ordered map for persistent memory
(pmem::obj::concurrent_map) is based on a concurrent skip list data structure. Intel
TBB supplies tbb::concurrent_map, which is designed for volatile memory that we use
as a baseline for a port to persistent memory. The concurrent skip list data structure
can be implemented as a lock-free algorithm. But Intel chose a provably correct
1
Intel Threading Building Blocks library (https://github.com/intel/tbb).
2
Michael Voss, Rafael Asenjo, James Reinders. C++ Parallel Programming with Threading Building
Blocks; Apress, 2019; ISBN-13 (electronic): 978-1-4842-4398-5; https://www.apress.com/gp/
book/9781484243978.
Chapter 14 ConCurrenCy and persistent MeMory
We define concurrent in this context to be the method of organizing data structures
for access by multiple threads. Such data structures are intended for use in a parallel
computing environment when multiple threads can concurrently call methods of a data
structure without additional synchronization required.
C++ Standard Template Library (STL) data structures can be wrapped in a coarsegrained mutex to make them safe for concurrent access by letting only one thread
operate on the container at a time. However, that approach eliminates concurrency
and thereby restricts parallel speedup if implemented in performance-critical code.
Designing concurrent data structures is a challenging task. The difficulty increases
significantly when we need to develop concurrent data structures for persistent memory
and make them fault tolerant.
The pmem::obj::concurrent_map and pmem::obj::concurrent_hash_map structures
were inspired by the Intel Threading Building Blocks (Intel TBB),
1
which provides
implementations of these concurrent data structures designed for volatile memory. You
can read the Pro TBB: C++ Parallel Programming with Threading Building Blocks book
2
to get more information and learn how to use these concurrent data structures in your
application. The free electronic copy is available from Apress at https://www.apress.
com/gp/book/9781484243978.
There are three main methods in our concurrent associative data structures: find,
insert, and erase/delete. We describe each data structure with a focus on these three
methods.
Concurrent Ordered Map
The implementation of the concurrent ordered map for persistent memory
(pmem::obj::concurrent_map) is based on a concurrent skip list data structure. Intel
TBB supplies tbb::concurrent_map, which is designed for volatile memory that we use
as a baseline for a port to persistent memory. The concurrent skip list data structure
can be implemented as a lock-free algorithm. But Intel chose a provably correct
1
Intel Threading Building Blocks library (https://github.com/intel/tbb).
2
Michael Voss, Rafael Asenjo, James Reinders. C++ Parallel Programming with Threading Building
Blocks; Apress, 2019; ISBN-13 (electronic): 978-1-4842-4398-5; https://www.apress.com/gp/
book/9781484243978.
Chapter 14 ConCurrenCy and persistent MeMory