Draft: CCoinMap Experiments #32128

pull martinus wants to merge 3 commits into bitcoin:master from martinus:2025-03-scheduler-destroy-in-separate-thread-experiment changing 9 files +111 −31
  1. martinus commented at 6:02 am on March 24, 2025: contributor

    This is a draft PR to show various possible optimizations for CCoinsMap. In my benchmark, all these changes lead to a statistically significant speed improvement for -reindex-chainstate.

     0Benchmark 1: ./build/bin/bitcoind -stopatheight=600000 -dbcache=5000 -printtoconsole=0 -reindex-chainstate -noconnect -connect=192.168.8.118 (COMMIT = ac188b573c8)
 1  Time (mean ± σ):     2089.253 s ± 23.737 s    [User: 2110.111 s, System: 299.197 s]
 2  Range (min … max):   2062.751 s … 2108.561 s    3 runs
 3
 4Benchmark 2: ./build/bin/bitcoind -stopatheight=600000 -dbcache=5000 -printtoconsole=0 -reindex-chainstate -noconnect -connect=192.168.8.118 (COMMIT = 7113095b3cd)
 5  Time (mean ± σ):     2431.028 s ± 17.544 s    [User: 2439.746 s, System: 284.994 s]
 6  Range (min … max):   2415.408 s … 2450.009 s    3 runs
 7
 8Benchmark 3: ./build/bin/bitcoind -stopatheight=600000 -dbcache=5000 -printtoconsole=0 -reindex-chainstate -noconnect -connect=192.168.8.118 (COMMIT = 7370e13d93d)
 9  Time (mean ± σ):     2530.955 s ± 21.575 s    [User: 2539.882 s, System: 285.890 s]
10  Range (min … max):   2512.525 s … 2554.687 s    3 runs
11
12Benchmark 4: ./build/bin/bitcoind -stopatheight=600000 -dbcache=5000 -printtoconsole=0 -reindex-chainstate -noconnect -connect=192.168.8.118 (COMMIT = e568c1dd134)
13  Time (mean ± σ):     2839.864 s ±  9.993 s    [User: 2850.112 s, System: 287.916 s]
14  Range (min … max):   2830.073 s … 2850.047 s    3 runs
15
16Summary
17  ./build/bin/bitcoind -stopatheight=600000 -dbcache=5000 -printtoconsole=0 -reindex-chainstate -noconnect -connect=192.168.8.118 (COMMIT = ac188b573c8) ran
18    1.16 ± 0.02 times faster than ./build/bin/bitcoind -stopatheight=600000 -dbcache=5000 -printtoconsole=0 -reindex-chainstate -noconnect -connect=192.168.8.118 (COMMIT = 7113095b3cd)
19    1.21 ± 0.02 times faster than ./build/bin/bitcoind -stopatheight=600000 -dbcache=5000 -printtoconsole=0 -reindex-chainstate -noconnect -connect=192.168.8.118 (COMMIT = 7370e13d93d)
20    1.36 ± 0.02 times faster than ./build/bin/bitcoind -stopatheight=600000 -dbcache=5000 -printtoconsole=0 -reindex-chainstate -noconnect -connect=192.168.8.118 (COMMIT = e568c1dd134)
  2. SaltedOutpointHasher uses rapidhash 
    SipHashUint256Extra is rather slow. For the purpose of generating a hash
from a COutPoint and some seed that is only used inside a hashmap, it is
sufficient to use a non-cryptographic hash. rapidhash [1] is a well tested
and very fast hash function. This implementation strips down this hash
function, originally implemented for a memory buffer, to be used with
the COutPoint + 2*64bit seed as the input.

[1] https://github.com/Nicoshev/rapidhash
    104d5dd778
  3. CCoinsViewCache::BatchWrite lookup optimization 
    In the case when parent cache does not have an entry while child cache does,
this reduces the double hash lookup (find + try_emplace) with a single
try_emplace.
    723c49b63b
  4. DrahtBot commented at 6:02 am on March 24, 2025: contributor

    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/32128.

    Reviews

    See the guideline for information on the review process. A summary of reviews will appear here.

    Conflicts

    Reviewers, this pull request conflicts with the following ones:

    • #31895 (doc: Improve dependencies.md by NicolaLS)
    • #31703 (Use number of dirty cache entries in flush warnings/logs by sipa)
    • #30673 (coins: remove logic for spent-and-FRESH cache entries and writing non-DIRTY entries by andrewtoth)
    • #30442 ([IBD] precalculate SipHash constant salt calculations by l0rinc)

    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.

  5. DrahtBot commented at 6:51 am on March 24, 2025: contributor

    🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/39270918766

    Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

    • Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

    • A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.

    • An intermittent issue.

    Leave a comment here, if you need help tracking down a confusing failure.

  6. DrahtBot added the label CI failed on Mar 24, 2025
  7. in src/coins.h:225 in 1ae2763450 outdated 
    226-                                     CCoinsCacheEntry,
