bench: Add more realistic Coin Selection Bench

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

Adds a Coin Selection benchmark that doesn’t just test a worst case of one of the algorithms but exercises coin selection to to select inputs for a variety of different targets from a large number of UTXOs.

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 copy-paste <!–meta-tag:bot-skip–> into the comment that the bot should ignore.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#34208 (bench: add fluent API for untimed setup steps in nanobench by l0rinc)
#33032 (wallet, test: Replace MockableDatabase with in-memory SQLiteDatabase by achow101)

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.

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.

murchandamus force-pushed on Aug 18, 2025

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

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?

murchandamus commented at 8:43 pm on March 9, 2026:

Removed the wallet argument from addCoin(…)

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

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};

murchandamus commented at 7:40 pm on March 9, 2026:

Taken

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

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

murchandamus commented at 7:49 pm on March 9, 2026:

I reduced it to ten targets and added the reserve statement.

l0rinc commented at 3:26 pm on March 13, 2026:

I realized that looping to targets.capacity() is not a stable way to cap this benchmark at 10 targets, since the reservation is often rounded up to powers of two. We should extract the target count to a constant instead:

0constexpr size_t NUM_TARGETS{10};
1std::vector<CAmount> targets;
2targets.reserve(NUM_TARGETS);
3for (size_t i{0}; i < NUM_TARGETS; ++i) {
4    targets.push_back(10'000'000 + det_rand.randrange(90'000'000));
5}

Which would also allow us to make the benchmark average out the batch:

0bench.batch(NUM_TARGETS).run([&] {

in src/bench/coin_selection.cpp:102 in 2dfb6d5ebd 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.

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

murchandamus commented at 6:50 pm on March 9, 2026:

Okay, replaced with regular spaces.

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

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?

murchandamus commented at 7:03 pm on March 9, 2026:

Took your suggestion.

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

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}

murchandamus commented at 8:24 pm on March 9, 2026:

Nice idea. I realized that the weight was actually -1 everywhere and instead assigned weight and fees as intended.

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

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

murchandamus commented at 7:49 pm on March 9, 2026:

I removed the spendable arguments.

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

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));

murchandamus commented at 8:29 pm on March 9, 2026:

I switched the minimum and random part as suggested. I find the straight-up sat amounts more readable than mixing multiple units or the suffix construction, so I left that as was.

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

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}

murchandamus commented at 8:29 pm on March 9, 2026:

Changed to uint32_t

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}

murchandamus commented at 8:35 pm on March 9, 2026:

Took a variant of the first

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

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

murchandamus commented at 8:30 pm on March 9, 2026:

Removed the comment

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

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?

murchandamus commented at 8:32 pm on March 9, 2026:

We currently don’t have access to whether the search concluded or was interrupted early. I propose that we return it with the changes in #32150, and when that gets adopted, we could check here.

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

murchandamus commented at 7:01 pm on March 9, 2026:

I rewrote the paragraph avoiding numbers.

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?

murchandamus commented at 7:39 pm on March 9, 2026:

Reduced to ten iterations as you suggested.

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

murchandamus commented at 8:35 pm on March 9, 2026:

I replaced all instances of the space between the comment and value in this document. Please let me know if there was something else that I missed.

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);

maflcko removed the label CI failed on Sep 26, 2025

DrahtBot added the label Needs rebase on Dec 9, 2025

murchandamus force-pushed on Mar 8, 2026

DrahtBot added the label CI failed on Mar 8, 2026

DrahtBot commented at 8:53 pm on March 8, 2026: contributor

🚧 At least one of the CI tasks failed. Task test ancestor commits: https://github.com/bitcoin/bitcoin/actions/runs/22828405687/job/66212445052 LLM reason (✨ experimental): Compilation errors in bench_bitcoin (coin_selection.cpp) caused the build 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.

DrahtBot removed the label Needs rebase on Mar 8, 2026

murchandamus commented at 8:57 pm on March 9, 2026: member

Thanks for your comments, @l0rinc.

