bench: Add more realistic Coin Selection Bench

murchandamus commented at 2:17 am on August 9, 2025: contributor

First draft for a Coin Selection Benchmark that doesn’t just test a worst case of one of the algorithms but tries to select inputs for a variety of different targets.

DrahtBot added the label Tests on Aug 9, 2025

DrahtBot commented at 2:18 am on August 9, 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/33160.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	l0rinc

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

DrahtBot added the label CI failed on Aug 9, 2025

DrahtBot commented at 3:18 am on August 9, 2025: contributor

🚧 At least one of the CI tasks failed. Task tidy: https://github.com/bitcoin/bitcoin/runs/47721081968 LLM reason (✨ experimental): clang-tidy detected a performance-inefficient vector operation error, causing the CI to fail.

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.

bench: Add Coin Selection bench with diverse UTXOs 76a4a4b86c

bench: Move setup out of bench 2dfb6d5ebd

murchandamus force-pushed on Aug 18, 2025

in src/bench/coin_selection.cpp:123 in 2dfb6d5ebd

118+    // Add coins.
119+    for (int i = 0; i < 400; ++i) {
120+        int x{det_rand.randrange(100)};
121+        if (x < 50) {
122+            // 0.0001–0.001 COIN
123+            addCoin(det_rand.randrange(90'000) + 10'000, wallet, wtxs);

l0rinc commented at 8:47 pm on August 26, 2025:

we don’t actually need the wallet here, right?

in src/bench/coin_selection.cpp:159 in 2dfb6d5ebd

154+        // 0.1–1 COIN
155+        targets.push_back(det_rand.randrange(90'000'000) + 10'000'000);
156+    }
157+
158+    // Allow actual randomness for selection
159+    FastRandomContext rand{};

l0rinc commented at 9:09 pm on August 26, 2025:

we want deterministic randomness for benchmarks, otherwise it’s hard to know what we’re actually measuring:

0    FastRandomContext rand{/*fDeterministic=*/true};

in src/bench/coin_selection.cpp:153 in 2dfb6d5ebd

148+            available_coins.coins[OutputType::BECH32M].emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/true, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/ 0);
149+        }
150+    }
151+
152+    std::vector<CAmount> targets;
153+    for (int i = 0; i < 100; ++i) {

l0rinc commented at 9:10 pm on August 26, 2025:

we could reserve this to avoid the build failure:

0std::vector<CAmount> targets;
1targets.reserve(10);
2for (size_t i{0}; i < targets.capacity(); ++i) {
3    targets.push_back(rand_range(rng, 0.1_btc, 1_btc));
4}

Note that I have reduced the target count to 10 since the benchmark was very slow otherwise

in src/bench/coin_selection.cpp:102 in 2dfb6d5ebd

 95@@ -99,6 +96,90 @@ static void CoinSelection(benchmark::Bench& bench)
 96     });
 97 }
 98 
 99+// This benchmark is based on a UTXO pool composed of 400 UTXOs. The UTXOs are
100+// pseudorandomly generated to be of the four relevant output types P2PKH,
101+// P2SH-P2WPKH, P2WPKH, and P2TR UTXOs, and fall in the range of 10'000 sats to
102+// 1 ₿ with larger amounts being more likely.

l0rinc commented at 9:13 pm on August 26, 2025:

I’d avoid the Narrow No-Break Space chars from docs if possible, they’re rendered differently on different mediums

in src/bench/coin_selection.cpp:116 in 2dfb6d5ebd

111+    std::vector<std::unique_ptr<CWalletTx>> wtxs;
112+    LOCK(wallet.cs_wallet);
113+
114+    // Use arbitrary static seed for generating a pseudorandom scenario
115+    uint256 arb_seed = uint256("e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855");
116+    FastRandomContext det_rand{arb_seed};

l0rinc commented at 9:15 pm on August 26, 2025:

Same, seems simpler to just leave it to deterministic instead of hard-coding a confusing seed

0    FastRandomContext det_rand{/*fDeterministic=*/true};