227-                                     SaltedOutpointHasher,
228-                                     std::equal_to<COutPoint>,
229-                                     PoolAllocator<CoinsCachePair,
230-                                                   sizeof(CoinsCachePair) + sizeof(void*) * 4>>;
231+using CCoinsMap = boost::unordered_node_map<COutPoint,
    l0rinc commented at 12:49 pm on March 24, 2025:

    My understanding is that we’re trying to get away from external dependencies, so if this does improve performance, we may want to copy it over.

    For the record, similar attempts have been made before: #22640 @andrewtoth suggested we try your unordered_dense here as well.

    My understanding is that this will likely require retesting our memory related assumption so far.

    martinus commented at 6:24 pm on March 27, 2025:
    I think boost maps might be a better choice, I believe they are better tested, and might be faster as well. Also for boost::unordered_node_map references are stable, which is not the case for unordered_dense, so it is easier to have this as a drop-in replacement without worrying about pointer stability.
  8. in src/coins.cpp:192 in 723c49b63b outdated 
    185@@ -186,30 +186,34 @@ bool CCoinsViewCache::BatchWrite(CoinsViewCacheCursor& cursor, const uint256 &ha
186         if (!it->second.IsDirty()) {
187             continue;
188         }
189-        CCoinsMap::iterator itUs = cacheCoins.find(it->first);
190-        if (itUs == cacheCoins.end()) {
191+        CCoinsMap::iterator itUs;
192+        bool isInserted = false;
193+        if (!(it->second.IsFresh() && it->second.coin.IsSpent())) {
194+            std::tie(itUs, isInserted) = cacheCoins.try_emplace(it->first);
    l0rinc commented at 12:53 pm on March 24, 2025:
    This seems similar to #30326 - I’m surprised this has a measurable effect (and that I haven’t found it so far :D)
    martinus commented at 6:25 pm on March 27, 2025:
    It seems it has far less of an effect in your test, maybe I should also run the benchmark on my machine until block 890k for comparison
    l0rinc commented at 7:06 pm on March 27, 2025:
    Or maybe these are only measurable after the other changes are in place - I have compared all commits independently.
  9. in src/crypto/siphash.h:47 in 104d5dd778 outdated 
    43@@ -44,5 +44,6 @@ class CSipHasher
44  */
45 uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val);
46 uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra);
47+uint64_t ModifiedRapidHash(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra);
    l0rinc commented at 1:01 pm on March 24, 2025:

    I have also measured this being a bottleneck very often (https://github.com/bitcoin/bitcoin/pull/30442), and @sipa mentioned originally that we can swap it out with something better later: #8020 (comment)

    Do we need to account for collision attacks here, given that inclusion into the map is not for free?

    martinus commented at 6:27 pm on March 27, 2025:
    I think collision attacks can’t be an issue because the hash implementation still uses the random seed, and the hash itself is of good quality.
    sipa commented at 7:25 pm on March 27, 2025:

    I’m pretty skeptical about that claim. If the hash isn’t of cryptographic quality, I don’t know how I’d reason about an attacker’s ability to control the buckets, even with a secret random seed.

    To be clear, it’s entirely reasonable that this may be safe, but I don’t know how I’d convince myself that it is definitely safe.

    martinus commented at 2:26 pm on March 28, 2025:
    @sipa thanks, you are of course right; I should have read a bit more about that before… Nevertheless I think it’s at least interesting to see what difference a fast hash would make.
  10. l0rinc commented at 1:05 pm on March 24, 2025: contributor

    Welcome back @martinus, we missed you! :) I will measure these changes separately until 890k blocks soon. I have included this change a tracking PR where we have other similar experiments: #32043

    Edit: is the name of the branch an easter egg for what to expect next?

  11. martinus commented at 3:36 pm on March 24, 2025: contributor

    Welcome back @martinus, we missed you! :) I will measure these changes separately until 890k blocks soon. I have included this change a tracking PR where we have other similar experiments: #32043

    I have not done any programming in half a year, looking forward to getting back :)

  12. in doc/dependencies.md:21 in 1ae2763450 outdated 
    17@@ -18,7 +18,7 @@ Bitcoin Core requires one of the following compilers.
18 | Dependency | Releases | Version used | Minimum required | Runtime |
19 | --- | --- | --- | --- | --- |
20 | CMake | [link](https://cmake.org/) | N/A | [3.22](https://github.com/bitcoin/bitcoin/pull/30454) | No |
21-| [Boost](../depends/packages/boost.mk) | [link](https://www.boost.org/users/download/) | [1.81.0](https://github.com/bitcoin/bitcoin/pull/26557) | [1.73.0](https://github.com/bitcoin/bitcoin/pull/29066) | No |
    chellas2wp commented at 6:46 am on March 25, 2025:
    Starting process/approval request/apply specifications.
  13. laanwj added the label Validation on Mar 26, 2025
  14. l0rinc commented at 8:26 pm on March 26, 2025: contributor

    I have measured these commits separately against a baseline (undoing each commit, to measure them independently).

    • 1d281daf86 Merge bitcoin/bitcoin#32095: doc: clarify that testnet min-difficulty is the baseline
    • 1112433318 SaltedOutpointHasher uses rapidhash is 5% faster than 1d281daf86
    • e00d828362 CCoinsViewCache::BatchWrite lookup optimization is 0.5% faster than 1d281daf86
    • 1630e368d1 Use boost::unordered_node_map for CCoinsMap is 7.4% faster than 1d281daf86
     01d281daf86 (HEAD, origin/master, origin/HEAD) Merge bitcoin/bitcoin#32095: doc: clarify that testnet min-difficulty is not optional
 11112433318 SaltedOutpointHasher uses rapidhash
 2e00d828362 CCoinsViewCache::BatchWrite lookup optimization
 31630e368d1 (l0rinc/detached186) Use boost::unordered_node_map for CCoinsMap
 4Benchmark 1: COMPILER=gcc COMMIT=1d281daf8613a3cb7a26759c351ffb34dab0f656 ./build/bin/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=888888 -dbcache=5000 -blocksonly -reindex-chainstate -connect=0 -printtoconsole=0
 5  Time (abs ≡):        25746.852 s               [User: 24476.673 s, System: 1096.263 s]
 6 
 7Benchmark 2: COMPILER=gcc COMMIT=1112433318cbb096fec0cc83d2c424db652c126f ./build/bin/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=888888 -dbcache=5000 -blocksonly -reindex-chainstate -connect=0 -printtoconsole=0
 8  Time (abs ≡):        24511.624 s               [User: 23046.157 s, System: 1074.909 s]
 9 
10Benchmark 3: COMPILER=gcc COMMIT=e00d8283624f3d937f1222cb2c1540655045b095 ./build/bin/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=888888 -dbcache=5000 -blocksonly -reindex-chainstate -connect=0 -printtoconsole=0
11  Time (abs ≡):        25616.379 s               [User: 24209.459 s, System: 1088.005 s]
12 
13Benchmark 4: COMPILER=gcc COMMIT=1630e368d190a75870399cc38af3c6023faaf2d9 ./build/bin/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=888888 -dbcache=5000 -blocksonly -reindex-chainstate -connect=0 -printtoconsole=0
14  Time (abs ≡):        23966.508 s               [User: 22294.996 s, System: 1082.040 s]
15 
16Summary
17  COMPILER=gcc COMMIT=1630e368d190a75870399cc38af3c6023faaf2d9 ./build/bin/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=888888 -dbcache=5000 -blocksonly -reindex-chainstate -connect=0 -printtoconsole=0 ran
18    1.02 times faster than COMPILER=gcc COMMIT=1112433318cbb096fec0cc83d2c424db652c126f ./build/bin/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=888888 -dbcache=5000 -blocksonly -reindex-chainstate -connect=0 -printtoconsole=0
19    1.07 times faster than COMPILER=gcc COMMIT=e00d8283624f3d937f1222cb2c1540655045b095 ./build/bin/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=888888 -dbcache=5000 -blocksonly -reindex-chainstate -connect=0 -printtoconsole=0
20    1.07 times faster than COMPILER=gcc COMMIT=1d281daf8613a3cb7a26759c351ffb34dab0f656 ./build/bin/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=888888 -dbcache=5000 -blocksonly -reindex-chainstate -connect=0 -printtoconsole=0
  15. Use boost::unordered_node_map for CCoinsMap 
    boost::unordered_node_map is a highly optimized hashmap, available since
boost 1.82, that is API compatible to std::unordered_map for our use case.
It also can use the existing PoolAllocator.
    18b2c263aa
  16. martinus force-pushed on Mar 27, 2025


martinus DrahtBot l0rinc sipa chellas2wp

Labels
Validation CI failed

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2025-03-28 15:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me