A library for high-performance reference-counted pointers for automatic memory management.
This library is part of the following research project. If you use it for scientific purposes, please cite it as follows:
Concurrent Deferred Reference Counting with Constant-Time Overhead
Daniel Anderson, Guy E. Blelloch, Yuanhao Wei
The 42nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2021), 2021
To work with the tests and benchmarks, you will need a recent version of CMake. To use the library on its own, you can
simply include the include
directory. The library is header only and has no other dependencies. Our types are provided inside the namespace cdrc
.
You'll need a compiler that supports at least C++17. Some of our tests and benchmarks require C++20, but the library
itself should work with just C++17.
Our library provides three types that work similarly to C++'s standard shared_ptr
and atomic<shared_ptr>
. These types, and some of their important supported methods are:
- atomic_rc_ptr:
atomic_rc_ptr<T>
is closely modelled after C++โsatomic<shared_ptr<T>>
. It provides support for all of the standard operations, such as atomic load, store, exchange and CAS.load()
. Atomically creates anrc_ptr
to the currently managed object, returning the rc_ptrget_snapshot()
. Atomically creates asnapshot_ptr
to the currently managed object, returning thesnapshot_ptr
.store(desired)
. Atomically replaces the currently managed pointer with desired, which may be either anrc_ptr
or asnapshot_ptr
.compare_and_swap(expected, desired)
. Atomically compares the managed pointer with expected, and if they are equal, replaces the managed pointer with desired. The types of expected and desired may be eitherrc_ptr
orsnapshot_ptr
, and need not be the same. Ifdesired
is passed in as an r-value reference, then it is only moved from if the compare_and_swap succeeds.compare_exchange_weak(expected, desired)
. Same ascompare_and_swap
but, if the managed pointer is not equal to expected, loads the currently managed pointer into expected. This operation may spuriously return false, i.e. it is possible that the value of expected does not change
- rc_ptr: The
rc_ptr
type is closely modelled after C++โs standard libraryshared_ptr
. It supports all pointer-like operations, such as dereferencing, i.e. obtaining a reference to the underlying managed object, and assignment of anotherrc_ptr
to replace the current one. It is safe to read/copy anrc_ptr
concurrently from many threads, as long as there is never a race between one thread updating therc_ptr
and another reading it. Such a situation should be handled by anatomic_rc_ptr
. - snapshot_ptr: The
snapshot_ptr
type supports all of the same operations asrc_ptr
, except thatsnapshot_ptr
can only be moved and not copied. Additionally, whilerc_ptr
can safely be shared between threads,snapshot_ptr
should only be used locally by the thread that created it. The use ofsnapshot_ptr
should result in better performance thanrc_ptr
provided that each thread does not hold too manysnapshot_ptr
at once. Therefore,snapshot_ptr
is ideal for reading short-lived local references, for example, reading nodes in a data structure while traversing it.
These types are provided in the correspondingly named header files: <cdrc/atomic_rc_ptr.h>
, <cdrc/rc_ptr.h>
, and <cdrc/snapshot_ptr.h>
.
To allocate a new reference-counted object mananged by an rc_ptr
, use the static method rc_ptr<T>::make_shared(args...)
in the same way as the standard C++ std::make_shared
. Alternatively, the convenient aliases cdrc::make_rc<T>(args...)
and cdrc::make_shared<T>(args...)
can be used.
As a simple example, the following code implements a concurrent stack using our library. You can read a complete implementation in stack.h in the examples directory.
struct Node { T t; rc_ptr<Node> next; }
atomic_rc_ptr<Node> head;
void push_front(T t) {
rc_ptr<Node> p = make_rc<Node>(t, head.load());
while (!head.compare_exchange_weak(p->next, p)) {}
}
std::optional<T> pop_front() {
snapshot_ptr<Node> p = head.get_snapshot();
while (p != nullptr && !head.compare_exchange_weak(p, p->next)) { }
if (p != nullptr) return {p->t};
else return {};
}
The head node of the
stack is stored in an atomic_rc_ptr
because it may be modified and read concurrently by multiple threads. Each node
of the stack stores its next pointer as a non-atomic rc_ptr
.
This is safe, because although multiple threads may read the
same pointer concurrently, the internal nodes of the stack
are never modified, only the head is. Lastly, we can use a
snapshot_ptr
while performing pop_front
, since reading the
head is a short-lived local reference that will never be shared
with another thread.
To support writing advanced data structures, we also support marked pointers. Marked pointers allow you to utilize some of the redundant bits of the pointer representation to store flags, avoiding the need to store flags adjacent to the pointer and having to use double-word instructions to read/write the pointer/flag pair atomically. To use marked pointers, the types marked_arc_ptr
, marked_rc_ptr
, and marked_snapshot_ptr
can be used as substitutes for atomic_rc_ptr
, rc_ptr
, and snapshot_ptr
respectively. You can include them from the header <cdrc/marked_arc_ptr.h>
They support all of the same methods, but additionally support:
get_mark()
. Gets the current mark on the pointer.set_mark(mark)
. Sets the current mark on the pointer. The mark must be an unsigned integer at most 3, i.e., use only the bottom two bits.
Like regular rc_ptr
, to create a new reference-counted object managed by a marked_rc_ptr
, use marked_rc_ptr<T>::make_shared(args...)
.
As expected, the load
method of marked_arc_ptr
returns a marked_rc_ptr
, and the get_snapshot
method returns a marked_snapshot_ptr
. The get
method of marked_rc_ptr
and marked_snapshot_ptr
returns returns a raw pointer without the mark, and hence can be safely dereferenced.
Lastly, the marked_arc_ptr
type also supports these additional operations:
compare_and_set_mark(expected, desired_mark)
. Atomically compares the current marked pointer with expected (which should be amarked_rc_ptr
or amarked_snapshot_ptr
), and, if they are equal, sets the mark todesired_mark
and returns true. Otherwise returns false.set_mark_bit(bit)
. Atomically sets the value of the bit at the given position (must be 1 or 2) to 1get_mark_bit(bit)
. Returns the value of the mark bit at the given position (must be 1 or 2)
An example of how to use these marked pointers can be found in linked_list.h in the examples directory.
To configure the project for testing and benchmarking, create a build directory and run cmake. This is as easy as
mkdir build
cd build
cmake ..
make
This will build both the benchmarks and the tests. By default, the CMake project will build in Release mode. You probably want to do a Debug build for testing, by adding -DCMAKE_BUILD_TYPE=Debug
to the CMake configuration command. The tests can then be run by writing make test
from the build directory. These will validate that the code is functioning sensibly. See benchmarks for information on running the provided benchmarks.