sync: improve CCoinsViewCache ReallocateCache - 2nd try

[fjahr]

Rebased and reopened #28945

Original description:

TL;DR: this change improves sync time on my PC by ~6%.

While syncing when the CCoinsViewCache gets full it is flushed to disk and then memory is freed. Depending on available cache size, this happens several times. This PR removes the unnecessary reallocations for temporary CCoinsViewCache and reserves the cacheCoins's bucket array to its previous size.

I benchmarked the change on an AMD Ryzen 9 7950X with this command:

hyperfine \
--show-output --parameter-list commit b5a271334ca81a6adcb1c608d85c83621a9eae47,ceeb71816512642e92a110b2cf5d2549d090fe78 \
--setup 'git checkout {commit} && make -j$(nproc) src/bitcoind' \
--prepare 'sync; sudo /sbin/sysctl vm.drop_caches=3' \
-M 3 './src/bitcoind -dbcache=500 -reindex-chainstate -printtoconsole=0 -stopatheight=500000'

Where b5a2713 is mergebase, and ceeb718 this PR.

Which runs ./src/bitcoind -dbcache=500 -reindex-chainstate -printtoconsole=0 -stopatheight=500000 3 times and compares both commits, giving this result:

Benchmark 1: ./src/bitcoind -dbcache=500 -reindex-chainstate -printtoconsole=0 -stopatheight=500000 (commit = b5a271334ca81a6adcb1c608d85c83621a9eae47)
  Time (mean ± σ):     2815.648 s ± 70.720 s    [User: 2639.959 s, System: 640.051 s]
  Range (min … max):   2736.616 s … 2872.964 s    3 runs

Benchmark 2: ./src/bitcoind -dbcache=500 -reindex-chainstate -printtoconsole=0 -stopatheight=500000 (commit = ceeb71816512642e92a110b2cf5d2549d090fe78)
  Time (mean ± σ):     2661.520 s ± 23.205 s    [User: 2473.010 s, System: 624.040 s]
  Range (min … max):   2635.816 s … 2680.926 s    3 runs

Summary
  ./src/bitcoind -dbcache=500 -reindex-chainstate -printtoconsole=0 -stopatheight=500000 (commit = ceeb71816512642e92a110b2cf5d2549d090fe78) ran
    1.06 ± 0.03 times faster than ./src/bitcoind -dbcache=500 -reindex-chainstate -printtoconsole=0 -stopatheight=500000 (commit = b5a271334ca81a6adcb1c608d85c83621a9eae47)

[DrahtBot]

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/30370.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept NACK	l0rinc

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #30425 (kernel: De-globalize static validation variables by TheCharlatan)
• #28280 (Don't empty dbcache on prune flushes: >30% faster IBD by andrewtoth)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

[fjahr]

CI failure is unrelated (#30368).

[andrewtoth]

I have the same comment from #28945: Why can we not revert https://github.com/bitcoin/bitcoin/commit/5e4ac5abf54f8e6d6330df0c73119aa0cca4c103 to speed this up instead? I'm not clear why we need to have the coinsCache free up all associated memory to use the PoolAllocator.

[DrahtBot]

🐙 This pull request conflicts with the target branch and needs rebase.

[fjahr]

this seems to completely contradict what ReallocateCache was introduced in the first place

Can you explain what you mean by this? I don't understand how making it optional contradicts it.

[l0rinc]

Can you explain what you mean by this

I expanded on it in https://github.com/bitcoin/bitcoin/pull/30370#discussion_r1753749012.

My understanding is that ReallocateCache was introduced to save memory when shrinking the map after evictions, and this PR prohibits shrinking and reallocates the same capacity we were just trying to get rid of. If I'm mistaken here, I'd appreciate an explanation for why we can't solve it in a simpler way - e.g. by getting rid of ReallocateCache (or evicting the least recently used instead, since we have a linked list of dirty entries now), or something similar.

[andrewtoth]

Researching this more, I think I can answer my own question. The pool allocator introduced in https://github.com/bitcoin/bitcoin/pull/25325 cannot shrink in memory. It can only allocate more chunks, and freed memory just adds some nodes in the chunks to a freelist. But, we don't discount the available nodes in the freelist. So, even though we clear all elements, the memory usage reported by the map stays the same. This works great if we just fill up the map and then reallocate it, but it doesn't really work well now when we can sync the cache to disk without reallocating the cache. It also prevents us from being smarter about cache usage by tracking and deleting least recently added entries instead of just wiping it all when it gets full.

[andrewtoth]

In light of this, I think a better approach is to track the available memory in the freelist in the PoolAllocator and expose it in a public getter. Then, discount that available memory in CCoinsViewCache::DynamicMemoryUsage. And finally, revert 5e4ac5abf54f8e6d6330df0c73119aa0cca4c103 and achieve the speedup.

I think this will result in even more speedup, since the actual chunks in the pool allocator will be recycled and won't have to be reallocated.

[andrewtoth]

While trying to implement the approach above, it became apparent that we still need the call to ReallocateCache here. This is for the case when IBD is done with memory normally reserved for the mempool. After IBD is finished and the mempool starts filling up and encroaching on the memory used by the cache, the cache must be reallocated. There is no other way to shrink it.

I think it's good that we are not calling reallocate on the ephemeral views, but I think we can do better with the preallocation. Since we know the total cache size with https://github.com/bitcoin/bitcoin/blob/master/src/validation.cpp#L2760-L2761, we can divide that by sizeof(CoinsCachePair) and get an upper bound on how many entries we could ever add to that cache until we have to flush. Using that number with reserve is more accurate than just using the previous bucket size. The amount of extra space might have changed, or it could have been flushed spuriously with an rpc call. This way we are guaranteed to not have to resize the cache until the next flush.

We should also take this a step further and reserve the amount of entries needed for the ephemeral views used to connect and disconnect blocks. The only time the pool allocator can't be used and has to fall back to new is when the cache has to be resized, so these are allocations we want to avoid. By tallying the number of inputs and outputs in the block before connecting/disconnecting, we can then reserve and only do a single allocation per block.

[l0rinc]

@fjahr, I've measured the effect of this change on a full IBD - <1%, doesn't seem significant.

benchmarks

master

Benchmark 1: COMMIT=d73f37dda221835b5109ede1b84db2dc7c4b74a1 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=870000 -printtoconsole=0                             
  Time (mean ± σ):     39690.021 s ± 333.717 s    [User: 51244.778 s, System: 3430.580 s]                                                                                                 
  Range (min … max):   39454.047 s … 39925.995 s    2 runs 

this PR rebased on top of master

Benchmark 1: COMMIT=ba36ac6c4ae46b1dc4386326844ce67664fc9206 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=870000 -printtoconsole=0
  Time (mean ± σ):     39587.720 s ± 527.298 s    [User: 51105.792 s, System: 3430.869 s]
  Range (min … max):   39214.864 s … 39960.575 s    2 runs

Given this and @andrewtoth's excellent analysis above, does this PR still make sense?

I will try to provide an alternative, but it might take some time since it depends on other changes that are meant to improve memory accounting (e.g. https://github.com/bitcoin/bitcoin/pull/18086, https://github.com/bitcoin/bitcoin/pull/28531), and I still think that dropping the cache completely is really wasteful and we should try some form of MRU cache like https://github.com/bitcoin/bitcoin/pull/31102 instead.

This is what an IBD with default max cache size looks like:

[fjahr]

Alright, closing if the effect isn't significant. I have a few too many things on my plate at the moment anyway so maybe someone else wants to investigate further from here.