Merge bitcoin/bitcoin#13226: Optimize SelectCoinsBnB by tracking the selection by index rather than by position

9d2005285c77f6c4148bccfa0b8b9135abfa021c doc: Revise comments and whitespace to clarify (Ben Woosley)
def43a4d888b4a21c082404d1b25707c481d7625 refactor: Rename i to curr_try in SelectCoinsBnB (Ben Woosley)
1dd092367789749527777ac2b256e639f5706584 refactor: Track BnB selection by index (Ben Woosley)

Pull request description:

  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
  ```

ACKs for top commit:
  achow101:
    reACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c
  glozow:
    code review ACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c
  Xekyo:
    reACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c

Tree-SHA512: 453ea11ad58c48928dc76956e3e98916f6924e95510eb02fe89a899ff102fe9cc08a04d557f381ad0218a210275e5383101d971c1ffad38b06b1c57d81144315

1 files changed, 28 insertions, 32 deletions

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 513572da45..20891a3e28 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -66,14 +66,13 @@ 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
-    curr_selection.reserve(utxo_pool.size());
+    std::vector<size_t> curr_selection; // selected utxo indexes
 
     // Calculate curr_available_value
     CAmount curr_available_value = 0;
     for (const OutputGroup& utxo : utxo_pool) {
-        // Assert that this utxo is not negative. It should never be negative, effective value calculation should have removed it
+        // Assert that this utxo is not negative. It should never be negative,
+        // effective value calculation should have removed it
         assert(utxo.GetSelectionAmount() > 0);
         curr_available_value += utxo.GetSelectionAmount();
     }
@@ -85,15 +84,15 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
     std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
 
     CAmount curr_waste = 0;
-    std::vector<bool> best_selection;
+    std::vector<size_t> best_selection;
     CAmount best_waste = MAX_MONEY;
 
     // Depth First search loop for choosing the UTXOs
-    for (size_t i = 0; i < TOTAL_TRIES; ++i) {
+    for (size_t curr_try = 0, utxo_pool_index = 0; curr_try < TOTAL_TRIES; ++curr_try, ++utxo_pool_index) {
         // Conditions for starting a backtrack
         bool backtrack = false;
-        if (curr_value + curr_available_value < selection_target ||                // Cannot possibly reach target with the amount remaining in the curr_available_value.
-            curr_value > selection_target + cost_of_change ||    // Selected value is out of range, go back and try other branch
+        if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value.
+            curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch
             (curr_waste > best_waste && (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0)) { // Don't select things which we know will be more wasteful if the waste is increasing
             backtrack = true;
         } else if (curr_value >= selection_target) {       // Selected value is within range
@@ -104,7 +103,6 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
             // 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());
                 best_waste = curr_waste;
                 if (best_waste == 0) {
                     break;
@@ -114,38 +112,38 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
             backtrack = true;
         }
 
-        // 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();
-                curr_available_value += utxo_pool.at(curr_selection.size()).GetSelectionAmount();
-            }
-
+        if (backtrack) { // Backtracking, moving backwards
             if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
                 break;
             }
 
+            // Add omitted UTXOs back to lookahead before traversing the omission branch of last included UTXO.
+            for (--utxo_pool_index; utxo_pool_index > curr_selection.back(); --utxo_pool_index) {
+                curr_available_value += utxo_pool.at(utxo_pool_index).GetSelectionAmount();
+            }
+
             // Output was included on previous iterations, try excluding now.
-            curr_selection.back() = false;
-            OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1);
+            assert(utxo_pool_index == curr_selection.back());
+            OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
             curr_value -= utxo.GetSelectionAmount();
             curr_waste -= utxo.fee - utxo.long_term_fee;
+            curr_selection.pop_back();
         } else { // Moving forwards, continuing down this branch
-            OutputGroup& utxo = utxo_pool.at(curr_selection.size());
+            OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
 
             // Remove this utxo from the curr_available_value utxo amount
             curr_available_value -= utxo.GetSelectionAmount();
 
-            // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded. Since the ratio of fee to
-            // long term fee is the same, we only need to check if one of those values match in order to know that the waste is the same.
-            if (!curr_selection.empty() && !curr_selection.back() &&
-                utxo.GetSelectionAmount() == utxo_pool.at(curr_selection.size() - 1).GetSelectionAmount() &&
-                utxo.fee == utxo_pool.at(curr_selection.size() - 1).fee) {
-                curr_selection.push_back(false);
-            } else {
+            if (curr_selection.empty() ||
+                // The previous index is included and therefore not relevant for exclusion shortcut
+                (utxo_pool_index - 1) == curr_selection.back() ||
+                // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded.
+                // Since the ratio of fee to long term fee is the same, we only need to check if one of those values match in order to know that the waste is the same.
+                utxo.GetSelectionAmount() != utxo_pool.at(utxo_pool_index - 1).GetSelectionAmount() ||
+                utxo.fee != utxo_pool.at(utxo_pool_index - 1).fee)
+            {
                 // Inclusion branch first (Largest First Exploration)
-                curr_selection.push_back(true);
+                curr_selection.push_back(utxo_pool_index);
                 curr_value += utxo.GetSelectionAmount();
                 curr_waste += utxo.fee - utxo.long_term_fee;
             }
@@ -158,10 +156,8 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
     }
 
     // Set output set
-    for (size_t i = 0; i < best_selection.size(); ++i) {
-        if (best_selection.at(i)) {
-            result.AddInput(utxo_pool.at(i));
-        }
+    for (const size_t& i : best_selection) {
+        result.AddInput(utxo_pool.at(i));
     }
     result.ComputeAndSetWaste(CAmount{0});
     assert(best_waste == result.GetWaste());