fuzz: Speed up *_package_eval fuzz targets a bit #31457

pull maflcko wants to merge 2 commits into bitcoin:master from maflcko:2412-fuzz-pkg-eval-faster changing 1 files +4 −4
  1. maflcko commented at 12:42 pm on December 10, 2024: member

    Each target is at least 10% faster for me when running over the current set of qa-assets, which seems nice.

    The changes outpoints_value from a map to an unordered map, which is safe, because the element order is not used in the fuzz test and the map is only used for lookup.

    (mempool_outpoints can’t be changed, because the order matters here. Using unordered_set here may result in a non-deterministic fuzz target, given the same fuzz input.)

  2. DrahtBot commented at 12:43 pm on December 10, 2024: 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/31457.

    Reviews

    See the guideline for information on the review process.

    Type Reviewers
    ACK l0rinc, dergoegge

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

  3. DrahtBot added the label Tests on Dec 10, 2024
  4. in src/test/fuzz/package_eval.cpp:203 in fafaad5edc outdated 
    194@@ -195,8 +195,8 @@ FUZZ_TARGET(ephemeral_package_eval, .init = initialize_tx_pool)
195     MockTime(fuzzed_data_provider, chainstate);
196 
197     // All RBF-spendable outpoints outside of the unsubmitted package
198-    std::set<COutPoint> mempool_outpoints;
199-    std::map<COutPoint, CAmount> outpoints_value;
200+    std::unordered_set<COutPoint, SaltedOutpointHasher> mempool_outpoints;
    dergoegge commented at 3:24 pm on December 10, 2024:
    Using a SaltedOutpointHasher probably requires to call SeedRandomStateForTest(SeedRand::ZEROS) each iteration. Otherwise non-determinism might happen due to e.g. different order when iterating over the sets.
    maflcko commented at 3:47 pm on December 10, 2024:

    Good catch. This means:

    • Other tests may also need a re-seed on every iteration, if they interact with data, sorted by a salted hasher
    • The speed-up may actually come from invalidating the fuzz inputs, making a change like this harder to test
    maflcko commented at 10:57 am on December 12, 2024:

    Other tests may also need a re-seed on every iteration, if they interact with data, sorted by a salted hasher

    Fixed in #31481, possibly

    maflcko commented at 11:37 am on February 24, 2025:

    Reopened this pull request and dropped the changes to mempool_outpoints for now.

    I’ve kept the changes to outpoints_value, because:

    • the map is only used for lookup, so the order should not matter
    • It still provides a speedup of about 10%, albeit a bit less than the previous version
  5. maflcko marked this as a draft on Dec 10, 2024
  6. maflcko force-pushed on Jan 14, 2025
  7. maflcko commented at 8:14 am on January 20, 2025: member
    Closing for now, because changing the order of the elements in the set may invalidate the existing fuzz inputs, making this harder to review/test.
  8. maflcko closed this on Jan 20, 2025
  9. maflcko deleted the branch on Jan 20, 2025
  10. maflcko restored the branch on Feb 24, 2025
  11. maflcko reopened this on Feb 24, 2025
  12. maflcko force-pushed on Feb 24, 2025
  13. maflcko marked this as ready for review on Feb 24, 2025
  14. fuzz: [refactor] Avoid confusing c-style cast fa40fd043a
  15. fuzz: Speed up *_package_eval fuzz targets a bit fac3d93c2b
  16. maflcko force-pushed on Mar 16, 2025
  17. in src/test/fuzz/package_eval.cpp:204 in fac3d93c2b 
    200@@ -201,7 +201,7 @@ FUZZ_TARGET(ephemeral_package_eval, .init = initialize_tx_pool)
201 
202     // All RBF-spendable outpoints outside of the unsubmitted package
203     std::set<COutPoint> mempool_outpoints;
204-    std::map<COutPoint, CAmount> outpoints_value;
205+    std::unordered_map<COutPoint, CAmount, SaltedOutpointHasher> outpoints_value;
    l0rinc commented at 11:12 am on March 17, 2025:

    While I was investigating https://github.com/bitcoin/bitcoin/pull/31682/files#diff-c613867a2f35f2221c4e37262bee556e5b472aa95cd95e1eb0cbf8fe49ad83ffL41 I have also measured something like this, i.e. std::set<COutPoint> vs std::unordered_set<COutPoint, SaltedOutpointHasher> but interestingly I found the opposite - maybe it’s size dependent and small trees are faster than the SipHash calculation:

    std::set vInOutPoints;

    ns/block block/s err% total benchmark
    282,875.72 3,535.12 0.7% 10.96 CheckBlockBench
    266,602.67 3,750.90 0.6% 11.00 CheckBlockBench
    268,925.18 3,718.51 0.5% 11.02 CheckBlockBench

    std::unordered_set<COutPoint, SaltedOutpointHasher> vInOutPoints;

    ns/block block/s err% total benchmark
    1,159,639.34 862.34 0.1% 10.99 CheckBlockBench
    1,156,702.62 864.53 0.2% 10.98 CheckBlockBench
    1,142,114.09 875.57 0.1% 11.01 CheckBlockBench
    maflcko commented at 8:29 pm on March 17, 2025:
    Not sure if the two are comparable, inserting into an empty set or inserting into a set with one value (probably the most common cases) seems plausible to be faster than doing the same in an unordered_set. The goal here is to avoid fuzz timeouts (or long running large fuzz inputs) when using sanitizers.
  18. in src/test/fuzz/package_eval.cpp:203 in fac3d93c2b 
    200@@ -201,7 +201,7 @@ FUZZ_TARGET(ephemeral_package_eval, .init = initialize_tx_pool)
