Skip to content

Commit 59d6f7b

Browse files
kallewoofkallewoof
committed
wallet: Switch to using output groups instead of coins in coin selection
1 parent 87ebce2 commit 59d6f7b

File tree

6 files changed

+175
-160
lines changed

6 files changed

+175
-160
lines changed

‎src/bench/coin_selection.cpp‎

Lines changed: 14 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88

99
#include <set>
1010

11-
static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<COutput>& vCoins)
11+
static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<OutputGroup>& groups)
1212
{
1313
int nInput = 0;
1414

@@ -21,7 +21,7 @@ static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<CO
2121

2222
int nAge = 6 * 24;
2323
COutput output(wtx, nInput, nAge, true /* spendable */, true /* solvable */, true /* safe */);
24-
vCoins.push_back(output);
24+
groups.emplace_back(output.GetInputCoin(), 0, false, 0, 0);
2525
}
2626

2727
// Simple benchmark for wallet coin selection. Note that it maybe be necessary
@@ -37,37 +37,41 @@ static void CoinSelection(benchmark::State& state)
3737
LOCK(wallet.cs_wallet);
3838

3939
// Add coins.
40-
std::vector<COutput> vCoins;
40+
std::vector<OutputGroup> groups;
4141
for (int i = 0; i < 1000; ++i) {
42-
addCoin(1000 * COIN, wallet, vCoins);
42+
addCoin(1000 * COIN, wallet, groups);
4343
}
44-
addCoin(3 * COIN, wallet, vCoins);
44+
addCoin(3 * COIN, wallet, groups);
4545

4646
const CoinEligibilityFilter filter_standard(1, 6, 0);
4747
const CoinSelectionParams coin_selection_params(true, 34, 148, CFeeRate(0), 0);
4848
while (state.KeepRunning()) {
4949
std::set<CInputCoin> setCoinsRet;
5050
CAmount nValueRet;
5151
bool bnb_used;
52-
bool success = wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used);
52+
bool success = wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, groups, setCoinsRet, nValueRet, coin_selection_params, bnb_used);
5353
assert(success);
5454
assert(nValueRet == 1003 * COIN);
5555
assert(setCoinsRet.size() == 2);
5656
}
5757
}
5858

5959
typedef std::set<CInputCoin> CoinSet;
60+
static const CWallet testWallet("dummy", WalletDatabase::CreateDummy());
61+
std::vector<std::unique_ptr<CWalletTx>> wtxn;
6062

6163
// Copied from src/wallet/test/coinselector_tests.cpp
62-
static void add_coin(const CAmount& nValue, int nInput, std::vector<CInputCoin>& set)
64+
static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>& set)
6365
{
6466
CMutableTransaction tx;
6567
tx.vout.resize(nInput + 1);
6668
tx.vout[nInput].nValue = nValue;
67-
set.emplace_back(MakeTransactionRef(tx), nInput);
69+
std::unique_ptr<CWalletTx> wtx(new CWalletTx(&testWallet, MakeTransactionRef(std::move(tx))));
70+
set.emplace_back(COutput(wtx.get(), nInput, 0, true, true, true).GetInputCoin(), 0, true, 0, 0);
71+
wtxn.emplace_back(std::move(wtx));
6872
}
6973
// Copied from src/wallet/test/coinselector_tests.cpp
70-
static CAmount make_hard_case(int utxos, std::vector<CInputCoin>& utxo_pool)
74+
static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
7175
{
7276
utxo_pool.clear();
7377
CAmount target = 0;
@@ -82,7 +86,7 @@ static CAmount make_hard_case(int utxos, std::vector<CInputCoin>& utxo_pool)
8286
static void BnBExhaustion(benchmark::State& state)
8387
{
8488
// Setup
85-
std::vector<CInputCoin> utxo_pool;
89+
std::vector<OutputGroup> utxo_pool;
8690
CoinSet selection;
8791
CAmount value_ret = 0;
8892
CAmount not_input_fees = 0;

‎src/wallet/coinselection.cpp‎

Lines changed: 51 additions & 62 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88

99
// Descending order comparator
1010
struct {
11-
bool operator()(const CInputCoin& a, const CInputCoin& b) const
11+
bool operator()(const OutputGroup& a, const OutputGroup& b) const
1212
{
1313
return a.effective_value > b.effective_value;
1414
}
@@ -59,7 +59,7 @@ struct {
5959

6060
static const size_t TOTAL_TRIES = 100000;
6161

62-
bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees)
62+
bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees)
6363
{
6464
out_set.clear();
6565
CAmount curr_value = 0;
@@ -70,7 +70,7 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va
7070

7171
// Calculate curr_available_value
7272
CAmount curr_available_value = 0;
73-
for (const CInputCoin& utxo : utxo_pool) {
73+
for (const OutputGroup& utxo : utxo_pool) {
7474
// Assert that this utxo is not negative. It should never be negative, effective value calculation should have removed it
7575
assert(utxo.effective_value > 0);
7676
curr_available_value += utxo.effective_value;
@@ -123,11 +123,11 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va
123123

124124
// Output was included on previous iterations, try excluding now.
125125
curr_selection.back() = false;
126-
CInputCoin& utxo = utxo_pool.at(curr_selection.size() - 1);
126+
OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1);
127127
curr_value -= utxo.effective_value;
128128
curr_waste -= utxo.fee - utxo.long_term_fee;
129129
} else { // Moving forwards, continuing down this branch
130-
CInputCoin& utxo = utxo_pool.at(curr_selection.size());
130+
OutputGroup& utxo = utxo_pool.at(curr_selection.size());
131131

132132
// Remove this utxo from the curr_available_value utxo amount
133133
curr_available_value -= utxo.effective_value;
@@ -156,32 +156,32 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va
156156
value_ret = 0;
157157
for (size_t i = 0; i < best_selection.size(); ++i) {
158158
if (best_selection.at(i)) {
159-
out_set.insert(utxo_pool.at(i));
160-
value_ret += utxo_pool.at(i).txout.nValue;
159+
util::insert(out_set, utxo_pool.at(i).m_outputs);
160+
value_ret += utxo_pool.at(i).m_value;
161161
}
162162
}
163163

164164
return true;
165165
}
166166

167-
static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const CAmount& nTotalLower, const CAmount& nTargetValue,
167+
static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const CAmount& nTotalLower, const CAmount& nTargetValue,
168168
std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
169169
{
170170
std::vector<char> vfIncluded;
171171

172-
vfBest.assign(vValue.size(), true);
172+
vfBest.assign(groups.size(), true);
173173
nBest = nTotalLower;
174174

175175
FastRandomContext insecure_rand;
176176

177177
for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
178178
{
179-
vfIncluded.assign(vValue.size(), false);
179+
vfIncluded.assign(groups.size(), false);
180180
CAmount nTotal = 0;
181181
bool fReachedTarget = false;
182182
for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
183183
{
184-
for (unsigned int i = 0; i < vValue.size(); i++)
184+
for (unsigned int i = 0; i < groups.size(); i++)
185185
{
186186
//The solver here uses a randomized algorithm,
187187
//the randomness serves no real security purpose but is just
@@ -191,7 +191,7 @@ static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const C
191191
//the selection random.
192192
if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
193193
{
194-
nTotal += vValue[i].txout.nValue;
194+
nTotal += groups[i].m_value;
195195
vfIncluded[i] = true;
196196
if (nTotal >= nTargetValue)
197197
{
@@ -201,7 +201,7 @@ static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const C
201201
nBest = nTotal;
202202
vfBest = vfIncluded;
203203
}
204-
nTotal -= vValue[i].txout.nValue;
204+
nTotal -= groups[i].m_value;
205205
vfIncluded[i] = false;
206206
}
207207
}
@@ -210,86 +210,75 @@ static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const C
210210
}
211211
}
212212

213-
bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet)
213+
bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet)
214214
{
215215
setCoinsRet.clear();
216216
nValueRet = 0;
217217

218218
// List of values less than target
219-
boost::optional<CInputCoin> coinLowestLarger;
220-
std::vector<CInputCoin> vValue;
219+
boost::optional<OutputGroup> lowest_larger;
220+
std::vector<OutputGroup> applicable_groups;
221221
CAmount nTotalLower = 0;
222222

223-
random_shuffle(vCoins.begin(), vCoins.end(), GetRandInt);
223+
random_shuffle(groups.begin(), groups.end(), GetRandInt);
224224

225-
for (const CInputCoin &coin : vCoins)
226-
{
227-
if (coin.txout.nValue == nTargetValue)
228-
{
229-
setCoinsRet.insert(coin);
230-
nValueRet += coin.txout.nValue;
225+
for (const OutputGroup& group : groups) {
226+
if (group.m_value == nTargetValue) {
227+
util::insert(setCoinsRet, group.m_outputs);
228+
nValueRet += group.m_value;
231229
return true;
232-
}
233-
else if (coin.txout.nValue < nTargetValue + MIN_CHANGE)
234-
{
235-
vValue.push_back(coin);
236-
nTotalLower += coin.txout.nValue;
237-
}
238-
else if (!coinLowestLarger || coin.txout.nValue < coinLowestLarger->txout.nValue)
239-
{
240-
coinLowestLarger = coin;
230+
} else if (group.m_value < nTargetValue + MIN_CHANGE) {
231+
applicable_groups.push_back(group);
232+
nTotalLower += group.m_value;
233+
} else if (!lowest_larger || group.m_value < lowest_larger->m_value) {
234+
lowest_larger = group;
241235
}
242236
}
243237

244-
if (nTotalLower == nTargetValue)
245-
{
246-
for (const auto& input : vValue)
247-
{
248-
setCoinsRet.insert(input);
249-
nValueRet += input.txout.nValue;
238+
if (nTotalLower == nTargetValue) {
239+
for (const auto& group : applicable_groups) {
240+
util::insert(setCoinsRet, group.m_outputs);
241+
nValueRet += group.m_value;
250242
}
251243
return true;
252244
}
253245

254-
if (nTotalLower < nTargetValue)
255-
{
256-
if (!coinLowestLarger)
257-
return false;
258-
setCoinsRet.insert(coinLowestLarger.get());
259-
nValueRet += coinLowestLarger->txout.nValue;
246+
if (nTotalLower < nTargetValue) {
247+
if (!lowest_larger) return false;
248+
util::insert(setCoinsRet, lowest_larger->m_outputs);
249+
nValueRet += lowest_larger->m_value;
260250
return true;
261251
}
262252

263253
// Solve subset sum by stochastic approximation
264-
std::sort(vValue.begin(), vValue.end(), descending);
254+
std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
265255
std::vector<char> vfBest;
266256
CAmount nBest;
267257

268-
ApproximateBestSubset(vValue, nTotalLower, nTargetValue, vfBest, nBest);
269-
if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE)
270-
ApproximateBestSubset(vValue, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest);
258+
ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
259+
if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) {
260+
ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest);
261+
}
271262

272263
// If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
273264
// or the next bigger coin is closer), return the bigger coin
274-
if (coinLowestLarger &&
275-
((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || coinLowestLarger->txout.nValue <= nBest))
276-
{
277-
setCoinsRet.insert(coinLowestLarger.get());
278-
nValueRet += coinLowestLarger->txout.nValue;
279-
}
280-
else {
281-
for (unsigned int i = 0; i < vValue.size(); i++)
282-
if (vfBest[i])
283-
{
284-
setCoinsRet.insert(vValue[i]);
285-
nValueRet += vValue[i].txout.nValue;
265+
if (lowest_larger &&
266+
((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->m_value <= nBest)) {
267+
util::insert(setCoinsRet, lowest_larger->m_outputs);
268+
nValueRet += lowest_larger->m_value;
269+
} else {
270+
for (unsigned int i = 0; i < applicable_groups.size(); i++) {
271+
if (vfBest[i]) {
272+
util::insert(setCoinsRet, applicable_groups[i].m_outputs);
273+
nValueRet += applicable_groups[i].m_value;
286274
}
275+
}
287276

288277
if (LogAcceptCategory(BCLog::SELECTCOINS)) {
289278
LogPrint(BCLog::SELECTCOINS, "SelectCoins() best subset: "); /* Continued */
290-
for (unsigned int i = 0; i < vValue.size(); i++) {
279+
for (unsigned int i = 0; i < applicable_groups.size(); i++) {
291280
if (vfBest[i]) {
292-
LogPrint(BCLog::SELECTCOINS, "%s ", FormatMoney(vValue[i].txout.nValue)); /* Continued */
281+
LogPrint(BCLog::SELECTCOINS, "%s ", FormatMoney(applicable_groups[i].m_value)); /* Continued */
293282
}
294283
}
295284
LogPrint(BCLog::SELECTCOINS, "total %s\n", FormatMoney(nBest));

‎src/wallet/coinselection.h‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -95,9 +95,9 @@ struct OutputGroup
9595
bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
9696
};
9797

98-
bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees);
98+
bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees);
9999

100100
// Original coin selection algorithm as a fallback
101-
bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet);
101+
bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet);
102102

103103
#endif // BITCOIN_WALLET_COINSELECTION_H

0 commit comments

Comments
 (0)