note: can we reuse this for the random source below as well?

in src/bench/coin_selection.cpp:141 in 2dfb6d5ebd

136+    // Create coins
137+    wallet::CoinsResult available_coins;
138+    for (const auto& wtx : wtxs) {
139+        const auto txout = wtx->tx->vout.at(0);
140+        int y{det_rand.randrange(100)};
141+        if (y < 35) {

l0rinc commented at 9:18 pm on August 26, 2025:

we could dedup considerable here for better signal-to-noise ratio - it’s a lot of work to find the differences between the values:

 0for (const auto& wtx : wtxs) {
 1    const auto txout{wtx->tx->vout.at(0)};
 2    const int input_bytes{CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr)};
 3    const COutput output{(COutPoint{wtx->GetHash(), 0}), txout, /*depth=*/6 * 24, input_bytes, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/0};
 4    if (int y{rng.randrange(100)}; y < 35) {
 5        available_coins.coins[OutputType::LEGACY].push_back(output);
 6    } else if (y < 55) {
 7        available_coins.coins[OutputType::P2SH_SEGWIT].push_back(output);
 8    } else if (y < 90) {
 9        available_coins.coins[OutputType::BECH32].push_back(output);
10    } else {
11        available_coins.coins[OutputType::BECH32M].push_back(output);
12    }
13}

or even more thoroghly:

 0for (const auto& wtx : wtxs) {
 1    const int p{rand_percentage(rng)};
 2    auto val{p < 35 ? OutputType::LEGACY :
 3             p < 55 ? OutputType::P2SH_SEGWIT :
 4             p < 90 ? OutputType::BECH32 :
 5                      OutputType::BECH32M};
 6
 7    const auto txout{wtx->tx->vout.at(0)};
 8    const int input_bytes{CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr)};
 9    const COutput output{COutPoint{wtx->GetHash(), 0}, txout, /*depth=*/6 * 24, input_bytes, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/0};
10    available_coins.coins[val].emplace_back(output);
11}

in src/bench/coin_selection.cpp:142 in 2dfb6d5ebd

137+    wallet::CoinsResult available_coins;
138+    for (const auto& wtx : wtxs) {
139+        const auto txout = wtx->tx->vout.at(0);
140+        int y{det_rand.randrange(100)};
141+        if (y < 35) {
142+            available_coins.coins[OutputType::LEGACY].emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/true, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/ 0);

l0rinc commented at 9:22 pm on August 26, 2025:

Please rebase, spendable was removed since: https://github.com/bitcoin/bitcoin/commit/6a7aa015747e2634fe5a4b2f7fa0d104eb75c796#diff-38f1a8db124a979cb6dd76ce263f7aae0053d6967ee909e6356115fa0402dc8cL78

in src/bench/coin_selection.cpp:155 in 2dfb6d5ebd

150+    }
151+
152+    std::vector<CAmount> targets;
153+    for (int i = 0; i < 100; ++i) {
154+        // 0.1–1 COIN
155+        targets.push_back(det_rand.randrange(90'000'000) + 10'000'000);

l0rinc commented at 9:30 pm on August 26, 2025:

nit: since you’re also mentioning the minimum in the comment first, we might as well put the fixed size first here

0        targets.push_back(10'000'000 + det_rand.randrange(90'000'000));

Alternatively, to avoid all the 0s, consider:

0        targets.push_back(COIN / 10 + rng.randrange(COIN / 9 * 10));

This would unify it with the rest of the usages.

this has come up multiple times, we should really add a randrange helper with min/max values - but for now we can just do that here to make the test itself as clear as possible (we have a lot of comments, indicating that the code needed extra explanation, so let’s clear up the code instead and remove comments)

 0namespace {
 1constexpr CAmount operator""_sat(uint64_t v) { return v; }
 2constexpr CAmount operator""_ksat(uint64_t v) { return v * 1'000; }
 3constexpr CAmount operator""_btc(uint64_t v) { return v * COIN; }
 4constexpr CAmount operator""_btc(long double v) { return std::llround(v * COIN); }
 5// TODO if you don't trust doubles this could also work
 6constexpr CAmount operator""_btc(const char* s, size_t n) { CAmount a{0}; assert(ParseFixedPoint(std::string{s, n}, 8, &a)); return a; } 
 7
 8int rand_percentage(FastRandomContext& rng) { return rng.randrange(101); }
 9CAmount rand_range(FastRandomContext& rng, CAmount lo, CAmount hi) { return lo + rng.randrange(hi - lo + 1); }
10} // namespace

which would simplify the above to

0        targets.push_back(rand_range(rng, 0.1_btc, 1_btc));

in src/bench/coin_selection.cpp:184 in 2dfb6d5ebd

179+        }
180+    });
181+}
182+
183 // Copied from src/wallet/test/coinselector_tests.cpp
184 static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>& set)

