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):
0BnBExhaustion, 5, 650, 2.2564, 0.000672999, 0.000711565, 0.000693112 - master
1BnBExhaustion, 5, 650, 1.76232, 0.000528563, 0.000568806, 0.000539147 - this PR
103 // explore any more UTXOs to avoid burning money like that.
104- if (curr_waste <= best_waste) {
105+ if (candidate_waste <= best_waste) {
106 best_selection = curr_selection;
107- best_waste = curr_waste;
108+ best_waste = curr_waste = candidate_waste;
curr_waste to candidate_waste which we don’t want.
145- if (!curr_selection.empty() && !curr_selection.back() &&
146- utxo.effective_value == utxo_pool.at(curr_selection.size() - 1).effective_value &&
147- utxo.fee == utxo_pool.at(curr_selection.size() - 1).fee) {
148- curr_selection.push_back(false);
149- } else {
150+ size_t prev_index = curr_index - 1;
curr_index == 0. Could change logic and ordering to avoid that?
curr_selection being empty.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
No conflicts as of last run.
122+ break;
123 }
124
125- if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
126- break;
127+ // Walk backwards to find the last included UTXO that still needs to have its omission branch traversed.
155+ (curr_index - 1) == curr_selection.back() ||
156+ utxo.GetSelectionAmount() != utxo_pool.at(curr_index - 1).GetSelectionAmount() ||
157+ utxo.fee != utxo_pool.at(curr_index - 1).fee) {
158 // Inclusion branch first (Largest First Exploration)
159- curr_selection.push_back(true);
160+ curr_selection.push_back(curr_index);
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.
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.
88+ std::vector<size_t> best_selection;
89 CAmount best_waste = MAX_MONEY;
90
91 // Depth First search loop for choosing the UTXOs
92- for (size_t i = 0; i < TOTAL_TRIES; ++i) {
93+ for (size_t i = 0, curr_index = 0; i < TOTAL_TRIES; ++i, ++curr_index) {
i to try and curr_index to utxo_pool_depth.
utxo_pool_index, and curr_try as try is a keyword.
Code review ACK 7714444c08ce103297508bd1fb4b08bc67f6f637
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?
66@@ -67,7 +67,7 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
67 SelectionResult result(selection_target);
68 CAmount curr_value = 0;
69
70- std::vector<bool> curr_selection; // select the utxo at this index
71+ std::vector<size_t> curr_selection; // selected utxo indexes
72 curr_selection.reserve(utxo_pool.size());
in cec31e08ca64168fd084bc71ec250d8eaca99537:
Given that a big motivation here is to not allocate memory for every UTXO, we should probably remove this reserve(utxo_pool.size()) line
88@@ -89,7 +89,7 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
89 CAmount best_waste = MAX_MONEY;
90
91 // Depth First search loop for choosing the UTXOs
92- for (size_t curr_try = 0, curr_index = 0; curr_try < TOTAL_TRIES; ++curr_try, ++curr_index) {
93+ for (size_t curr_try = 0, utxo_pool_index = 0; curr_try < TOTAL_TRIES; ++curr_try, ++utxo_pool_index) {
curr_index variable in one commit, and then renaming it 2 commits later
132+ }
133+
134 // Output was included on previous iterations, try excluding now.
135- curr_selection.back() = false;
136- OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1);
137+ OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
in cec31e08ca64168fd084bc71ec250d8eaca99537: could be worth adding this line as a sanity check?
0 assert(utxo_pool_index == curr_selection.back());
1 OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
154+ if (curr_selection.empty() ||
155+ // The previous index is included and therefore not relevant for exclusion shortcut
156+ (curr_index - 1) == curr_selection.back() ||
157+ utxo.GetSelectionAmount() != utxo_pool.at(curr_index - 1).GetSelectionAmount() ||
158+ utxo.fee != utxo_pool.at(curr_index - 1).fee)
159+ {
don’t really see a reason to DeMorgans it
The reason is that one of the cases is no longer acted on, since we don’t track excluded utxos in curr_selection, so we only have a no-op in the “positive” case, hence the desire to invert the condition.
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.
code review ACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c
My bench results on master:
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 2,468,488.00 | 405.11 | 0.5% | 0.03 | BnBExhaustion |
on this branch:
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 1,396,491.00 | 716.08 | 0.4% | 0.02 | BnBExhaustion |