This branch has a long history. About two years ago I wrote a patch to
remove the mutex from shamap inner nodes (ref:
https://github.com/seelabs/rippled/tree/lockfree-tagged-cache). At the
time I measured a large memory savings of about 2 gig. Unfortunately,
the code required using the `folly` library, and I was hesitant to
introduce such a large dependency into rippled (especially one that was
so hard to build). This branch resurrects that old work and removes the
`folly` dependency.
The old branch used a lockless atomic shared pointer. This new branch
introduces a intrusive pointer type. Unlike boost's intrusive pointer,
this intrusive pointer can handle both strong and weak pointers (needed
for the tagged cache). Since this is an intrusive pointer type, in order
to support weak pointers, the object is not destroyed when the strong
count goes to zero. Instead, it is "partially destroyed" (for example,
inner nodes will reset their children). This intrusive pointer takes
16-bits for the strong count and 14-bits for the weak count, and takes
one 64-bit pointer to point at the object. This is much smaller than a
std::shared_pointer, which needs a control block to hold the strong and
weak counts (and potentially other objects), as well as an extra pointer
to point at the control block.
The intrusive shared pointer can be modified to support for atomic
operations (there is a branch that adds this support). These atomic
operations can be used instead of the lock when changing inner node
pointers in the shamap.
Note: The space savings is independent from removing the locks from
shamap inner node. Therefor this work is divided into two phases. In the
first phase a non-atomic intrusive pointer is introduced and the locks
are kept. In a second phases the atomic intrusive pointer could be
introduced and the locks will be removed. Some of the code in this patch
is written with the upcoming atomic work in mind (for example, using
exchange in places). The atomic intrusive pointer also requires the C++
library to support `atomic_ref`. Both gcc and msvc support this, but at
the time of this writing clang's library does not.
Note: Intrusive pointer will be 12 bytes. The shared_ptr will be around
40 bytes, depending on implementation.
When measuring memory usage on a validator, this patch resulted in
between a 10 and 15% memory savings.
From https://github.com/XRPLF/rippled/pull/4815 Seelabs: