This is a custom allocator for node based containers, as described in #16718 (comment). Hopefully, this is a less controversial change and easier to review than #16718.
The allocator retains memory of nodes, and allocates them in bulk. In my benchmarks, using this pool allocator for CCoinsMap gives about 16% faster -reindex-chainstate, and decreases memory usage by ~8%. The allocator is potentially useful for all node-based containers like std::list, std::map, std::unordered_map, etc. I believe this is especially useful on systems where malloc() and free() are relatively expensive operations, since this allocator will dramatically reduce these calls.
Some noteworthy properties about this allocator:
-
It relies on the fact that node based containers allocate nodes one at a time. If a container doesn’t behave like this, the allocator will still work but won’t be any faster.
-
The allocator determines the size of the nodes, which will then be used throughout the pool, by the first call to allocate(1). So if the container would not allocate something with the size of a node in its first call to allocate(1), the pool won’t be usable for nodes since it was set up with a different size. With C++17 it would be possible to use a containers type
node_typeto correctly initialize the pool’s size, but for now we have to rely on this heuristic. -
Copying / moving / swapping a map propagates the allocator. So if two different pools are used for two containers a and b, calling
a = bwill from now on use b’s pool in a. -
The pool is not threadsafe. Two containers which use the same pool in different threads won’t work.
-
A pool’s memory is only actually destroyed in the pool’s destructor.
I’ve added a benchmark to compare std::map, std::unordered_map with and without the pool allocator for the CCoinsMap.
