1 // Copyright (c) 2012-2020 The Bitcoin Core 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 <interfaces/chain.h>
7 #include <node/context.h>
8 #include <wallet/coinselection.h>
9 #include <wallet/wallet.h>
10
11 #include <set>
12
13 static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<std::unique_ptr<CWalletTx>>& wtxs)
14 {
15 static int nextLockTime = 0;
16 CMutableTransaction tx;
17 tx.nLockTime = nextLockTime++; // so all transactions get different hashes
18 tx.vout.resize(1);
19 tx.vout[0].nValue = nValue;
20 wtxs.push_back(std::make_unique<CWalletTx>(&wallet, MakeTransactionRef(std::move(tx))));
21 }
22
CCheckQueueSpeedPrevectorJob(benchmark::Bench & bench)23 // Simple benchmark for wallet coin selection. Note that it maybe be necessary
24 // to build up more complicated scenarios in order to get meaningful
25 // measurements of performance. From laanwj, "Wallet coin selection is probably
26 // the hardest, as you need a wider selection of scenarios, just testing the
27 // same one over and over isn't too useful. Generating random isn't useful
28 // either for measurements."
29 // (https://github.com/bitcoin/bitcoin/issues/7883#issuecomment-224807484)
30 static void CoinSelection(benchmark::Bench& bench)
31 {
32 NodeContext node;
33 auto chain = interfaces::MakeChain(node);
34 CWallet wallet(chain.get(), "", CreateDummyWalletDatabase());
35 wallet.SetupLegacyScriptPubKeyMan();
36 std::vector<std::unique_ptr<CWalletTx>> wtxs;
37 LOCK(wallet.cs_wallet);
38
39 // Add coins.
40 for (int i = 0; i < 1000; ++i) {
41 addCoin(1000 * COIN, wallet, wtxs);
42 }
43 addCoin(3 * COIN, wallet, wtxs);
44
45 // Create coins
46 std::vector<COutput> coins;
47 for (const auto& wtx : wtxs) {
48 coins.emplace_back(wtx.get(), 0 /* iIn */, 6 * 24 /* nDepthIn */, true /* spendable */, true /* solvable */, true /* safe */);
49 }
50
51 const CoinEligibilityFilter filter_standard(1, 6, 0);
52 const CoinSelectionParams coin_selection_params(/* change_output_size= */ 34,
53 /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0),
54 /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
55 /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false);
56 bench.run([&] {
57 std::set<CInputCoin> setCoinsRet;
58 CAmount nValueRet;
59 bool success = wallet.AttemptSelection(1003 * COIN, filter_standard, coins, setCoinsRet, nValueRet, coin_selection_params);
60 assert(success);
61 assert(nValueRet == 1003 * COIN);
62 assert(setCoinsRet.size() == 2);
63 });
64 }
65
66 typedef std::set<CInputCoin> CoinSet;
67 static NodeContext testNode;
68 static auto testChain = interfaces::MakeChain(testNode);
69 static CWallet testWallet(testChain.get(), "", CreateDummyWalletDatabase());
70 std::vector<std::unique_ptr<CWalletTx>> wtxn;
71
72 // Copied from src/wallet/test/coinselector_tests.cpp
73 static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>& set)
74 {
75 CMutableTransaction tx;
76 tx.vout.resize(nInput + 1);
77 tx.vout[nInput].nValue = nValue;
78 std::unique_ptr<CWalletTx> wtx = std::make_unique<CWalletTx>(&testWallet, MakeTransactionRef(std::move(tx)));
79 set.emplace_back();
80 set.back().Insert(COutput(wtx.get(), nInput, 0, true, true, true).GetInputCoin(), 0, true, 0, 0, false);
81 wtxn.emplace_back(std::move(wtx));
82 }
83 // Copied from src/wallet/test/coinselector_tests.cpp
84 static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
85 {
86 utxo_pool.clear();
87 CAmount target = 0;
88 for (int i = 0; i < utxos; ++i) {
89 target += (CAmount)1 << (utxos+i);
90 add_coin((CAmount)1 << (utxos+i), 2*i, utxo_pool);
91 add_coin(((CAmount)1 << (utxos+i)) + ((CAmount)1 << (utxos-1-i)), 2*i + 1, utxo_pool);
92 }
93 return target;
94 }
95
96 static void BnBExhaustion(benchmark::Bench& bench)
97 {
98 // Setup
99 testWallet.SetupLegacyScriptPubKeyMan();
100 std::vector<OutputGroup> utxo_pool;
101 CoinSet selection;
102 CAmount value_ret = 0;
103
104 bench.run([&] {
105 // Benchmark
106 CAmount target = make_hard_case(17, utxo_pool);
107 SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret); // Should exhaust
108
109 // Cleanup
110 utxo_pool.clear();
111 selection.clear();
112 });
113 }
114
115 BENCHMARK(CoinSelection);
116 BENCHMARK(BnBExhaustion);
117