l0rinc commented at 9:35 pm on August 26, 2025:

nInput should be uint32_t otherwise we’d have a narrowing conversion in OutPoint{tx.GetHash(), nInput}

in src/bench/coin_selection.cpp:132 in 76a4a4b86c outdated

127+        } else if (x < 95) {
128+            // 0.01–0.1 COIN
129+            addCoin(det_rand.randrange(9'000'000) + 1'000'000, wallet, wtxs);
130+        } else {
131+            // 0.1–1 COIN
132+            addCoin(det_rand.randrange(90'000'000) + 10'000'000, wallet, wtxs);

l0rinc commented at 10:13 pm on August 26, 2025:

we could also separate the parts that change from the parts that don’t, to improve readability by reducing number of moving parts:

 0for (int i{0}; i < 400; ++i) {
 1    CAmount val;
 2    if (int p{rand_percentage(rng)}; p < 50) {
 3        val = rand_range(rng, 10_ksat, 100_ksat);
 4    } else if (p < 75) {
 5        val = rand_range(rng, 100_ksat, 1_Msat);
 6    } else if (p < 95) {
 7        val = rand_range(rng, 1_Msat, 10_Msat);
 8    } else {
 9        val = rand_range(rng, 0.1_btc, 1_btc);
10    }
11    addCoin(val, wtxs);
12}

or

0for (int i{0}; i < 400; ++i) {
1    const int p{rand_percentage(rng)};
2    const auto val{p < 50 ? rand_range(rng, 10_ksat, 100_ksat) :
3                   p < 75 ? rand_range(rng, 100_ksat, 1_Msat) :
4                   p < 95 ? rand_range(rng, 1_Msat, 10_Msat) :
5                            rand_range(rng, 0.1_btc, 1_btc)};
6    addCoin(val, wtxs);
7}

in src/bench/coin_selection.cpp:212 in 2dfb6d5ebd

204@@ -205,16 +205,12 @@ static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
205 
206 static void BnBExhaustion(benchmark::Bench& bench)
207 {
208-    // Setup
209     std::vector<OutputGroup> utxo_pool;
210 
211+    CAmount target = make_hard_case(17, utxo_pool);
212     bench.run([&] {
213         // Benchmark

l0rinc commented at 10:47 pm on August 26, 2025:

we don’t have to keep this comment either in 2dfb6d5ebdb579f58244534835f027cd11187ae3

in src/bench/coin_selection.cpp:213 in 2dfb6d5ebd

210 
211+    CAmount target = make_hard_case(17, utxo_pool);
212     bench.run([&] {
213         // Benchmark
214-        CAmount target = make_hard_case(17, utxo_pool);
215         SelectCoinsBnB(utxo_pool, target, 0, MAX_STANDARD_TX_WEIGHT); // Should exhaust

l0rinc commented at 10:47 pm on August 26, 2025:

Should exhaust - can we assert that instead of adding a dead comment?

in src/bench/coin_selection.cpp:104 in 76a4a4b86c outdated

 95@@ -99,6 +96,90 @@ static void CoinSelection(benchmark::Bench& bench)
 96     });
 97 }
 98 
 99+// This benchmark is based on a UTXO pool composed of 400 UTXOs. The UTXOs are
100+// pseudorandomly generated to be of the four relevant output types P2PKH,
101+// P2SH-P2WPKH, P2WPKH, and P2TR UTXOs, and fall in the range of 10'000 sats to
102+// 1 ₿ with larger amounts being more likely.
103+// This UTXO pool is used to run coin selection for 100 pseudorandom selection
104+// targets from 0.1–2 ₿. Altogether, this gives us a deterministic benchmark

l0rinc commented at 10:55 pm on August 26, 2025:

where are we adding 2 btc? Could we avoid values from the comments, they’re just adding a maintenance burden when we’re forgetting updating them

in src/bench/coin_selection.cpp:176 in 76a4a4b86c outdated

171+    };
172+    auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard];
173+
174+    bench.run([&] {
175+        for (const auto& target : targets) {
176+            auto result = AttemptSelection(wallet.chain(), target, group, coin_selection_params, /*allow_mixed_output_types=*/true);

l0rinc commented at 11:18 pm on August 26, 2025:

For the record, Knapsack and CoinsBnB are really slow (with debug build to avoid all the inlining), making this whole benchmark one of our heaviest - could we reduce some of the iterations?

in src/bench/coin_selection.cpp:163 in 76a4a4b86c outdated

158+    // Allow actual randomness for selection
159+    FastRandomContext rand{};
160+    const CoinEligibilityFilter filter_standard(1, 6, 0);
161+    const CoinSelectionParams coin_selection_params{
162+        rand,
163+        /*change_output_size=*/ 31,

l0rinc commented at 11:56 pm on August 26, 2025:

nit: let’s unify the comment styles across the file

l0rinc changes_requested

l0rinc commented at 0:00 am on August 27, 2025: contributor

Concept ACK, the existing test were all quite trivial compared to this new one. I left a ton of comments, for simplicity here’s the final code that I’m suggesting, feel free to pick and choose from it.

  0// Copyright (c) 2012-2022 The Bitcoin Core developers
  1// Distributed under the MIT software license, see the accompanying
  2// file COPYING or http://www.opensource.org/licenses/mit-license.php.
  3
  4#include <bench/bench.h>
  5#include <consensus/amount.h>
  6#include <interfaces/chain.h>
  7#include <node/context.h>
  8#include <outputtype.h>
  9#include <policy/feerate.h>
 10#include <policy/policy.h>
 11#include <primitives/transaction.h>
 12#include <random.h>
 13#include <sync.h>
 14#include <util/result.h>
 15#include <wallet/coinselection.h>
 16#include <wallet/spend.h>
 17#include <wallet/test/util.h>
 18#include <wallet/transaction.h>
 19#include <wallet/wallet.h>
 20
 21#include <cassert>
 22#include <map>
 23#include <memory>
 24#include <set>
 25#include <utility>
 26#include <vector>
 27#include <cmath>
 28
 29using node::NodeContext;
 30using wallet::AttemptSelection;
 31using wallet::CHANGE_LOWER;
 32using wallet::COutput;
 33using wallet::CWallet;
 34using wallet::CWalletTx;
 35using wallet::CoinEligibilityFilter;
 36using wallet::CoinSelectionParams;
 37using wallet::CreateMockableWalletDatabase;
 38using wallet::OutputGroup;
 39using wallet::SelectCoinsBnB;
 40using wallet::TxStateInactive;
 41
 42namespace {
 43constexpr CAmount operator""_sat(uint64_t v) { return v; }
 44constexpr CAmount operator""_ksat(uint64_t v) { return v * 1'000; }
 45constexpr CAmount operator""_btc(uint64_t v) { return v * COIN; }
 46constexpr CAmount operator""_btc(long double v) { return std::llround(v * COIN); }
 47
 48int rand_percentage(FastRandomContext& rng) { return rng.randrange(100); }
 49CAmount rand_range(FastRandomContext& rng, CAmount lo, CAmount hi) { return lo + rng.randrange(hi - lo + 1); }
 50} // namespace
 51
 52static void addCoin(CAmount nValue, std::vector<std::unique_ptr<CWalletTx>>& wtxs)
 53{
 54    static int nextLockTime = 0;
 55    CMutableTransaction tx;
 56    tx.nLockTime = nextLockTime++; // so all transactions get different hashes
 57    tx.vout.resize(1);
 58    tx.vout[0].nValue = nValue;
 59    wtxs.push_back(std::make_unique<CWalletTx>(MakeTransactionRef(std::move(tx)), TxStateInactive{}));
 60}
 61
 62// Simple benchmark for wallet coin selection that exercises a worst-case
 63// scenario for Knapsack: All UTXOs are necessary, but it is not an exact
 64// match, so the only eligible input set is only discovered on the second pass
 65// after all random walks fail to produce a solution.
 66static void KnapsackWorstCase(benchmark::Bench& bench)
 67{
 68    NodeContext node;
 69    auto chain{interfaces::MakeChain(node)};
 70    CWallet wallet(chain.get(), "", CreateMockableWalletDatabase());
 71    std::vector<std::unique_ptr<CWalletTx>> wtxs;
 72    LOCK(wallet.cs_wallet);
 73
 74    for (int i{0}; i < 1000; ++i) {
 75        addCoin(1000_btc, wtxs);
 76    }
 77    addCoin(3_btc, wtxs);
 78
 79    // Create coins
 80    wallet::CoinsResult available_coins;
 81    for (const auto& wtx : wtxs) {
 82        const auto txout{wtx->tx->vout.at(0)};
 83        const int input_bytes{CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr)};
 84        const COutput output{COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, input_bytes, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/0};
 85        available_coins.coins[OutputType::BECH32].emplace_back(output);
 86    }
 87
 88    const CoinEligibilityFilter filter_standard(1, 6, 0);
 89    FastRandomContext rand{/*fDeterministic=*/true};
 90    const CoinSelectionParams coin_selection_params{
 91        rand,
 92        /*change_output_size=*/34,
 93        /*change_spend_size=*/148,
 94        /*min_change_target=*/CHANGE_LOWER,
 95        /*effective_feerate=*/CFeeRate(20'000),
 96        /*long_term_feerate=*/CFeeRate(10'000),
 97        /*discard_feerate=*/CFeeRate(3000),
 98        /*tx_noinputs_size=*/0,
 99        /*avoid_partial=*/false,
100    };
101    auto group{wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard]};
102    bench.run([&] {
103        auto result{AttemptSelection(wallet.chain(), 1002.99_btc, group, coin_selection_params, /*allow_mixed_output_types=*/true)};
104        assert(result);
105        assert(result->GetSelectedValue() == 1003_btc);
106        assert(result->GetInputSet().size() == 2);
107    });
108}
109
110// This benchmark is based on a UTXO pool composed of 400 UTXOs. The UTXOs are
111// pseudorandomly generated to be of the four relevant output types P2PKH,
112// P2SH-P2WPKH, P2WPKH, and P2TR UTXOs, and fall in the range of 10'000 sats to
113// 1₿ with larger amounts being more likely.
114// This UTXO pool is used to run coin selection for 100 pseudorandom selection
115// targets from 0.1–2₿. Altogether, this gives us a deterministic benchmark
116// with a hopefully somewhat representative coin selection scenario.
117static void CoinSelectionOnDiverseWallet(benchmark::Bench& bench)
118{
119    FastRandomContext rng{/*fDeterministic=*/true};
120
121    NodeContext node;
122    auto chain{interfaces::MakeChain(node)};
123    CWallet wallet(chain.get(), "", CreateMockableWalletDatabase());
124    LOCK(wallet.cs_wallet);
125
126    std::vector<std::unique_ptr<CWalletTx>> wtxs;
127    wtxs.reserve(400);
128    for (size_t i{0}; i < wtxs.capacity(); ++i) {
129        const int p{rand_percentage(rng)};
130        const auto val{p < 50 ? rand_range(rng, 10_ksat, 100_ksat) :
131                       p < 75 ? rand_range(rng, 100_ksat, 1000_ksat) :
132                       p < 95 ? rand_range(rng, 1000_ksat, 1_btc) :
133                                rand_range(rng, 0.1_btc, 1_btc)};
134        addCoin(val, wtxs);
135    }
136
137    // Create coins
138    wallet::CoinsResult available_coins;
139    for (const auto& wtx : wtxs) {
140        const int p{rand_percentage(rng)};
141        auto val{p < 35 ? OutputType::LEGACY :
142                 p < 55 ? OutputType::P2SH_SEGWIT :
143                 p < 90 ? OutputType::BECH32 :
144                          OutputType::BECH32M};
145
146        const auto txout{wtx->tx->vout.at(0)};
147        const int input_bytes{CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr)};
148        const COutput output{COutPoint{wtx->GetHash(), 0}, txout, /*depth=*/6 * 24, input_bytes, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/0};
149        available_coins.coins[val].emplace_back(output);
150    }
151
152    std::vector<CAmount> targets;
153    targets.reserve(10);
154    for (size_t i{0}; i < targets.capacity(); ++i) {
155        targets.push_back(rand_range(rng, 0.1_btc, 1_btc));
156    }
157
158    const CoinSelectionParams coin_selection_params{
159        rng,
160        /*change_output_size=*/31,
161        /*change_spend_size=*/68,
162        /*min_change_target=*/CHANGE_LOWER,
163        /*effective_feerate=*/CFeeRate(20'000),
164        /*long_term_feerate=*/CFeeRate(10'000),
165        /*discard_feerate=*/CFeeRate(3000),
166        /*tx_noinputs_size=*/72,
167        /*avoid_partial=*/false,
168    };
169    const CoinEligibilityFilter filter_standard(1, 6, 0);
170    auto group{wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard]};
171
172    bench.run([&] {
173        for (const auto& target : targets) {
174            auto result{AttemptSelection(wallet.chain(), target, group, coin_selection_params, /*allow_mixed_output_types=*/true)};
175            assert(result && result->GetSelectedValue() >= target);
176        }
177    });
178}
179
180static void add_coin(CAmount nValue, uint32_t nInput, std::vector<OutputGroup>& set)
181{
182    CMutableTransaction tx;
183    tx.vout.resize(nInput + 1);
184    tx.vout[nInput].nValue = nValue;
185    COutput output(COutPoint{tx.GetHash(), nInput}, tx.vout.at(nInput), /*depth=*/0, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/true, /*fees=*/0);
186    set.emplace_back();
187    set.back().Insert(std::make_shared<COutput>(output), /*ancestors=*/0, /*descendants=*/0);
188}
189
190static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
191{
192    utxo_pool.clear();
193    CAmount target{0};
194    for (int i{0}; i < utxos; ++i) {
195        target += 1_sat << (utxos + i);
196        add_coin(1_sat << (utxos + i), 2 * i, utxo_pool);
197        add_coin((1_sat << (utxos + i)) + (1_sat << (utxos - 1 - i)), 2 * i + 1, utxo_pool);
198    }
199    return target;
200}
201
202static void BnBExhaustion(benchmark::Bench& bench)
203{
204    std::vector<OutputGroup> utxo_pool;
205    auto target{make_hard_case(17, utxo_pool)};
206    bench.run([&] {
207        SelectCoinsBnB(utxo_pool, target, 0, MAX_STANDARD_TX_WEIGHT); // Should exhaust
208    });
209}
210
211BENCHMARK(KnapsackWorstCase, benchmark::PriorityLevel::HIGH);
212BENCHMARK(CoinSelectionOnDiverseWallet, benchmark::PriorityLevel::HIGH);
213BENCHMARK(BnBExhaustion, benchmark::PriorityLevel::HIGH);

bench: Add more realistic Coin Selection Bench #33160

Code Coverage & Benchmarks

Reviews