murchandamus force-pushed on Mar 9, 2026

DrahtBot removed the label CI failed on Mar 9, 2026

murchandamus force-pushed on Mar 12, 2026

murchandamus marked this as ready for review on Mar 12, 2026

murchandamus requested review from l0rinc on Mar 12, 2026

in src/bench/coin_selection.cpp:78 in 8b0ab66156

76-        available_coins.coins[OutputType::BECH32].emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/ 0);
77+        available_coins.coins[OutputType::BECH32].emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/0);
78     }
79 
80     const CoinEligibilityFilter filter_standard(1, 6, 0);
81     FastRandomContext rand{};

l0rinc commented at 3:40 pm on March 13, 2026:

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

murchandamus commented at 9:32 pm on March 13, 2026:

Taken

in src/bench/coin_selection.cpp:77 in 8b0ab66156

75         const auto txout = wtx->tx->vout.at(0);
76-        available_coins.coins[OutputType::BECH32].emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/ 0);
77+        available_coins.coins[OutputType::BECH32].emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/0);
78     }
79 
80     const CoinEligibilityFilter filter_standard(1, 6, 0);

l0rinc commented at 3:44 pm on March 13, 2026:

Could add helpers to a few more places:

0    const CoinEligibilityFilter filter_standard(/*conf_mine=*/1, /*conf_theirs=*/6, /*max_ancestors=*/0);

murchandamus commented at 9:30 pm on March 13, 2026:

Taken

in src/bench/coin_selection.cpp:101 in 8b0ab66156

 95@@ -99,15 +96,103 @@ static void CoinSelection(benchmark::Bench& bench)
 96     });
 97 }
 98 
 99+// This benchmark is based on a UTXO pool composed of hundreds of UTXOs. The
100+// UTXOs are pseudorandomly generated to be of the four relevant output types
101+// P2PKH, P2SH-P2WPKH, P2WPKH, and P2TR UTXOs.

l0rinc commented at 3:54 pm on March 13, 2026:

nit: the benchmark doesn’t actually generate UTXOs of those script types:

0// The UTXOs are pseudorandomly generated and assigned one of the four
1// relevant output types: P2PKH, P2SH-P2WPKH, P2WPKH, and P2TR.

murchandamus commented at 9:30 pm on March 13, 2026:

Taken

in src/bench/coin_selection.cpp:180 in 8b0ab66156 outdated

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

l0rinc commented at 4:03 pm on March 13, 2026:

nit: is /*allow_mixed_output_types=*/false maybe more accurate here? We basically always return at https://github.com/bitcoin/bitcoin/blob/3a222507fd4d61c4ac8b4506343a345d66ee76b1/src/wallet/spend.cpp#L716 (is that deliberate?), which means that https://github.com/bitcoin/bitcoin/blob/3a222507fd4d61c4ac8b4506343a345d66ee76b1/src/wallet/spend.cpp#L716-L723 is basically never executed.

murchandamus commented at 8:29 pm on March 13, 2026:

Given the random targets and random UTXOs, it would be possible for all output types by themselves not to have sufficient funds to produce a solution. In that case, we would fall back to mix the UTXOs and select from all of them together. This is very unlikely with 400 UTXOs, but still seems correct to me.

in src/bench/coin_selection.cpp:122 in 8b0ab66156

117+    for (int i = 0; i < 400; ++i) {
118+        CAmount amount;
119+        int p{det_rand.randrange(100)};
120+        if (p < 50) {
121+            amount = 10'000 + det_rand.randrange(90'000);
122+        } else if (p < 75)  {

l0rinc commented at 4:04 pm on March 13, 2026:

0        } else if (p < 75) {

in src/bench/coin_selection.cpp:187 in 8b0ab66156

182+            assert(result->GetSelectedValue() >= target);
183+        }
184+    });
185+}
186+
187 // Copied from src/wallet/test/coinselector_tests.cpp

l0rinc commented at 4:04 pm on March 13, 2026:

are these Copied from comments useful?

murchandamus commented at 9:17 pm on March 13, 2026:

