From 13161ecf032b7a850686e5942c12222c8f3d0d52 Mon Sep 17 00:00:00 2001
From: Murch <murch@murch.one>
Date: Mon, 8 Jan 2024 13:04:29 -0500
Subject: 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.
---
 src/wallet/test/coinselector_tests.cpp | 15 +++++++--------
 1 file changed, 7 insertions(+), 8 deletions(-)

(limited to 'src/wallet/test')

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()));
     }
 }
-- 
cgit v1.2.3