diff options
author | Murch <murch@murch.one> | 2024-01-08 13:04:29 -0500 |
---|---|---|
committer | Murch <murch@murch.one> | 2024-02-09 11:03:18 +0100 |
commit | 13161ecf032b7a850686e5942c12222c8f3d0d52 (patch) | |
tree | 9cb96bfd4ff94772613f74ae18ff5ce89cb72d43 /src/wallet/test | |
parent | b7672c7cdd87acb105639f475744094b53cc9891 (diff) | |
download | bitcoin-13161ecf032b7a850686e5942c12222c8f3d0d52.tar.xz |
opt: Skip over barren combinations of tiny UTXOs
Given a lot of small amount UTXOs it is possible that the lookahead
indicates sufficient funds, but any combination of them would push us
beyond the current best_weight.
We can estimate a lower bound for the minimal necessary weight to reach
target from the maximal amount and minimal weight in the tail of the
UTXO pool: if adding a number of hypothetical UTXOs of this maximum
amount and minimum weight would not be able to beat `best_weight`, we
can SHIFT to the omission branch, and CUT if the last selected UTXO is
not heavier than the minimum weight of the remainder.
Diffstat (limited to 'src/wallet/test')
-rw-r--r-- | src/wallet/test/coinselector_tests.cpp | 15 |
1 files changed, 7 insertions, 8 deletions
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index 23df7e186c..9a349f0992 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -1111,7 +1111,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) // 4) Test that two less valuable UTXOs with a combined lower weight are preferred over a more valuable heavier UTXO // 5) Test finding a solution in a UTXO pool with mixed weights // 6) Test that the lightest solution among many clones is found - // 7) Lots of tiny UTXOs of different amounts quickly exhausts the search attempts + // 7) Test that lots of tiny UTXOs can be skipped if they are too heavy while there are enough funds in lookahead FastRandomContext rand; CoinSelectionParams dummy_params{ // Only used to provide the 'avoid_partial' flag. @@ -1180,7 +1180,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) }); BOOST_CHECK(res); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. - size_t expected_attempts = 184; + size_t expected_attempts = 37; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } @@ -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 = 218; + size_t expected_attempts = 92; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } @@ -1270,14 +1270,13 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) add_coin(1 * COIN, 0, expected_result); 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 = 42; + size_t expected_attempts = 38; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } { // ################################################################################################################# - // 7) Lots of tiny UTXOs of different amounts quickly exhausts the search attempts + // 7) Test that lots of tiny UTXOs can be skipped if they are too heavy while there are enough funds in lookahead // ################################################################################################################# CAmount target = 1.9L * COIN; int max_weight = 40000; // WU @@ -1293,11 +1292,11 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) return available_coins; }); SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG); - add_coin(1.8 * COIN, 1, expected_result); + add_coin(1 * COIN, 1, expected_result); add_coin(1 * COIN, 2, 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 = 100'000; + size_t expected_attempts = 7; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } } |