Refactoring: optimize SelectCoinsBnB #13167

pull martinus wants to merge 3 commits into bitcoin:master from martinus:optimize-SelectCoinsBnB changing 2 files +21 −21

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:

BnBExhaustion, 5, 650, 2.08837, 0.000634196, 0.000660664, 0.000638457  # before
BnBExhaustion, 5, 2300, 4.89576, 0.000422629, 0.000429628, 0.000424571 # std::vector<char>
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

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

Needs rebase
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

There hasn't been much activity lately and the patch still needs rebase, so I am closing this for now. Please let me know when you want to continue working on this, so the pull request can be re-opened.
DrahtBot closed this on Oct 28, 2018
laanwj removed the label Needs rebase on Oct 24, 2019
MarcoFalke locked this on Dec 16, 2021

Contributors

martinus

achow101

DrahtBot

Labels

Refactoring Wallet Up for grabs

Linked (view graph)

#13226 Optimize SelectCoinsBnB by tracking the selection by index rather than by position