Optimize SelectCoinsBnB by tracking the selection by index rather than by position #13226
Conversation
|
/cc @achow101 this is the last of my BnB series |
d74e583 to
08b8dbd
Compare
08b8dbd to
514e49e
Compare
|
Rebased for #13691 |
514e49e to
109ca2e
Compare
|
Dropped the second commit as insignificant, updated the description / benchmarks. |
109ca2e to
4c24e8e
Compare
4c24e8e to
c95aa43
Compare
|
Closing this given #13167 is closed, and optimizing coin selection perf isn't much of a priority. |
|
@xekyo take a look |
2ce79b3 to
7714444
Compare
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. ConflictsNo conflicts as of last run. |
There was a problem hiding this comment.
Code review ACK 7714444
Regarding the commit message, AFAIU the complexity reduction applies to the vector of the selection index and the assembly of the best_selection. I'm surprised that's good for such a speedup. Am I missing something why this is so much faster?
src/wallet/coinselection.cpp
Outdated
| if (curr_selection.empty() || | ||
| // The previous index is included and therefore not relevant for exclusion shortcut | ||
| (curr_index - 1) == curr_selection.back() || | ||
| utxo.GetSelectionAmount() != utxo_pool.at(curr_index - 1).GetSelectionAmount() || | ||
| utxo.fee != utxo_pool.at(curr_index - 1).fee) { | ||
| // Inclusion branch first (Largest First Exploration) | ||
| curr_selection.push_back(true); | ||
| curr_selection.push_back(curr_index); |
There was a problem hiding this comment.
Took me a bit to verify whether this is equivalent, but this does look correct to me.
Optional: The comment about "fee to long term fee" threw me off at first, perhaps it would actually be clearer to drop the second sentence of the comment before the if-block.
There was a problem hiding this comment.
Yeah - as an aid to the reviewer, I'm applying De Morgan's law here.
I left the comment but moved it to above the relevant check.
|
Hi @Empact, are you still making progress on this, or would you be open to the idea of someone else adopting the PR? I was just considering amending my prior commentary after not looking at this for a while, but I would be happy to take a look at the failing check instead, if you aren't working on this anymore. |
|
Hey Mark, yes I'd like to pick it back up again - have been otherwise engaged for a while but I expect to have time next week. |
4a218f3 to
e6b45f3
Compare
|
ACK e6b45f3 |
src/wallet/coinselection.cpp
Outdated
| @@ -67,7 +67,7 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo | |||
| SelectionResult result(selection_target); | |||
| CAmount curr_value = 0; | |||
|
|
|||
| std::vector<bool> curr_selection; // select the utxo at this index | |||
| std::vector<size_t> curr_selection; // selected utxo indexes | |||
| curr_selection.reserve(utxo_pool.size()); | |||
There was a problem hiding this comment.
in cec31e0:
Given that a big motivation here is to not allocate memory for every UTXO, we should probably remove this reserve(utxo_pool.size()) line
This is a performance optimization - rather than track all visited values in a bool vector, track the selected index in a vector. This results in a complexity reduction of O(utxo_size) to O(selection_size).
Clarifies purpose and removes name collisions with other indicies.
e6b45f3 to
9d20052
Compare
|
reACK 9d20052 |
This is prompted by #13167 and presented as a friendly alternative to it.
IMO you can improve code readability and performance by about 20% by tracking the selected utxos by index, rather than by position. This reduces the storage access complexity from roughly O(utxo_size) to O(selection_size).
On my machine (median of 5 trials):