Refactoring: optimize SelectCoinsBnB #13167
Conversation
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.
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.
.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.
| @@ -102,7 +102,6 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va | |||
| // explore any more UTXOs to avoid burning money like that. | |||
| if (curr_waste <= best_waste) { | |||
| best_selection = curr_selection; | |||
| best_selection.resize(utxo_pool.size()); | |||
There was a problem hiding this comment.
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).
There was a problem hiding this comment.
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
There was a problem hiding this comment.
Indeed, that is the case. Ignore my other comments then.
There was a problem hiding this comment.
Thanks for reviewing!
| @@ -155,9 +155,9 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va | |||
| // Set output set | |||
| value_ret = 0; | |||
| for (size_t i = 0; i < best_selection.size(); ++i) { | |||
There was a problem hiding this comment.
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.
| @@ -112,38 +111,39 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va | |||
| // Backtracking, moving backwards | |||
| if (backtrack) { | |||
| // Walk backwards to find the last included UTXO that still needs to have its omission branch traversed. | |||
| while (!curr_selection.empty() && !curr_selection.back()) { | |||
| curr_selection.pop_back(); | |||
There was a problem hiding this comment.
As an extra belt-and-suspenders check, walking backwards should reset each selection choice to the default state of false.
|
utACK d339f1f |
| Needs rebase |
| 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. |
Some simple optimizations to
SelectCoinsBnB. In total these changes sum up to a speedup of a factor of about 2.4 on my machine:These changes are minor code refactoring that should not change the behaviour of the algorithm in any way.