Concept ACK

The numbers look very promising!

Seems like this could be one of those rare optimization opportunities actually worth pursuing :)

I'm curious what the impact would be on the performance if you allocated N chunks at a time, always, to fill a page.

E.g., if you want to allocate one node, always allocate something like aligned_alloc(sysconf(_SC_PAGESIZE), size) and divide it up into a bunch of pointers for the free list.

Cool properties of doing so: Better cache alignment on items added around the same time, fewer things to keep in the allocated chunks list, if you were to sort the list by pointer (perhaps lazily, when we're not doing anything else) you would get something with good cache alignment again.

I'm curious what the impact would be on the performance if you allocated N chunks at a time, always, to fill a page.

I've run the benchmark with ::aligned_alloc(sysconf(_SC_PAGESIZE), ...); and only allocating a single page, and at least in the benchmark there's no difference:

Do you have specific code for that? The changes sounded a bit more complex than just aligning the allocator. Did you divide the allocation into N free list chunks? Or just over-allocate?

Do you have specific code for that? The changes sounded a bit more complex than just aligning the allocator. Did you divide the allocation into N free list chunks? Or just over-allocate?

MemoryResource::AllocateNewBlock is the only place where I actually malloc a new block that's divided into the chunks. Here I've replaced the ::operator new(num_chunks* m_chunk_size_bytes) with ::alligned_alloc(sysconf(_SC_PAGESIZE), num_chunks* m_chunk_size_bytes). And use free in ~MemoryResource.
I also changed the default allocation size m_block_size_bytes from 262144 to sysconf(_SC_PAGESIZE).

So for node size of 104 bytes and page size 4096, this should allocate a page-alligned block with 39*104=4056 bytes.

Some fresh benches in (high dbcache). Continuing to see fairly substantial time/memory improvements with this change.

commands index

#22702 vs. $mergebase (absolute)

#22702 vs. $mergebase (relative)

Thanks for the benchmark! Good to see its 8.4% faster. I think the only reason the memory is lower is because the memusage::DynamicUsage now overestimates the memory requirements of the std::unordered_map that uses the node_allocator. I guess I should correct that. Then the memory usage should stay roughly the same (as it should, that's what -dbcache is for), but the number of transactions that can be cached will increase.

MemoryResource::AllocateNewBlock is the only place where I actually malloc a new block that's divided into the chunks. Here I've replaced the ::operator new(num_chunks* m_chunk_size_bytes) with ::alligned_alloc(sysconf(_SC_PAGESIZE), num_chunks* m_chunk_size_bytes). And use free in ~MemoryResource.
I also changed the default allocation size m_block_size_bytes from 262144 to sysconf(_SC_PAGESIZE).

hmm yeah it's interesting to think through the alignment issues. I think I understand the code a bit better now so it makes sense that most of you allocations are already aligned. One thing that strikes me is that it seems that you have these 104 byte chunks (13 uint64_t s). You might get better properties if you pad them out to the nearest 32/64/128 bytes (memory overhead 24 bytes :( ), because then you'll never have nodes across cache lines. Memory usage is a bit worse though, but cache perfomance may be better this way? https://www.usenix.org/legacy/publications/library/proceedings/als00/2000papers/papers/full_papers/sears/sears_html/index.html for reference.

might also be interesting to bump the CScript prevector size from 28 to 35 (7 bytes). This would help with the above as well because if we're 104/128 byte aligned we have the capacity & then we'd also save a prevector allocation (which means the vector costs 25 bytes + 34-35 bytes) for a non p2sh segwit v0-v1 output, and also means even more indirection.

This might have system impacts very broadly because prevector is a leaky optimization sadly.

I've benchmarked the performance of CChainState::ConnectBlock between cde8a99 (PR) and the mergebase 803ef70 (MB) using the validation::connect_block tracepoint. The tracepoint reports the time it took to connect each block. This means my results don't include the time it took to download and, AFAIK, not the time it took to persist the block to disk. I didn't look at memory usage.

I've oriented myself on @jamesob's parameters and synced the blocks 500.000 to 540.000 from a localhost peer three times for the PR and the MB. I used the default dbcache (shouldn't matter for my measurements as cache flushes don't happen while inside CChainState::ConnectBlock). I've used an idle workstation with an i5 6500 and an NVME drive. Room and hardware temperature between runs changed which could have impacted performance. A bpftrace script to hook into the tracepoint can be found here.

Total time spent in CChainState::ConnectBlock per run for PR and MB:

(PR run 2 and run 3 are overlapping quite a bit and indistinguishably here)

My results confirm that less time is spent in CChainState::ConnectBlock with PR compared to MB. A performance improvement between 6% - 10% is likely.

To rule out temperature effects on performance, these measurements could be redone with a properly cooled server/workstation.

EDIT: I did another three runs of PR and MB with calling pyperf system tune beforehand as @martinus suggested. PR is still faster.

@JeremyRubin I actually tried to bump it up to 128 byte to see what that does, but I didn't see any major difference. The benchmark got maybe 1% slower, but maybe the benchmark is also not very realistic. I also tried to reduce the size by 8 byte (which can be done by making use of the Coin's padding in CCoinsCacheEntry, I might open anothe PR for that), and it got about ~1% faster. I think though that even with no performance benefit the node_allocator is worthwhile because it has lower memory overhead, so we can cache more entries with the same -dbcache setting.

@jonatack Thanks for the review! I'm not sure though how I should best incorporate your changes? Should I copy them and add a Co-authored-by in the commit message? (I've never done that)

