coin_selection.cpp raw
1 // Copyright (c) 2012-2022 The Limenka developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5 #include <bench/bench.h>
6 #include <consensus/amount.h>
7 #include <interfaces/chain.h>
8 #include <node/context.h>
9 #include <outputtype.h>
10 #include <policy/feerate.h>
11 #include <policy/policy.h>
12 #include <primitives/transaction.h>
13 #include <random.h>
14 #include <sync.h>
15 #include <util/result.h>
16 #include <wallet/coinselection.h>
17 #include <wallet/spend.h>
18 #include <wallet/test/util.h>
19 #include <wallet/transaction.h>
20 #include <wallet/wallet.h>
21
22 #include <cassert>
23 #include <map>
24 #include <memory>
25 #include <set>
26 #include <utility>
27 #include <vector>
28
29 using node::NodeContext;
30 using wallet::AttemptSelection;
31 using wallet::CHANGE_LOWER;
32 using wallet::COutput;
33 using wallet::CWallet;
34 using wallet::CWalletTx;
35 using wallet::CoinEligibilityFilter;
36 using wallet::CoinSelectionParams;
37 using wallet::CreateMockableWalletDatabase;
38 using wallet::OutputGroup;
39 using wallet::SelectCoinsBnB;
40 using wallet::TxStateInactive;
41
42 static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<std::unique_ptr<CWalletTx>>& wtxs)
43 {
44 static int nextLockTime = 0;
45 CMutableTransaction tx;
46 tx.nLockTime = nextLockTime++; // so all transactions get different hashes
47 tx.vout.resize(1);
48 tx.vout[0].nValue = nValue;
49 wtxs.push_back(std::make_unique<CWalletTx>(MakeTransactionRef(std::move(tx)), TxStateInactive{}));
50 }
51
52 // Simple benchmark for wallet coin selection. Note that it maybe be necessary
53 // to build up more complicated scenarios in order to get meaningful
54 // measurements of performance. From laanwj, "Wallet coin selection is probably
55 // the hardest, as you need a wider selection of scenarios, just testing the
56 // same one over and over isn't too useful. Generating random isn't useful
57 // either for measurements."
58 // (https://github.com/limenka/limenka/issues/7883#issuecomment-224807484)
59 static void CoinSelection(benchmark::Bench& bench)
60 {
61 NodeContext node;
62 auto chain = interfaces::MakeChain(node);
63 CWallet wallet(chain.get(), "", CreateMockableWalletDatabase());
64 std::vector<std::unique_ptr<CWalletTx>> wtxs;
65 LOCK(wallet.cs_wallet);
66
67 // Add coins.
68 for (int i = 0; i < 1000; ++i) {
69 addCoin(1000 * COIN, wallet, wtxs);
70 }
71 addCoin(3 * COIN, wallet, wtxs);
72
73 // Create coins
74 wallet::CoinsResult available_coins;
75 for (const auto& wtx : wtxs) {
76 const auto txout = wtx->tx->vout.at(0);
77 available_coins.coins[OutputType::BECH32].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);
78 }
79
80 const CoinEligibilityFilter filter_standard(1, 6, 0);
81 FastRandomContext rand{};
82 const CoinSelectionParams coin_selection_params{
83 rand,
84 /*change_output_size=*/ 34,
85 /*change_spend_size=*/ 148,
86 /*min_change_target=*/ CHANGE_LOWER,
87 /*effective_feerate=*/ CFeeRate(20'000),
88 /*long_term_feerate=*/ CFeeRate(10'000),
89 /*discard_feerate=*/ CFeeRate(3000),
90 /*tx_noinputs_size=*/ 0,
91 /*avoid_partial=*/ false,
92 };
93 auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard];
94 bench.run([&] {
95 auto result = AttemptSelection(wallet.chain(), 1002.99 * COIN, group, coin_selection_params, /*allow_mixed_output_types=*/true);
96 assert(result);
97 assert(result->GetSelectedValue() == 1003 * COIN);
98 assert(result->GetInputSet().size() == 2);
99 });
100 }
101
102 // Copied from src/wallet/test/coinselector_tests.cpp
103 static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>& set)
104 {
105 CMutableTransaction tx;
106 tx.vout.resize(nInput + 1);
107 tx.vout[nInput].nValue = nValue;
108 COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 0, /*input_bytes=*/ -1, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ true, /*fees=*/ 0);
109 set.emplace_back();
110 set.back().Insert(std::make_shared<COutput>(output), /*ancestors=*/ 0, /*descendants=*/ 0);
111 }
112 // Copied from src/wallet/test/coinselector_tests.cpp
113 static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
114 {
115 utxo_pool.clear();
116 CAmount target = 0;
117 for (int i = 0; i < utxos; ++i) {
118 target += CAmount{1} << (utxos+i);
119 add_coin(CAmount{1} << (utxos+i), 2*i, utxo_pool);
120 add_coin((CAmount{1} << (utxos+i)) + (CAmount{1} << (utxos-1-i)), 2*i + 1, utxo_pool);
121 }
122 return target;
123 }
124
125 static void BnBExhaustion(benchmark::Bench& bench)
126 {
127 // Setup
128 std::vector<OutputGroup> utxo_pool;
129
130 bench.run([&] {
131 // Benchmark
132 CAmount target = make_hard_case(17, utxo_pool);
133 SelectCoinsBnB(utxo_pool, target, 0, MAX_STANDARD_TX_WEIGHT); // Should exhaust
134
135 // Cleanup
136 utxo_pool.clear();
137 });
138 }
139
140 BENCHMARK(CoinSelection, benchmark::PriorityLevel::HIGH);
141 BENCHMARK(BnBExhaustion, benchmark::PriorityLevel::HIGH);
142