Removed.

in src/bench/coin_selection.cpp:162 in 8b0ab66156

157+    targets.reserve(10);
158+    for (size_t i{0}; i < targets.capacity(); ++i) {
159+        targets.push_back(10'000'000 + det_rand.randrange(90'000'000));
160+    }
161+
162+    // Allow actual randomness for selection

l0rinc commented at 4:06 pm on March 13, 2026:

0    // Keep selection deterministic for benchmark stability

murchandamus commented at 10:20 pm on March 13, 2026:

Put above det_rand

in src/bench/coin_selection.cpp:92 in 8b0ab66156

l0rinc commented at 4:17 pm on March 13, 2026:

slightly unrelated: we could maybe change floating point here to avoid potential weirdness:

0auto result = AttemptSelection(wallet.chain(), 1002 * COIN + 99 * CENT, group, coin_selection_params, /*allow_mixed_output_types=*/true);

or

0auto result = AttemptSelection(wallet.chain(), 100'299'000'000, group, coin_selection_params, /*allow_mixed_output_types=*/true);

murchandamus commented at 9:20 pm on March 13, 2026:

Thanks, looking at the old benchmark again, I realized that I was mistaken in what it did. It had 1000 × 1000 BTC and 1 × 3 BTC, and then looked that 1003 would be selected via 1000 + 3.

I don’t think it’s an interesting case to keep around next to the new benchmark, so I propose removing it.

l0rinc approved

l0rinc commented at 4:27 pm on March 13, 2026: contributor

I’m mostly okay with the change, left a few more comments

  0diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp
  1--- a/src/bench/coin_selection.cpp	(revision 67544d3b713f945e6c9fa826aa081a1b966f458a)
  2+++ b/src/bench/coin_selection.cpp	(date 1773418910077)
  3@@ -12,6 +12,7 @@
  4 #include <primitives/transaction.h>
  5 #include <random.h>
  6 #include <sync.h>
  7+#include <test/util/setup_common.h>
  8 #include <util/result.h>
  9 #include <wallet/coinselection.h>
 10 #include <wallet/spend.h>
 11@@ -74,8 +75,8 @@
 12         available_coins.coins[OutputType::BECH32].emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/0);
 13     }
 14 
 15-    const CoinEligibilityFilter filter_standard(1, 6, 0);
 16-    FastRandomContext rand{};
 17+    const CoinEligibilityFilter filter_standard(/*conf_mine=*/1, /*conf_theirs=*/6, /*max_ancestors=*/0);
 18+    FastRandomContext rand{/*fDeterministic=*/true};
 19     const CoinSelectionParams coin_selection_params{
 20         rand,
 21         /*change_output_size=*/34,
 22@@ -89,7 +90,7 @@
 23     };
 24     auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard];
 25     bench.run([&] {
 26-        auto result = AttemptSelection(wallet.chain(), 1002.99 * COIN, group, coin_selection_params, /*allow_mixed_output_types=*/true);
 27+        auto result = AttemptSelection(wallet.chain(), 1002 * COIN + 99 * CENT, group, coin_selection_params, /*allow_mixed_output_types=*/false);
 28         assert(result);
 29         assert(result->GetSelectedValue() == 1003 * COIN);
 30         assert(result->GetInputSet().size() == 2);
 31@@ -97,8 +98,8 @@
 32 }
 33 
 34 // This benchmark is based on a UTXO pool composed of hundreds of UTXOs. The
 35-// UTXOs are pseudorandomly generated to be of the four relevant output types
 36-// P2PKH, P2SH-P2WPKH, P2WPKH, and P2TR UTXOs.
 37+// UTXOs are pseudorandomly generated and assigned one of the four relevant
 38+// output types: P2PKH, P2SH-P2WPKH, P2WPKH, and P2TR.
 39 // Smaller amounts are more likely to be generated than larger amounts. This
 40 // UTXO pool is used to run coin selection for pseudorandom selection targets.
 41 // Altogether, this gives us a deterministic benchmark with a somewhat
 42@@ -119,7 +120,7 @@
 43         int p{det_rand.randrange(100)};
 44         if (p < 50) {
 45             amount = 10'000 + det_rand.randrange(90'000);
 46-        } else if (p < 75)  {
 47+        } else if (p < 75) {
 48             amount = 100'000 + det_rand.randrange(900'000);
 49         } else if (p < 95) {
 50             amount = 1'000'000 + det_rand.randrange(9'000'000);
 51@@ -153,15 +154,16 @@
 52         available_coins.coins[outtype].emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, /*input_bytes=*/input_bytes, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/fees);
 53     }
 54 
 55+    constexpr size_t NUM_TARGETS{10};
 56     std::vector<CAmount> targets;
 57-    targets.reserve(10);
 58-    for (size_t i{0}; i < targets.capacity(); ++i) {
 59+    targets.reserve(NUM_TARGETS);
 60+    for (size_t i{0}; i < NUM_TARGETS; ++i) {
 61         targets.push_back(10'000'000 + det_rand.randrange(90'000'000));
 62     }
 63 
 64-    // Allow actual randomness for selection
 65+    // Keep selection deterministic for benchmark stability
 66     FastRandomContext rand{/*fDeterministic=*/true};
 67-    const CoinEligibilityFilter filter_standard(1, 6, 0);
 68+    const CoinEligibilityFilter filter_standard(/*conf_mine=*/1, /*conf_theirs=*/6, /*max_ancestors=*/0);
 69     const CoinSelectionParams coin_selection_params{
 70         rand,
 71         /*change_output_size=*/31,
 72@@ -175,7 +177,7 @@
 73     };
 74     auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard];
 75 
 76-    bench.run([&] {
 77+    bench.batch(NUM_TARGETS).run([&] {
 78         for (const auto& target : targets) {
 79             auto result = AttemptSelection(wallet.chain(), target, group, coin_selection_params, /*allow_mixed_output_types=*/true);
 80             assert(result);
 81@@ -184,7 +186,6 @@
 82     });
 83 }
 84 
 85-// Copied from src/wallet/test/coinselector_tests.cpp
 86 static void add_coin(const CAmount& nValue, uint32_t nInput, std::vector<OutputGroup>& set)
 87 {
 88     CMutableTransaction tx;
 89@@ -194,7 +195,6 @@
 90     set.emplace_back();
 91     set.back().Insert(std::make_shared<COutput>(output), /*ancestors=*/0, /*cluster_count=*/0);
 92 }
 93-// Copied from src/wallet/test/coinselector_tests.cpp
 94 static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
 95 {
 96     utxo_pool.clear();
 97@@ -213,7 +213,7 @@
 98 
 99     CAmount target = make_hard_case(17, utxo_pool);
100     bench.run([&] {
101-        (void)SelectCoinsBnB(utxo_pool, target, /*cost_of_change=*/0, MAX_STANDARD_TX_WEIGHT); // Should exhaust
102+        (void)SelectCoinsBnB(utxo_pool, target, /*cost_of_change=*/0, MAX_STANDARD_TX_WEIGHT);
103     });
104 }

bench: Move setup out of bench

Also:
- Fix type mismatch
- Harmonize comments

Co-authored-by: l0rinc <pap.lorinc@gmail.com>

9ef2a2683d

bench: Remove unnecessary wallet parameter

Co-authored-by: l0rinc <pap.lorinc@gmail.com>

8054ac9856

bench: Replace Coin Selection bench

Co-authored-by: l0rinc <pap.lorinc@gmail.com>

6a9ac95c80

murchandamus force-pushed on Mar 13, 2026

murchandamus commented at 10:07 pm on March 13, 2026: member

Took almost all of your suggestion (unresolved where I didn’t or had comments).

Spent more time staring at it, and was left wondering what the old Coin Selection benchmark was adding at this point, so I instead restructured the PR to replace it.

bench: Add more realistic Coin Selection Bench #33160

Code Coverage & Benchmarks

Reviews

Conflicts