diff options
author | Murch <murch@murch.one> | 2024-01-08 15:17:36 -0500 |
---|---|---|
committer | Murch <murch@murch.one> | 2024-02-09 10:51:17 +0100 |
commit | 407b1e3432b77511900b77be84d5d7450352f462 (patch) | |
tree | b2c5c91bcd8b20998a660199334d44f96efb369a | |
parent | 5f84f3cc043c5fb15072f5072fee752eaa01a2ec (diff) | |
download | bitcoin-407b1e3432b77511900b77be84d5d7450352f462.tar.xz |
opt: Track remaining effective_value in lookahead
Introduces a dedicated data structure to track the total
effective_value available in the remaining UTXOs at each index of the
UTXO pool. In contrast to the approach in BnB, this allows us to
immediately jump to a lower index instead of visiting every UTXO to add
back their eff_value to the lookahead.
-rw-r--r-- | src/wallet/coinselection.cpp | 19 | ||||
-rw-r--r-- | src/wallet/test/coinselector_tests.cpp | 4 |
2 files changed, 15 insertions, 8 deletions
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index cf666e7459..fb63e92bb8 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -313,13 +313,17 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_weight) { std::sort(utxo_pool.begin(), utxo_pool.end(), descending); + // The sum of UTXO amounts after this UTXO index, e.g. lookahead[5] = Σ(UTXO[6+].amount) + std::vector<CAmount> lookahead(utxo_pool.size()); - // Check that there are sufficient funds + // Calculate lookahead values, and check that there are sufficient funds CAmount total_available = 0; - for (const OutputGroup& utxo : utxo_pool) { - // Assert UTXOs with non-positive effective value have been filtered - Assume(utxo.GetSelectionAmount() > 0); - total_available += utxo.GetSelectionAmount(); + for (size_t i = 0; i < utxo_pool.size(); ++i) { + size_t index = utxo_pool.size() - 1 - i; // Loop over every element in reverse order + lookahead[index] = total_available; + // UTXOs with non-positive effective value must have been filtered + Assume(utxo_pool[index].GetSelectionAmount() > 0); + total_available += utxo_pool[index].GetSelectionAmount(); } const CAmount total_target = selection_target + change_target; @@ -409,7 +413,10 @@ util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, c ++curr_try; // EVALUATE current selection: check for solutions and see whether we can CUT or SHIFT before EXPLORING further - if (curr_weight > max_weight) { + if (curr_amount + lookahead[curr_selection.back()] < total_target) { + // Insufficient funds with lookahead: CUT + should_cut = true; + } else if (curr_weight > max_weight) { // max_weight exceeded: SHIFT max_tx_weight_exceeded = true; should_shift = true; diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index fe9922e31c..c335a32ec6 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -1231,7 +1231,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) add_coin(4 * COIN, 3, expected_result); BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. - size_t expected_attempts = 525; + size_t expected_attempts = 281; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } @@ -1271,7 +1271,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. // If this takes more attempts, the implementation has regressed - size_t expected_attempts = 82'815; + size_t expected_attempts = 82'407; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } |