bench: Add more realistic Coin Selection Bench #33160

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.

<!--e57a25ab6845829454e8d69fc972939a-->

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

<!--006a51241073e994b41acfe9ec718e94-->

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33160.

<!--021abf342d371248e50ceaed478a90ca-->

Reviews

See the guideline for information on the review process.

If your review is incorrectly listed, please copy-paste <code>&lt;!--meta-tag:bot-skip--&gt;</code> into the comment that the bot should ignore.

<!--174a7506f384e20aa4161008e828411d-->

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #33034 (wallet: Store transactions in a separate sqlite table by achow101)
• #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.

<!--5faf32d7da4f0f540f40219e4f7537a3-->

LLM Linter (✨ experimental)

Possible places where named args for integral literals may be used (e.g. func(x, /*named_arg=*/0) in C++, and func(x, named_arg=0) in Python):

• COutPoint(wtx->GetHash(), 0) in src/bench/coin_selection.cpp

^{2026-04-07 22:25:35}

<!--85328a0da195eb286784d51f73fa0af9-->

🚧 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.}

<details><summary>Hints</summary>

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.

</details>

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.

<details> <summary>Details</summary>

// Copyright (c) 2012-2022 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <bench/bench.h>
#include <consensus/amount.h>
#include <interfaces/chain.h>
#include <node/context.h>
#include <outputtype.h>
#include <policy/feerate.h>
#include <policy/policy.h>
#include <primitives/transaction.h>
#include <random.h>
#include <sync.h>
#include <util/result.h>
#include <wallet/coinselection.h>
#include <wallet/spend.h>
#include <wallet/test/util.h>
#include <wallet/transaction.h>
#include <wallet/wallet.h>

#include <cassert>
#include <map>
#include <memory>
#include <set>
#include <utility>
#include <vector>
#include <cmath>

using node::NodeContext;
using wallet::AttemptSelection;
using wallet::CHANGE_LOWER;
using wallet::COutput;
using wallet::CWallet;
using wallet::CWalletTx;
using wallet::CoinEligibilityFilter;
using wallet::CoinSelectionParams;
using wallet::CreateMockableWalletDatabase;
using wallet::OutputGroup;
using wallet::SelectCoinsBnB;
using wallet::TxStateInactive;

namespace {
constexpr CAmount operator""_sat(uint64_t v) { return v; }
constexpr CAmount operator""_ksat(uint64_t v) { return v * 1'000; }
constexpr CAmount operator""_btc(uint64_t v) { return v * COIN; }
constexpr CAmount operator""_btc(long double v) { return std::llround(v * COIN); }

int rand_percentage(FastRandomContext& rng) { return rng.randrange(100); }
CAmount rand_range(FastRandomContext& rng, CAmount lo, CAmount hi) { return lo + rng.randrange(hi - lo + 1); }
} // namespace

static void addCoin(CAmount nValue, std::vector<std::unique_ptr<CWalletTx>>& wtxs)
{
    static int nextLockTime = 0;
    CMutableTransaction tx;
    tx.nLockTime = nextLockTime++; // so all transactions get different hashes
    tx.vout.resize(1);
    tx.vout[0].nValue = nValue;
    wtxs.push_back(std::make_unique<CWalletTx>(MakeTransactionRef(std::move(tx)), TxStateInactive{}));
}

// Simple benchmark for wallet coin selection that exercises a worst-case
// scenario for Knapsack: All UTXOs are necessary, but it is not an exact
// match, so the only eligible input set is only discovered on the second pass
// after all random walks fail to produce a solution.
static void KnapsackWorstCase(benchmark::Bench& bench)
{
    NodeContext node;
    auto chain{interfaces::MakeChain(node)};
    CWallet wallet(chain.get(), "", CreateMockableWalletDatabase());
    std::vector<std::unique_ptr<CWalletTx>> wtxs;
    LOCK(wallet.cs_wallet);

    for (int i{0}; i < 1000; ++i) {
        addCoin(1000_btc, wtxs);
    }
    addCoin(3_btc, wtxs);

    // Create coins
    wallet::CoinsResult available_coins;
    for (const auto& wtx : wtxs) {
        const auto txout{wtx->tx->vout.at(0)};
        const int input_bytes{CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr)};
        const COutput output{COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, input_bytes, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/0};
        available_coins.coins[OutputType::BECH32].emplace_back(output);
    }