@0xB10C Thanks for the benchmark! You might get a bit more stable result with pyperf: I always use sudo pyperf system tune before I run a benchmark which does a few things to make benchmarks much more stable (e.g. locks the CPU to a fixed frequency, disables turbo boost)

@jonatack Thanks for the review! I'm not sure though how I should best incorporate your changes? Should I copy them and add a Co-authored-by in the commit message? (I've never done that)

Thanks! I'd say squash in the changes you want to keep. You can add an empty line followed by Co-authored-by: Jon Atack <jon@atack.com> to the bottom of a commit message if you like, but it was just a regular average review :)

Bench results with more modest dbcache (800): 6% speedup, 6.7% less memory usage.

I've now updated the code with correct memory estimation, and benchmarked it. I had a fully synchronized node, and ran -reindex-chainstate from block 0 to 690000. All done on a Intel i7 8700, locked to 3200 MHz. I used this command:

/usr/bin/time -v bitcoind -datadir=/run/media/martinus/big/bitcoin/db -dbcache=5000 -assumevalid=00000000000000000002a23d6df20eecec15b21d32c75833cce28f113de888b7 -reindex-chainstate -printtoconsole=0 -stopatheight=690000

The PR ran quite a bit faster than master, 20.8%, with practically the same memory usage. Here some interesting data from /usr/bin/time:

Here are some graphs that I created from parsing the debug.log file:

CCoinsMap requires currently 104 byte for one node, and node_allocator basically uses exactly that (a bit more for house keeping of the allocated blocks but that's practically negigable), and the std::unordered_map's default requires 128 byte (16 byte house keeping, and 8 more byte for 16 byte alignment). So we can cache quite a bit more transactions in the same amount of memory:

Due to the different allocation behavior (it allocates one big chunk of memory right as the first Coin is added), I also had to update the checks in validation_flush_tests.cpp

Unfortunately Microsofts implementation of unordered_map behaves quite a bit different from libc++ and libstdc++, so the heuristic that I'm using to detect the node size doesn't work. I've added a WIP to the header until I've fixed this. Most likely I'll ditch the heuristic completely, and properly calculate the correct size. I'm already doing that in the tests anyways (except for windows)

Rebased to resolve conflict in Makefile.test.include
By the way, is there an easy way to see what has actually changed in a rebase? I just moved 2 lines.

Rebased to resolve conflict in Makefile.test.include By the way, is there an easy way to see what has actually changed in a rebase? I just moved 2 lines.

git range-diff a19f641 472f5b0 95c53bf

(Will re-review this PR soon.)

I have been testing this on a busy node (~400 connections) for more than a month. I have noticed no crashes, no memory leaks, and no other unexpected behavior.

I see a number of unaddressed comments here by @ryanofsky. What is the status of those?

I see a number of unaddressed comments here by @ryanofsky. What is the status of those?

I've now gone through all unaddressed comments and marked all as resolved that I consider fully resolved. As far as I can say only nits remain

I have been testing this on a busy node (~400 connections) for more than a month. I have noticed no crashes, no memory leaks, and no other unexpected behavior.

Still no issues!

Still, to be honest, I think this change is a bit scary, and I have a hard time signing off on it. The reason is that it adds quite a lot of complexity, and depends on quite some C++ magic and cleverness (e.g. relying on unordered_map internals). C++ being not exactly a memory-safe language, this increases the risk of accidental foot-guns. I appreciate the work it's great to make things faster, and I really don't want to discourage it, but, especially as long as it's used for consensus code we do have to err on the side of safety and correctness.

Still, to be honest, I think this change is a bit scary

I guess it is, it got a lot more complex that I initially anticipated. I don't think it can be made much simpler. I'm pretty sure it works, but obviously there's no 100% guarantee. So I'm fine with it not being merged, at least then I can't be responsible for a bitcoind crash 😅

Since the code here is not tightly coupled to bitcoind, when I have the time I will try to create a generic c++ library out of it.

Thanks everyone who reviewed & tested or otherwise spent time on this!

@martinus this pull was discussed yesterday at the weekly meeting (see https://www.erisian.com.au/bitcoin-core-dev/log-2022-06-02.html#l-358). I've been running it without issues as well for some time and am concept ACK (but need to re-review carefully). @sipa wrote "I need to look at the latest code changes again, but I'm very concept ACK on that allocator", followed by @laanwj "to be clear i'm not against it, but we need to be really sure it gets enough review". For info :)

I'm trying to understand what potential problems we fear here. Is it that the node crashes or is it consensus problems (or both)?

I didn't mean for it to be closed @martinus. Of course, you're free to. Making a generic library sounds like a good idea. We could subtree or import it once it's "proven".

I just wanted to voice my concern. If we can drum up enough reviewers here with the appropriate knowledge about C++ internals (and it doesn't all rest on @sipa's shoulders, for example), it'd be good. Something that was proposed in the meeting yesterday was an advanced review club.

I'm trying to understand what potential problems we fear here. Is it that the node crashes or is it consensus problems (or both)?

Memory corruption resulting in consensus problems would be the worst outcome. Other crashes (especially if hard to debug / diagnose) would be bad too, of course.

I'm trying to understand what potential problems we fear here. Is it that the node crashes or is it consensus problems (or both)?

I think the major concern here could be summarized as "we're worried about unknown unknowns." Swapping out an allocator (or as in the original case of #16718, the whole map implementation) entails displacing a lot of low-level C++ code that is widely deployed and tested by the standard library with code that we (or if not just us, a much smaller subset of the software world) maintain and test.

If anything goes wrong with the UTXO set, it's no news to everyone that it certainly spells big issues for bitcoin. While the performance gains here are very enticing, and indeed @luke-jr earlier made the interesting point that maybe moving this critical code into our domain of control (and out of the black box of std) may be preferable, since we would explicitly understand and maintain a very core dependency of the validation process, this "mountain man" approach obviously has an associated cost: maintaining such an important and sensitive piece of the system represents a liability that we would no longer shoulder alongside the wider C++ usage base.

I originally proposed the hashmap implementation change that (I think?) inspired @martinus to undertake this work. I'm glad he has done this work, even if it remains experimental, because it's important for us to understand this design space better. But that said I can understand why @laanwj would express an abundance of caution about this kind of thing, and it resonates with me. Everyone here understands that a change like this should not be done lightly, but even given that, it's hard to know when we've "tested enough" to know that this will be safe for perpetuity. Unknown unknowns.

All that said, I'm far from the most qualified systems guy on this project, so it would be interesting to hear from others like @sipa @ryanofsky @theuni @TheBlueMatt. Maybe we can fuzz this to death on a bunch of different platforms and convince ourselves that it's as safe or safer than using std's allocator. Such a determination is out of my ability.

I think I've found a way to get almost all of the benefit of the node_allocator with a significantly less scary implementation. Same memory advantage, but a bit slower. I'll prepare a new PR 👍

@martinus I started working on a fuzz test for the allocator, to show at least its behavior w.r.t. its external interface is correct.

If you're going to simplify things: will there still be an allocator class, and a concept of a memory resource? If so, will the memory resource still be parametrized by the size of the pooled objects in it?

@martinus I started working on a fuzz test for the allocator, to show at least its behavior w.r.t. its external interface is correct.

That's awesome!

If you're going to simplify things: will there still be an allocator class, and a concept of a memory resource? If so, will the memory resource still be parametrized by the size of the pooled objects in it?

There will be just a memory resource, which will be passed to a std::pmr::polymorphic_allocator. I have a prototype of the memory resource here: https://gist.github.com/martinus/0cee4dd177beda78bb1e2e3d128c2d70
That's basically all that is needed in <100 lines of code. This implements the abstract std::pmr::memory_resource interface which is much simpler than implementing a full allocator. Doesn't need any rebinding, type casting, reinterpret_cast.

Also, instead of having to correctly guess the pool's memory size I simply use a vector with multiple pools of different size. Most of them will stay empty, but that overhead is negligible.

Usage is like so:

using CCoinsMap = std::pmr::unordered_map<COutPoint, CCoinsCacheEntry, SaltedOutpointHasher>;
auto mr = NodePoolResource<256>(); // large enough to fit nodes size
auto map = CCoinsMap{0, SaltedOutpointHasher{}, std::equal_to<COutPoint>{}, &mr};

@martinus Cool, that looks a lot simpler. The runtime indirection from the polymorphic resource does sound like it'd introduce a performance penalty, so I think we'll want benchmarks to see if it doesn't hurt.

A few thoughts:

• I like the idea of giving the resource a pool for every allocation size up to a limit; that seems far less fragile than something that only works for one size.
• It seems it would be possible to actually (possibly later, even) introduce a class like std::polymorphic_allocator, but which is parametrized by the concrete type of the resource? If the NodePoolResource is marked final (perhaps a good idea to do in general), then the compiler would be able to optimize away the dynamic calls even. This would allow getting the same benefits as the earlier approach in a more incremental way (and perhaps may be useful for benchmarking the overhead of the polymorphism exactly).
• I believe it may be desirable to round up size at the start of do_allocate / do_deallocate instead of using 0 for small sizes. While that is not optimally efficient, it's still better in practice than deferring to the default allocator (as at least on common platforms, that has an overhead of at least two pointers). The requirements would be (a) size has to be a multiple of alignment_of(FreeList*) and of alignment, and (b) size has to be at least sizeof(FreeList*) and at least size. Because sizes are always a multiple of alignment, and alignments are always powers of two, I believe these two requirements can be met as std::max(S, (size + A - 1) & ~size_t{A - 1}), where S = sizeof(FreeList*) and A = alignment_of(FreeList*).
• When the above is done, I think the code can otherwise actually ignore the input alignment value (making it work for any alignment up to the alignment of the pools themselves, which ought to be sufficient for any object).
• Would it make sense to use an array of pools, rather than a vector? That avoids one memory indirection at runtime, and for MAX_BLOCK_SIZE_BYTES=256, an array of 63 elements suffices (even with A=S=4).

Thanks @spia for having a close look!

I believe it may be desirable to round up size at the start of do_allocate / do_deallocate instead of using 0 for small sizes.

I can do that and it probably makes the resource more widely usable, but at least for the CCoinsMap it won't make a difference because it has the same alignment as the FreeList*.

Would it make sense to use an array of pools, rather than a vector?

Yes! I originally wanted to get rid of the template argument, but using std::array is actually a bit faster in my benchmarks so I'll go that route.

I'm working on that in this branch, where I'm now using std::array and rounding up: master...martinus:2022-06-very-not-scary-NodePoolResource

I hope to have something PR-ready in a week or two.

@martinus Here is a generic memory resource fuzzer: https://github.com/sipa/bitcoin/commits/202206_pmrallocfuzz

It also includes a somewhat modified version of your code, with a few more template parameters/sanity checks, and the rounding as I was thinking of it. Seems to work great. Feel free to try on top of your version of the resource, or combine ideas/whatever.

I like making the code generally usable in wider scenarios than just the ones we care about, as it means generic tests can be written for it, which need fewer assumptions.

Another idea for something to include in the tests which I haven't done: add a member function to the resource to ask if it still has any outstanding allocations (by summing the size of all allocated chunks, and comparing with the sum of all elements in the freelist).

Another idea for something to include in the tests which I haven't done: add a member function to the resource to ask if it still has any outstanding allocations (by summing the size of all allocated chunks, and comparing with the sum of all elements in the freelist).

Excellent idea, I've now added an even stronger check: make sure that all data in the freelist actually comes from the chunks, doesn't overlap in any way, and each byte from the chunks can be found in the freelists or is still available