201 
202     // All RBF-spendable outpoints outside of the unsubmitted package
203     std::set<COutPoint> mempool_outpoints;
    l0rinc commented at 11:38 am on March 17, 2025:

    If you think unordered_map is indeed faster (I’ll measure it once my benchmarking servers will be available), we could change the std::set instances as well - and given that they’re array based, we might as well pre-allocate them.

     0diff --git a/src/test/fuzz/package_eval.cpp b/src/test/fuzz/package_eval.cpp
 1--- a/src/test/fuzz/package_eval.cpp	(revision 147655098edde6feffbbe2c601d5874a7d3a3c5c)
 2+++ b/src/test/fuzz/package_eval.cpp	(date 1742211475064)
 3@@ -57,9 +57,9 @@
 4 }
 5 
 6 struct OutpointsUpdater final : public CValidationInterface {
 7-    std::set<COutPoint>& m_mempool_outpoints;
 8+    std::unordered_set<COutPoint, SaltedOutpointHasher>& m_mempool_outpoints;
 9 
10-    explicit OutpointsUpdater(std::set<COutPoint>& r)
11+    explicit OutpointsUpdater(std::unordered_set<COutPoint, SaltedOutpointHasher>& r)
12         : m_mempool_outpoints{r} {}
13 
14     void TransactionAddedToMempool(const NewMempoolTransactionInfo& tx, uint64_t /* mempool_sequence */) override
15@@ -67,6 +67,7 @@
16         // for coins spent we always want to be able to rbf so they're not removed
17 
18         // outputs from this tx can now be spent
19+        m_mempool_outpoints.reserve(m_mempool_outpoints.size() + tx.info.m_tx->vout.size());
20         for (uint32_t index{0}; index < tx.info.m_tx->vout.size(); ++index) {
21             m_mempool_outpoints.insert(COutPoint{tx.info.m_tx->GetHash(), index});
22         }
23@@ -75,6 +76,7 @@
24     void TransactionRemovedFromMempool(const CTransactionRef& tx, MemPoolRemovalReason reason, uint64_t /* mempool_sequence */) override
25     {
26         // outpoints spent by this tx are now available
27+        m_mempool_outpoints.reserve(m_mempool_outpoints.size() + tx->vin.size());
28         for (const auto& input : tx->vin) {
29             // Could already exist if this was a replacement
30             m_mempool_outpoints.insert(input.prevout);
31@@ -200,8 +202,10 @@
32     MockTime(fuzzed_data_provider, chainstate);
33 
34     // All RBF-spendable outpoints outside of the unsubmitted package
35-    std::set<COutPoint> mempool_outpoints;
36+    std::unordered_set<COutPoint, SaltedOutpointHasher> mempool_outpoints;
37+    mempool_outpoints.reserve(g_outpoints_coinbase_init_mature.size());
38     std::unordered_map<COutPoint, CAmount, SaltedOutpointHasher> outpoints_value;
39+    outpoints_value.reserve(g_outpoints_coinbase_init_mature.size());
40     for (const auto& outpoint : g_outpoints_coinbase_init_mature) {
41         Assert(mempool_outpoints.insert(outpoint).second);
42         outpoints_value[outpoint] = 50 * COIN;
43@@ -226,8 +230,10 @@
44 
45         // Make small packages
46         const auto num_txs = outpoint_to_rbf ? 1 : fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 4);
47+        txs.reserve(num_txs);
48 
49-        std::set<COutPoint> package_outpoints;
50+        std::unordered_set<COutPoint, SaltedOutpointHasher> package_outpoints;
51+        package_outpoints.reserve((num_txs - 1) * 4);
52         while (txs.size() < num_txs) {
53             // Create transaction to add to the mempool
54             txs.emplace_back([&] {
55@@ -355,8 +361,10 @@
56     MockTime(fuzzed_data_provider, chainstate);
57 
58     // All RBF-spendable outpoints outside of the unsubmitted package
59-    std::set<COutPoint> mempool_outpoints;
60+    std::unordered_set<COutPoint, SaltedOutpointHasher> mempool_outpoints;
61+    mempool_outpoints.reserve(g_outpoints_coinbase_init_mature.size());
62     std::unordered_map<COutPoint, CAmount, SaltedOutpointHasher> outpoints_value;
63+    outpoints_value.reserve(g_outpoints_coinbase_init_mature.size());
64     for (const auto& outpoint : g_outpoints_coinbase_init_mature) {
65         Assert(mempool_outpoints.insert(outpoint).second);
66         outpoints_value[outpoint] = 50 * COIN;
67@@ -378,7 +386,9 @@
68 
69         // Make packages of 1-to-26 transactions
70         const auto num_txs = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 26);
71-        std::set<COutPoint> package_outpoints;
72+        txs.reserve(num_txs);
73+        std::unordered_set<COutPoint, SaltedOutpointHasher> package_outpoints;
74+        package_outpoints.reserve((num_txs - 1) * 4);
75         while (txs.size() < num_txs) {
76             // Create transaction to add to the mempool
77             txs.emplace_back([&] {
    maflcko commented at 8:22 pm on March 17, 2025:
    mempool_outpoints can’t be changed, because the order matters here. An unordered_set isn’t ordered and may result in a non-deterministic fuzz target, given the same fuzz input.
    l0rinc commented at 8:25 pm on March 17, 2025:
    Ah, that’s what #31457 (review) meant (I assume it applies to package_outpoints as well) - please resolve this comment
    l0rinc commented at 9:21 pm on March 17, 2025:
    Could you please add this conclusion to the PR description, I misinterpreted “the element order is not used in the fuzz test” as meaning the previous related discussions can be skipped :/
    maflcko commented at 1:21 pm on March 18, 2025:
    thx, done
  19. l0rinc commented at 11:43 am on March 17, 2025: contributor

    I will run the tx_package_eval fuzz corpora a bit later, but my previous benchmarks indicated that unordered map/set may not always be faster.

    Is this a correct way to measure the speed difference (on a Mac)?

    0git clone --depth=1 https://github.com/bitcoin-core/qa-assets
1cmake --preset=libfuzzer \
2  -DCMAKE_C_COMPILER="$(brew --prefix llvm)/bin/clang" \
3  -DCMAKE_CXX_COMPILER="$(brew --prefix llvm)/bin/clang++" \
4  -DCMAKE_EXE_LINKER_FLAGS="-fuse-ld=lld"
5cmake --build build_fuzz
6time FUZZ=tx_package_eval build_fuzz/bin/fuzz qa-assets/fuzz_corpora/tx_package_eval
  20. l0rinc referenced this in commit 6f9f415a4f on Mar 17, 2025
  21. Prabhat1308 commented at 1:48 pm on March 17, 2025: none

    Is this a correct way to measure the speed difference (on a Mac)?

    0git clone --depth=1 https://github.com/bitcoin-core/qa-assets
1cmake --preset=libfuzzer\
2   -DCMAKE_C_COMPILER="$(brew --prefix llvm)/bin/clang" \
3   -DCMAKE_CXX_COMPILER="$(brew --prefix llvm)/bin/clang++" \
4   -DCMAKE_EXE_LINKER_FLAGS="-fuse-ld=lld"
5cmake --build build_fuzz
6time FUZZ=tx_package_eval build_fuzz/bin/fuzz qa-assets/fuzz_corpora/tx_package_eval

    Running this (I did not shallow clone but fully cloned) I run into Overflow errors constantly . Am I doing something wrong ?

  22. l0rinc commented at 10:18 pm on March 17, 2025: contributor

    I’ve rebased and ran the tx_package_eval fuzz corpora with a fixed seed before and after this change, 2 times per commit. It indicates a 13% speedup - the suggested additional reserve calls don’t seem to matter at all.

    0git clone --depth=1 https://github.com/bitcoin-core/qa-assets 2>/dev/null || true; \
1COMMITS="86f13e7ab17a9a38172398e09b92bc63a10cc60b 6323f196ca7e69e1052a4c7e7a5beeab0010f8fa fd161bd9fdeced1ee929d86946ee205ea6cc7212"; \
2hyperfine \
3    --export-json "fuzz-benchmark-results-$(date +%Y%m%d-%H%M%S).json" \
4    --runs 2 \
5    --parameter-list COMMIT ${COMMITS// /,} \
6    --prepare "git checkout {COMMIT} && cmake --preset=libfuzzer && cmake --build build_fuzz" \
7    "FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval"

     0# 86f13e7ab1 fuzz: [refactor] Avoid confusing c-style cast
 1Benchmark 1: FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval (COMMIT = 86f13e7ab17a9a38172398e09b92bc63a10cc60b)
 2  Time (mean ± σ):     408.573 s ±  0.250 s    [User: 383.637 s, System: 16.735 s]
 3  Range (min … max):   408.396 s … 408.749 s    2 runs
 4
 5# 6323f196ca fuzz: Speed up *_package_eval fuzz targets a bit
 6Benchmark 2: FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval (COMMIT = 6323f196ca7e69e1052a4c7e7a5beeab0010f8fa)
 7  Time (mean ± σ):     361.642 s ±  1.331 s    [User: 336.472 s, System: 16.928 s]
 8  Range (min … max):   360.701 s … 362.583 s    2 runs
 9 
10# fd161bd9fd fuzz: reserve (PR suggestion without the `std::unordered_set` changes)
11Benchmark 3: FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval (COMMIT = fd161bd9fdeced1ee929d86946ee205ea6cc7212)
12  Time (mean ± σ):     361.922 s ±  0.366 s    [User: 336.748 s, System: 16.933 s]
13  Range (min … max):   361.663 s … 362.181 s    2 runs

    0# Summary
1  FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval (COMMIT = 6323f196ca7e69e1052a4c7e7a5beeab0010f8fa) ran
2    1.00 ± 0.00 times faster than FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval (COMMIT = fd161bd9fdeced1ee929d86946ee205ea6cc7212)
3    1.13 ± 0.00 times faster than FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval (COMMIT = 86f13e7ab17a9a38172398e09b92bc63a10cc60b)

    I have also measured ephemeral_package_eval, since it was also updated here, but it wasn’t that slow to begin with so the change is mostly for consistency, not necessarily an optimization.

     0git clone --depth=1 https://github.com/bitcoin-core/qa-assets 2>/dev/null || true; \
 1COMMITS="86f13e7ab17a9a38172398e09b92bc63a10cc60b 6323f196ca7e69e1052a4c7e7a5beeab0010f8fa fd161bd9fdeced1ee929d86946ee205ea6cc7212"; \
 2hyperfine \
 3    --export-json "fuzz-benchmark-results-$(date +%Y%m%d-%H%M%S).json" \
 4    --runs 2 \
 5    --parameter-list COMMIT ${COMMITS// /,} \
 6    --prepare "git checkout {COMMIT} && cmake --preset=libfuzzer && cmake --build build_fuzz" \
 7    "FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval"
 8    
 9Benchmark 1: FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval (COMMIT = 86f13e7ab17a9a38172398e09b92bc63a10cc60b)
10  Time (mean ± σ):     77.363 s ±  0.078 s    [User: 66.607 s, System: 7.389 s]
11  Range (min … max):   77.308 s … 77.418 s    2 runs
12 
13Benchmark 2: FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval (COMMIT = 6323f196ca7e69e1052a4c7e7a5beeab0010f8fa)
14  Time (mean ± σ):     76.356 s ±  0.546 s    [User: 65.598 s, System: 7.342 s]
15  Range (min … max):   75.970 s … 76.741 s    2 runs
16 
17Benchmark 3: FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval (COMMIT = fd161bd9fdeced1ee929d86946ee205ea6cc7212)
18  Time (mean ± σ):     76.090 s ±  0.138 s    [User: 65.388 s, System: 7.343 s]
19  Range (min … max):   75.992 s … 76.188 s    2 runs
20 
21Summary
22  FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval (COMMIT = fd161bd9fdeced1ee929d86946ee205ea6cc7212) ran
23    1.00 ± 0.01 times faster than FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval (COMMIT = 6323f196ca7e69e1052a4c7e7a5beeab0010f8fa)
24    1.02 ± 0.00 times faster than FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval (COMMIT = 86f13e7ab17a9a38172398e09b92bc63a10cc60b)

    ACK fac3d93c2ba84899c2c6516b5449f61ef653d9fa

  23. fanquake referenced this in commit 6245c23504 on Mar 18, 2025
  24. maflcko requested review from dergoegge on Mar 18, 2025
  25. dergoegge approved
  26. dergoegge commented at 1:53 pm on March 19, 2025: member
    Code review ACK fac3d93c2ba84899c2c6516b5449f61ef653d9fa
  27. fanquake merged this on Mar 20, 2025
  28. fanquake closed this on Mar 20, 2025
  29. maflcko deleted the branch on Mar 20, 2025


maflcko DrahtBot dergoegge l0rinc Prabhat1308

Labels
Tests

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-31 09:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me