Refactoring: optimize SelectCoinsBnB

martinus commented at 3:37 pm on May 4, 2018: contributor

Some simple optimizations to SelectCoinsBnB. In total these changes sum up to a speedup of a factor of about 2.4 on my machine:

0BnBExhaustion, 5, 650, 2.08837, 0.000634196, 0.000660664, 0.000638457  # before
1BnBExhaustion, 5, 2300, 4.89576, 0.000422629, 0.000429628, 0.000424571 # std::vector<char>
2BnBExhaustion, 5, 2300, 3.48065, 0.000299667, 0.000308361, 0.000301751 # with curr_selection_size
3BnBExhaustion, 5, 2300, 3.08375, 0.000266867, 0.000270109, 0.00026751  # [] instead of .at

These changes are minor code refactoring that should not change the behaviour of the algorithm in any way.

replaces std::vector<bool> with std::vector<char>

std::vector<bool> is unfortunately very slow. This change replaces it with std::vector<char>
like it is done in ApproximateBestSubset. Also updates number of iterations for the benchmark.

The performance difference is quite significant:

BnBExhaustion, 5, 650, 2.08837, 0.000634196, 0.000660664, 0.000638457  # before
BnBExhaustion, 5, 2300, 4.89576, 0.000422629, 0.000429628, 0.000424571 # after

This changes speeds up the benchmark by a factor of about 1.5.

4eb5025eae

Use indexing instead of push_back() / pop_back

Using a preallocated std::vector<char> with indexing instead of push_back and
pop_back further speeds up the algorithm:

BnBExhaustion, 5, 2300, 4.89576, 0.000422629, 0.000429628, 0.000424571 # std::vector<const>
BnBExhaustion, 5, 2300, 3.48065, 0.000299667, 0.000308361, 0.000301751 # with indexing

Speedup is a factor of 1.4 on my machine.

70be3e2bb7

replace .at() with [] indexing

.at() performs out of bounds checks, which are not necessary because
curr_available_value is used as a stopping criteria anyways. Another speedup:

BnBExhaustion, 5, 2300, 3.48065, 0.000299667, 0.000308361, 0.000301751 # with curr_selection_size
BnBExhaustion, 5, 2300, 3.08375, 0.000266867, 0.000270109, 0.00026751  # [] instead of .at

Speeds up by another factor of 1.13.

d339f1f85e

fanquake added the label Wallet on May 4, 2018

fanquake requested review from achow101 on May 5, 2018

fanquake added the label Refactoring on May 5, 2018

in src/wallet/coinselection.cpp:105 in d339f1f85e

101@@ -102,7 +102,6 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va
102             // explore any more UTXOs to avoid burning money like that.
103             if (curr_waste <= best_waste) {
104                 best_selection = curr_selection;
105-                best_selection.resize(utxo_pool.size());

achow101 commented at 4:31 am on May 5, 2018:

I think you will need to also record curr_selection_size since copying curr_selection may also copy outputs that were selected in previous iterations that are not actually part of the current selection (i.e. selected previously but are at indexes past curr_selection_size).

martinus commented at 5:06 am on May 5, 2018:

I think this is not necessary. If I understand it correctly, what’s right from curr_selection_size will always be 0. The only place where the size goes back is in line 114-117, the loop stops when it finds true then sets it to false. So there is no way that any value right from curr_selection_size will ever be true

achow101 commented at 5:13 am on May 5, 2018:

Indeed, that is the case. Ignore my other comments then.

martinus commented at 5:23 am on May 5, 2018:

Thanks for reviewing!

in src/wallet/coinselection.cpp:157 in d339f1f85e

154@@ -155,9 +155,9 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va
155     // Set output set
156     value_ret = 0;
157     for (size_t i = 0; i < best_selection.size(); ++i) {

achow101 commented at 4:32 am on May 5, 2018:

This should go up to a tracked best_selection_size. Otherwise we may accidentally include outputs which are not part of the best selection as they are at locations past the size of the actual best selection.

in src/wallet/coinselection.cpp:116 in d339f1f85e

110@@ -112,38 +111,39 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va
111         // Backtracking, moving backwards
112         if (backtrack) {
113             // Walk backwards to find the last included UTXO that still needs to have its omission branch traversed.
114-            while (!curr_selection.empty() && !curr_selection.back()) {
115-                curr_selection.pop_back();

achow101 commented at 4:33 am on May 5, 2018:

As an extra belt-and-suspenders check, walking backwards should reset each selection choice to the default state of false.

achow101 commented at 4:34 am on May 5, 2018: member

Mostly looks good, just a few concerns about accidentally including outputs which aren’t actually part of the best selection but were in a different selection iteration.

achow101 commented at 5:13 am on May 5, 2018: member

utACK d339f1f85e3fd7765464718d2c077712a9c07177

DrahtBot commented at 1:54 pm on July 22, 2018: member

DrahtBot added the label Needs rebase on Jul 22, 2018

DrahtBot added the label Up for grabs on Oct 28, 2018

DrahtBot commented at 1:42 pm on October 28, 2018: member

DrahtBot closed this on Oct 28, 2018

laanwj removed the label Needs rebase on Oct 24, 2019

MarcoFalke locked this on Dec 16, 2021

Refactoring: optimize SelectCoinsBnB #13167