    const CoinEligibilityFilter filter_standard(1, 6, 0);
    FastRandomContext rand{/*fDeterministic=*/true};
    const CoinSelectionParams coin_selection_params{
        rand,
        /*change_output_size=*/34,
        /*change_spend_size=*/148,
        /*min_change_target=*/CHANGE_LOWER,
        /*effective_feerate=*/CFeeRate(20'000),
        /*long_term_feerate=*/CFeeRate(10'000),
        /*discard_feerate=*/CFeeRate(3000),
        /*tx_noinputs_size=*/0,
        /*avoid_partial=*/false,
    };
    auto group{wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard]};
    bench.run([&] {
        auto result{AttemptSelection(wallet.chain(), 1002.99_btc, group, coin_selection_params, /*allow_mixed_output_types=*/true)};
        assert(result);
        assert(result->GetSelectedValue() == 1003_btc);
        assert(result->GetInputSet().size() == 2);
    });
}

// This benchmark is based on a UTXO pool composed of 400 UTXOs. The UTXOs are
// pseudorandomly generated to be of the four relevant output types P2PKH,
// P2SH-P2WPKH, P2WPKH, and P2TR UTXOs, and fall in the range of 10'000 sats to
// 1₿ with larger amounts being more likely.
// This UTXO pool is used to run coin selection for 100 pseudorandom selection
// targets from 0.1–2₿. Altogether, this gives us a deterministic benchmark
// with a hopefully somewhat representative coin selection scenario.
static void CoinSelectionOnDiverseWallet(benchmark::Bench& bench)
{
    FastRandomContext rng{/*fDeterministic=*/true};

    NodeContext node;
    auto chain{interfaces::MakeChain(node)};
    CWallet wallet(chain.get(), "", CreateMockableWalletDatabase());
    LOCK(wallet.cs_wallet);

    std::vector<std::unique_ptr<CWalletTx>> wtxs;
    wtxs.reserve(400);
    for (size_t i{0}; i < wtxs.capacity(); ++i) {
        const int p{rand_percentage(rng)};
        const auto val{p < 50 ? rand_range(rng, 10_ksat, 100_ksat) :
                       p < 75 ? rand_range(rng, 100_ksat, 1000_ksat) :
                       p < 95 ? rand_range(rng, 1000_ksat, 1_btc) :
                                rand_range(rng, 0.1_btc, 1_btc)};
        addCoin(val, wtxs);
    }

    // Create coins
    wallet::CoinsResult available_coins;
    for (const auto& wtx : wtxs) {
        const int p{rand_percentage(rng)};
        auto val{p < 35 ? OutputType::LEGACY :
                 p < 55 ? OutputType::P2SH_SEGWIT :
                 p < 90 ? OutputType::BECH32 :
                          OutputType::BECH32M};

        const auto txout{wtx->tx->vout.at(0)};
        const int input_bytes{CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr)};
        const COutput output{COutPoint{wtx->GetHash(), 0}, txout, /*depth=*/6 * 24, input_bytes, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/0};
        available_coins.coins[val].emplace_back(output);
    }

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

    const CoinSelectionParams coin_selection_params{
        rng,
        /*change_output_size=*/31,
        /*change_spend_size=*/68,
        /*min_change_target=*/CHANGE_LOWER,
        /*effective_feerate=*/CFeeRate(20'000),
        /*long_term_feerate=*/CFeeRate(10'000),
        /*discard_feerate=*/CFeeRate(3000),
        /*tx_noinputs_size=*/72,
        /*avoid_partial=*/false,
    };
    const CoinEligibilityFilter filter_standard(1, 6, 0);
    auto group{wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard]};

    bench.run([&] {
        for (const auto& target : targets) {
            auto result{AttemptSelection(wallet.chain(), target, group, coin_selection_params, /*allow_mixed_output_types=*/true)};
            assert(result && result->GetSelectedValue() >= target);
        }
    });
}

static void add_coin(CAmount nValue, uint32_t nInput, std::vector<OutputGroup>& set)
{
    CMutableTransaction tx;
    tx.vout.resize(nInput + 1);
    tx.vout[nInput].nValue = nValue;
    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);
    set.emplace_back();
    set.back().Insert(std::make_shared<COutput>(output), /*ancestors=*/0, /*descendants=*/0);
}

static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
{
    utxo_pool.clear();
    CAmount target{0};
    for (int i{0}; i < utxos; ++i) {
        target += 1_sat << (utxos + i);
        add_coin(1_sat << (utxos + i), 2 * i, utxo_pool);
        add_coin((1_sat << (utxos + i)) + (1_sat << (utxos - 1 - i)), 2 * i + 1, utxo_pool);
    }
    return target;
}

static void BnBExhaustion(benchmark::Bench& bench)
{
    std::vector<OutputGroup> utxo_pool;
    auto target{make_hard_case(17, utxo_pool)};
    bench.run([&] {
        SelectCoinsBnB(utxo_pool, target, 0, MAX_STANDARD_TX_WEIGHT); // Should exhaust
    });
}

BENCHMARK(KnapsackWorstCase, benchmark::PriorityLevel::HIGH);
BENCHMARK(CoinSelectionOnDiverseWallet, benchmark::PriorityLevel::HIGH);
BENCHMARK(BnBExhaustion, benchmark::PriorityLevel::HIGH);

</details>

<!--85328a0da195eb286784d51f73fa0af9-->

🚧 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.}

<details><summary>Hints</summary>

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.

</details>

Thanks for your comments, @l0rinc.

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

<details><summary>All combined suggestions</summary>

diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp
--- a/src/bench/coin_selection.cpp	(revision 67544d3b713f945e6c9fa826aa081a1b966f458a)
+++ b/src/bench/coin_selection.cpp	(date 1773418910077)
@@ -12,6 +12,7 @@
 #include <primitives/transaction.h>
 #include <random.h>
 #include <sync.h>
+#include <test/util/setup_common.h>
 #include <util/result.h>
 #include <wallet/coinselection.h>
 #include <wallet/spend.h>
@@ -74,8 +75,8 @@
         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);
     }
 
-    const CoinEligibilityFilter filter_standard(1, 6, 0);
-    FastRandomContext rand{};
+    const CoinEligibilityFilter filter_standard(/*conf_mine=*/1, /*conf_theirs=*/6, /*max_ancestors=*/0);
+    FastRandomContext rand{/*fDeterministic=*/true};
     const CoinSelectionParams coin_selection_params{
         rand,
         /*change_output_size=*/34,
@@ -89,7 +90,7 @@
     };
     auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard];
     bench.run([&] {
-        auto result = AttemptSelection(wallet.chain(), 1002.99 * COIN, group, coin_selection_params, /*allow_mixed_output_types=*/true);
+        auto result = AttemptSelection(wallet.chain(), 1002 * COIN + 99 * CENT, group, coin_selection_params, /*allow_mixed_output_types=*/false);
         assert(result);
         assert(result->GetSelectedValue() == 1003 * COIN);
         assert(result->GetInputSet().size() == 2);
@@ -97,8 +98,8 @@
 }
 
 // This benchmark is based on a UTXO pool composed of hundreds of UTXOs. The
-// UTXOs are pseudorandomly generated to be of the four relevant output types
-// P2PKH, P2SH-P2WPKH, P2WPKH, and P2TR UTXOs.
+// UTXOs are pseudorandomly generated and assigned one of the four relevant
+// output types: P2PKH, P2SH-P2WPKH, P2WPKH, and P2TR.
 // Smaller amounts are more likely to be generated than larger amounts. This
 // UTXO pool is used to run coin selection for pseudorandom selection targets.
 // Altogether, this gives us a deterministic benchmark with a somewhat
@@ -119,7 +120,7 @@
         int p{det_rand.randrange(100)};
         if (p < 50) {
             amount = 10'000 + det_rand.randrange(90'000);
-        } else if (p < 75)  {
+        } else if (p < 75) {
             amount = 100'000 + det_rand.randrange(900'000);
         } else if (p < 95) {
             amount = 1'000'000 + det_rand.randrange(9'000'000);
@@ -153,15 +154,16 @@
         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);
     }
 
+    constexpr size_t NUM_TARGETS{10};
     std::vector<CAmount> targets;
-    targets.reserve(10);
-    for (size_t i{0}; i < targets.capacity(); ++i) {
+    targets.reserve(NUM_TARGETS);
+    for (size_t i{0}; i < NUM_TARGETS; ++i) {
         targets.push_back(10'000'000 + det_rand.randrange(90'000'000));
     }
 
-    // Allow actual randomness for selection
+    // Keep selection deterministic for benchmark stability
     FastRandomContext rand{/*fDeterministic=*/true};
-    const CoinEligibilityFilter filter_standard(1, 6, 0);
+    const CoinEligibilityFilter filter_standard(/*conf_mine=*/1, /*conf_theirs=*/6, /*max_ancestors=*/0);
     const CoinSelectionParams coin_selection_params{
         rand,
         /*change_output_size=*/31,
@@ -175,7 +177,7 @@
     };
     auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard];
 
-    bench.run([&] {
+    bench.batch(NUM_TARGETS).run([&] {
         for (const auto& target : targets) {
             auto result = AttemptSelection(wallet.chain(), target, group, coin_selection_params, /*allow_mixed_output_types=*/true);
             assert(result);
@@ -184,7 +186,6 @@
     });
 }
 
-// Copied from src/wallet/test/coinselector_tests.cpp
 static void add_coin(const CAmount& nValue, uint32_t nInput, std::vector<OutputGroup>& set)
 {
     CMutableTransaction tx;
@@ -194,7 +195,6 @@
     set.emplace_back();
     set.back().Insert(std::make_shared<COutput>(output), /*ancestors=*/0, /*cluster_count=*/0);
 }
-// Copied from src/wallet/test/coinselector_tests.cpp
 static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
 {
     utxo_pool.clear();
@@ -213,7 +213,7 @@
 
     CAmount target = make_hard_case(17, utxo_pool);
     bench.run([&] {
-        (void)SelectCoinsBnB(utxo_pool, target, /*cost_of_change=*/0, MAX_STANDARD_TX_WEIGHT); // Should exhaust
+        (void)SelectCoinsBnB(utxo_pool, target, /*cost_of_change=*/0, MAX_STANDARD_TX_WEIGHT);
     });
 }

</details>

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.

Rebased after conflict with #34208

The current version is a lot simplers. I think we could make it more reliable by resetting the mutations inside the measurement block with the new setup method.

<!--cf906140f33d8803c4a75a2196329ecb-->

🐙 This pull request conflicts with the target branch and needs rebase.