refactor: Optimize BnB exploration #32150

1. 
   murchandamus commented at 2:33 am on March 27, 2025: contributor

   This PR refactors the implementation of the BnB coinselection algorithm to skip the duplicate evaluation of previously visited input selections.

   (First Draft, needs some cleaning up)

2. 
   DrahtBot commented at 2:33 am on March 27, 2025: contributor

   The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

   Code Coverage & Benchmarks

   For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32150.

   Reviews

   See the guideline for information on the review process.

   Type	Reviewers
   Concept ACK	yancyribbens

   If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

   Conflicts

   Reviewers, this pull request conflicts with the following ones:

   • #29532 (Refactor BnB tests by murchandamus)

   If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

3. DrahtBot added the label Refactoring on Mar 27, 2025
4. murchandamus marked this as a draft on Mar 27, 2025
5. coinselection: Count BnB iterations e2a4d86131
6. coinselection: rewrite BnB in CoinGrinder-style

   In the original implementation of BnB, the state of the search is
   backtracked by explicitly walking back to the omission branch and then
   testing again. This retests an equivalent candidate set as before, e.g.,
   after backtracking from {ABC}, it would evaluate {AB_}, before trying
   {AB_D}, but {AB_} is equivalent to {AB} which was tested before.
   
   CoinGrinder tracks the state of the search instead by remembering which
   UTXO was last added and explicitly shifting from that UTXO directly to
   the next, so after {ABC}, it will immediately move on to {AB_D}. We
   replicate this approach here.

   51a22db993
7. coinselection: Track whether BnB completed

   BnB may not be able to exhaustively search all potentially interesting
   combinations for large UTXO pools, so we keep track of whether the
   search was terminated by the iteration limit.

   b3a5bd9f3d
8. coinselection: BnB skip exploring high waste 2490306d60
9. coinselection: Track effectve_value 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 original 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.

   4aeffd685e
10. opt: Skip evaluation of equivalent input sets

    When two successive UTXOs match in effective value and weight, we can
    skip the second if the prior is not selected: adding it would create an
    equivalent input set to a previously evaluated.
    
    E.g. if we have three UTXOs with effective values {5, 3, 3} of the same
    weight each, we want to evaluate
    {5, _, _}, {5, 3, _}, {5, 3, 3}, {_, 3, _}, {_, 3, 3},
    but skip {5, _, 3}, and {_, _, 3}, because the first 3 is not selected,
    and we therefore do not need to evaluate the second 3 at the same
    position in the input set.
    
    If we reach the end of the branch, we must SHIFT the previously selected
    UTXO group instead.

    0d2e9aac18
11. opt: Skip UTXOs with worse waste, same eff_value

    When two successive UTXOs differ in waste but match in effective value,
    we can skip the second if the first is not selected, because all input
    sets we can generate by swapping out a less wasteful UTXOs with a more
    wastefull UTXO of matching effective value would be strictly worse.

    613df18b00
12. murchandamus force-pushed on Mar 27, 2025
13. 
    yancyribbens commented at 4:05 pm on March 27, 2025: contributor

    Concept ACK
14. 
    yancyribbens commented at 4:12 pm on March 27, 2025: contributor

    I ran benchmarking on master and benchmarking on this branch since it’s fairly large change.

    master:

    0|               ns/op |                op/s |    err% |     total | benchmark
    1|--------------------:|--------------------:|--------:|----------:|:----------
    2|       43,633,696.00 |               22.92 |    0.1% |      0.48 | `CoinSelection`
    

    https://github.com/bitcoin/bitcoin/pull/32150/commits/e2a4d86131e8f1661eb450c50b8072147965b111:

    0
    1|               ns/op |                op/s |    err% |     total | benchmark
    2|--------------------:|--------------------:|--------:|----------:|:----------
    3|       40,433,894.00 |               24.73 |    0.1% |      0.44 | `CoinSelection`
    

    looks like a marginal improvement in bechmarked performance.

Contributors
murchandamus DrahtBot yancyribbens

Labels
Refactoring