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.)
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--006a51241073e994b41acfe9ec718e94-->
For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/31457.
<!--021abf342d371248e50ceaed478a90ca-->
See the guideline for information on the review process.
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.
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;
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.
Good catch. This means:
Reopened this pull request and dropped the changes to mempool_outpoints for now.
I've kept the changes to outpoints_value, because:
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.
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;
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:
<details> <summary>`CheckBlockBench` measurements repeated 3x</summary>
std::set<COutPoint> 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
</details>
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.
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;
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.
<details> <summary>Details</summary>
diff --git a/src/test/fuzz/package_eval.cpp b/src/test/fuzz/package_eval.cpp
--- a/src/test/fuzz/package_eval.cpp (revision 147655098edde6feffbbe2c601d5874a7d3a3c5c)
+++ b/src/test/fuzz/package_eval.cpp (date 1742211475064)
@@ -57,9 +57,9 @@
}
struct OutpointsUpdater final : public CValidationInterface {
- std::set<COutPoint>& m_mempool_outpoints;
+ std::unordered_set<COutPoint, SaltedOutpointHasher>& m_mempool_outpoints;
- explicit OutpointsUpdater(std::set<COutPoint>& r)
+ explicit OutpointsUpdater(std::unordered_set<COutPoint, SaltedOutpointHasher>& r)
: m_mempool_outpoints{r} {}
void TransactionAddedToMempool(const NewMempoolTransactionInfo& tx, uint64_t /* mempool_sequence */) override
@@ -67,6 +67,7 @@
// for coins spent we always want to be able to rbf so they're not removed
// outputs from this tx can now be spent
+ m_mempool_outpoints.reserve(m_mempool_outpoints.size() + tx.info.m_tx->vout.size());
for (uint32_t index{0}; index < tx.info.m_tx->vout.size(); ++index) {
m_mempool_outpoints.insert(COutPoint{tx.info.m_tx->GetHash(), index});
}
@@ -75,6 +76,7 @@
void TransactionRemovedFromMempool(const CTransactionRef& tx, MemPoolRemovalReason reason, uint64_t /* mempool_sequence */) override
{
// outpoints spent by this tx are now available
+ m_mempool_outpoints.reserve(m_mempool_outpoints.size() + tx->vin.size());
for (const auto& input : tx->vin) {
// Could already exist if this was a replacement
m_mempool_outpoints.insert(input.prevout);
@@ -200,8 +202,10 @@
MockTime(fuzzed_data_provider, chainstate);
// All RBF-spendable outpoints outside of the unsubmitted package
- std::set<COutPoint> mempool_outpoints;
+ std::unordered_set<COutPoint, SaltedOutpointHasher> mempool_outpoints;
+ mempool_outpoints.reserve(g_outpoints_coinbase_init_mature.size());
std::unordered_map<COutPoint, CAmount, SaltedOutpointHasher> outpoints_value;
+ outpoints_value.reserve(g_outpoints_coinbase_init_mature.size());
for (const auto& outpoint : g_outpoints_coinbase_init_mature) {
Assert(mempool_outpoints.insert(outpoint).second);
outpoints_value[outpoint] = 50 * COIN;
@@ -226,8 +230,10 @@
// Make small packages
const auto num_txs = outpoint_to_rbf ? 1 : fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 4);
+ txs.reserve(num_txs);
- std::set<COutPoint> package_outpoints;
+ std::unordered_set<COutPoint, SaltedOutpointHasher> package_outpoints;
+ package_outpoints.reserve((num_txs - 1) * 4);
while (txs.size() < num_txs) {
// Create transaction to add to the mempool
txs.emplace_back([&] {
@@ -355,8 +361,10 @@
MockTime(fuzzed_data_provider, chainstate);
// All RBF-spendable outpoints outside of the unsubmitted package
- std::set<COutPoint> mempool_outpoints;
+ std::unordered_set<COutPoint, SaltedOutpointHasher> mempool_outpoints;
+ mempool_outpoints.reserve(g_outpoints_coinbase_init_mature.size());
std::unordered_map<COutPoint, CAmount, SaltedOutpointHasher> outpoints_value;
+ outpoints_value.reserve(g_outpoints_coinbase_init_mature.size());
for (const auto& outpoint : g_outpoints_coinbase_init_mature) {
Assert(mempool_outpoints.insert(outpoint).second);
outpoints_value[outpoint] = 50 * COIN;
@@ -378,7 +386,9 @@
// Make packages of 1-to-26 transactions
const auto num_txs = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 26);
- std::set<COutPoint> package_outpoints;
+ txs.reserve(num_txs);
+ std::unordered_set<COutPoint, SaltedOutpointHasher> package_outpoints;
+ package_outpoints.reserve((num_txs - 1) * 4);
while (txs.size() < num_txs) {
// Create transaction to add to the mempool
txs.emplace_back([&] {
</details>
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.
Ah, that's what #31457 (review) meant (I assume it applies to package_outpoints as well) - please resolve this comment
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 :/
thx, done
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)?
git clone --depth=1 https://github.com/bitcoin-core/qa-assets
cmake --preset=libfuzzer \
-DCMAKE_C_COMPILER="$(brew --prefix llvm)/bin/clang" \
-DCMAKE_CXX_COMPILER="$(brew --prefix llvm)/bin/clang++" \
-DCMAKE_EXE_LINKER_FLAGS="-fuse-ld=lld"
cmake --build build_fuzz
time FUZZ=tx_package_eval build_fuzz/bin/fuzz qa-assets/fuzz_corpora/tx_package_eval
Is this a correct way to measure the speed difference (on a Mac)?
git clone --depth=1 https://github.com/bitcoin-core/qa-assets cmake --preset=libfuzzer\ -DCMAKE_C_COMPILER="$(brew --prefix llvm)/bin/clang" \ -DCMAKE_CXX_COMPILER="$(brew --prefix llvm)/bin/clang++" \ -DCMAKE_EXE_LINKER_FLAGS="-fuse-ld=lld" cmake --build build_fuzz time 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 ?
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.
<details> <summary>Reproducer benchmark</summary>
git clone --depth=1 https://github.com/bitcoin-core/qa-assets 2>/dev/null || true; \
COMMITS="86f13e7ab17a9a38172398e09b92bc63a10cc60b 6323f196ca7e69e1052a4c7e7a5beeab0010f8fa fd161bd9fdeced1ee929d86946ee205ea6cc7212"; \
hyperfine \
--export-json "fuzz-benchmark-results-$(date +%Y%m%d-%H%M%S).json" \
--runs 2 \
--parameter-list COMMIT ${COMMITS// /,} \
--prepare "git checkout {COMMIT} && cmake --preset=libfuzzer && cmake --build build_fuzz" \
"FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval"
</details>
<details> <summary>Measurements</summary>
# 86f13e7ab1 fuzz: [refactor] Avoid confusing c-style cast
Benchmark 1: FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval (COMMIT = 86f13e7ab17a9a38172398e09b92bc63a10cc60b)
Time (mean ± σ): 408.573 s ± 0.250 s [User: 383.637 s, System: 16.735 s]
Range (min … max): 408.396 s … 408.749 s 2 runs
# 6323f196ca fuzz: Speed up *_package_eval fuzz targets a bit
Benchmark 2: FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval (COMMIT = 6323f196ca7e69e1052a4c7e7a5beeab0010f8fa)
Time (mean ± σ): 361.642 s ± 1.331 s [User: 336.472 s, System: 16.928 s]
Range (min … max): 360.701 s … 362.583 s 2 runs
# fd161bd9fd fuzz: reserve (PR suggestion without the `std::unordered_set` changes)
Benchmark 3: FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval (COMMIT = fd161bd9fdeced1ee929d86946ee205ea6cc7212)
Time (mean ± σ): 361.922 s ± 0.366 s [User: 336.748 s, System: 16.933 s]
Range (min … max): 361.663 s … 362.181 s 2 runs
</details>
# Summary
FUZZ=tx_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/tx_package_eval (COMMIT = 6323f196ca7e69e1052a4c7e7a5beeab0010f8fa) ran
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)
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.
<details> <summary>Measurements</summary>
git clone --depth=1 https://github.com/bitcoin-core/qa-assets 2>/dev/null || true; \
COMMITS="86f13e7ab17a9a38172398e09b92bc63a10cc60b 6323f196ca7e69e1052a4c7e7a5beeab0010f8fa fd161bd9fdeced1ee929d86946ee205ea6cc7212"; \
hyperfine \
--export-json "fuzz-benchmark-results-$(date +%Y%m%d-%H%M%S).json" \
--runs 2 \
--parameter-list COMMIT ${COMMITS// /,} \
--prepare "git checkout {COMMIT} && cmake --preset=libfuzzer && cmake --build build_fuzz" \
"FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval"
Benchmark 1: FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval (COMMIT = 86f13e7ab17a9a38172398e09b92bc63a10cc60b)
Time (mean ± σ): 77.363 s ± 0.078 s [User: 66.607 s, System: 7.389 s]
Range (min … max): 77.308 s … 77.418 s 2 runs
Benchmark 2: FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval (COMMIT = 6323f196ca7e69e1052a4c7e7a5beeab0010f8fa)
Time (mean ± σ): 76.356 s ± 0.546 s [User: 65.598 s, System: 7.342 s]
Range (min … max): 75.970 s … 76.741 s 2 runs
Benchmark 3: FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval (COMMIT = fd161bd9fdeced1ee929d86946ee205ea6cc7212)
Time (mean ± σ): 76.090 s ± 0.138 s [User: 65.388 s, System: 7.343 s]
Range (min … max): 75.992 s … 76.188 s 2 runs
Summary
FUZZ=ephemeral_package_eval build_fuzz/bin/fuzz -seed=914696157 -runs=1 qa-assets/fuzz_corpora/ephemeral_package_eval (COMMIT = fd161bd9fdeced1ee929d86946ee205ea6cc7212) ran
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)
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)
</details>
ACK fac3d93c2ba84899c2c6516b5449f61ef653d9fa
Code review ACK fac3d93c2ba84899c2c6516b5449f61ef653d9fa