coinselection: Optimize BnB exploration

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

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

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.

As fewer nodes are visited, this approach will enumerate more possible combinations than the original implementation given the same limit for iterations.

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

No conflicts as of last run.

DrahtBot added the label Refactoring on Mar 27, 2025

murchandamus marked this as a draft on Mar 27, 2025

murchandamus force-pushed on Mar 27, 2025

yancyribbens commented at 4:05 pm on March 27, 2025: contributor

Concept ACK

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.

murchandamus force-pushed on Apr 1, 2025

murchandamus commented at 0:05 am on April 1, 2025: contributor

Rebased on #29532

murchandamus force-pushed on Apr 1, 2025

in src/wallet/test/coinselection_tests.cpp:133 in d765ba9ae5 outdated

129@@ -130,14 +130,14 @@ BOOST_AUTO_TEST_CASE(bnb_test)
130     AddCoins(utxo_pool, {1 * CENT, 3 * CENT, 5 * CENT});
131 
132     // Simple success cases
133-    TestBnBSuccess("Select smallest UTXO", utxo_pool, /*selection_target=*/1 * CENT, /*expected_input_amounts=*/{1 * CENT}, /*expected_attempts=*/6);
134-    TestBnBSuccess("Select middle UTXO", utxo_pool, /*selection_target=*/3 * CENT, /*expected_input_amounts=*/{3 * CENT}, /*expected_attempts=*/4);
135-    TestBnBSuccess("Select biggest UTXO", utxo_pool, /*selection_target=*/5 * CENT, /*expected_input_amounts=*/{5 * CENT}, /*expected_attempts=*/2);
136-    TestBnBSuccess("Select two UTXOs", utxo_pool, /*selection_target=*/4 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/6);
137-    TestBnBSuccess("Select all UTXOs", utxo_pool, /*selection_target=*/9 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT, 5 * CENT}, /*expected_attempts=*/6);
138+    TestBnBSuccess("Select smallest UTXO", utxo_pool, /*selection_target=*/1 * CENT, /*expected_input_amounts=*/{1 * CENT}, /*expected_attempts=*/3);

yancyribbens commented at 7:12 pm on April 1, 2025:

Nice, it looks like the backtrack iterations are no longer recorded which effectively makes this probably more of an optimization than a refactor. Now it’s possible more solutions can be found since the number of times the loop will run is effectively more improving search resolution. May be worth adding a note of that to the commit message.

murchandamus commented at 9:35 pm on April 1, 2025:

Thanks, I renamed the PR and added more explanation to the opening comment.

murchandamus renamed this:
~~refactor: Optimize BnB exploration~~
coinselection: Optimize BnB exploration
on Apr 1, 2025

murchandamus commented at 4:14 pm on April 2, 2025: contributor

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

If I remember right the Coin Selection benchmark is rather non-representative. I have a todo to update it somewhere in my backlog.

yancyribbens commented at 4:04 pm on April 3, 2025: contributor

If I remember right the Coin Selection benchmark is rather non-representative. I have a todo to update it somewhere in my backlog.

Good point. I took a quick look, and the current benchmark runs BnB for only 4 iterations. there are 1,000 clones and one non clone so most of the work is done by skipping clones which isn’t very representative as you say.

Instead of keeping this in your backlog, shouldn’t there be an issue opened so it doesn’t get overlooked? Maybe someone else has the bandwidth to pick it up. Possibly I could but I also have a large backlog of I’d like to work on.

Also, I note there is also BnBExhaustion(benchmark::Bench& bench) which is probably more “representative” although it also looks like you have a TODO to re-write that as well:

Worth noting that src/bench/coin_selection.cpp makes a copy of the make_hard_case function (commenting as such), so removal here may lead to confusion unless that benchmark is also updated.

DrahtBot added the label CI failed on Apr 29, 2025

DrahtBot removed the label CI failed on May 2, 2025

murchandamus force-pushed on May 2, 2025

murchandamus force-pushed on May 3, 2025

murchandamus marked this as ready for review on May 6, 2025

coinselection: Track BnB iteration count in result df20dd4f90

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.

9580c0e490

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.

3ba25ba64d

coinselection: BnB skip exploring high waste 813ac54726

coinselection: Track effective_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.

6ff6e98000

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.

ee103e5df9

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.

447551732c

murchandamus force-pushed on May 8, 2025

murchandamus commented at 9:57 pm on May 8, 2025: contributor

The preceding PR #29532 got merged, so this is now ready for review.

coinselection: Optimize BnB exploration #32150

Code Coverage & Benchmarks

Reviews

Conflicts