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):
BnBExhaustion, 5, 650, 2.2564, 0.000672999, 0.000711565, 0.000693112 - master
BnBExhaustion, 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;
I believe this is incorrect. This will set curr_waste to candidate_waste which we don't want.
Fixed.
Dropped the second commit as insignificant, updated the description / benchmarks.
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;
This will lead to an unsigned integer overflow in the case of curr_index == 0. Could change logic and ordering to avoid that?
Fair enough, I moved the subtraction inline, which avoids storing the overflowed value in the 0 case, and is more consistent with prior implementation. Note the behavior is not changed as the 0 case also corresponded to curr_selection being empty.
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--174a7506f384e20aa4161008e828411d-->
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.
Optional: Please update comment to "add omitted UTXOs back to lookahead before traversing the omission branch of last included UTXO"
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) {
Optional: given that we now have two indices incremented in this for-loop, perhaps rename i to try and curr_index to utxo_pool_depth.
Done, though I went with 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?
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.
ACK e6b45f39457f5d52232faf5b9395b7420a52bdc5
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) {
33e8d4b4b8999d5f80227fa20bed7271ab0976bd should be squashed into cec31e08ca64168fd084bc71ec250d8eaca99537, it was confusing to me that we're introducing a new 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?
assert(utxo_pool_index == curr_selection.back());
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 | + {
In cec31e08ca64168fd084bc71ec250d8eaca99537: I actually think the original condition for exclusion shortcut was clearer, and don't really see a reason to DeMorgans it
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.
Okay, makes sense
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
reACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c
reACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c