test: Add expected result assertions #31656

yancyribbens commented at 7:26 PM on January 14, 2025: contributor

~This is a trivial addition to the test suit, however it shouldn't be required to add debug statements and manually run the tests if someone needs to know the results of this test.~

Add an assertion for the values returned. The goal of the test is to show that a minimal weight selection of UTXOs is returned by coin-grinder. Since there are multiple possible solutions, the added assertion shows that coin-grinder finds the solution with the lowest weight. Without this assertion, it's ambiguous whether or not coin-grinder is returning the solution with the lowest weight.

Remove the check that a result is returned since the expected result assertion implies a result.

DrahtBot commented at 7:26 PM on January 14, 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/31656.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	janb84, murchandamus
Stale ACK	brunoerg

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

DrahtBot added the label Tests on Jan 14, 2025

in src/wallet/test/coinselector_tests.cpp:1185 in dd4f894c58 outdated

1182 | @@ -1183,6 +1183,14 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests)
1183 |              return available_coins;
1184 |          });
1185 |          BOOST_CHECK(res);

brunoerg commented at 12:41 PM on January 15, 2025:

nit: Maybe this BOOST_CHECK is not needed anymore since you're checking the result itself.

yancyribbens commented at 11:02 PM on January 15, 2025:

Good idea, thanks. I've removed the implicit check.

brunoerg approved

brunoerg commented at 12:44 PM on January 15, 2025: contributor

code review ACK dd4f894c58a8f220da224bd220cdad8cd810099a

This is just a simple addition to the test case "Test that two less valuable UTXOs with a combined lower weight are preferred over a more valuable heavier UTXO" and does not increase any test coverage.

For this case, we currently only check whether coin grinder was able to return a result. Now, it checks if the result is the expected one.

yancyribbens force-pushed on Jan 15, 2025

yancyribbens commented at 11:08 PM on January 15, 2025: contributor

Updated commit message since this commit now also removes an assertion as discussed in this PR review.

in src/wallet/test/coinselector_tests.cpp:1186 in 0a4548589f outdated

1181 | @@ -1182,7 +1182,14 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests)
1182 |              }
1183 |              return available_coins;
1184 |          });
1185 | -        BOOST_CHECK(res);
1186 | +        SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
1187 | +        for (int i = 0; i < 10; i++) {

Prabhat1308 commented at 7:31 PM on January 17, 2025:

        for (int i = 0; i < 10; ++i) {

Preference is given to ++i according to developer-notes.md

yancyribbens commented at 10:11 PM on January 20, 2025:

Thanks, done. I did a copy paste from above (line 1177) which I guess should be changed also but not here.

in src/wallet/test/coinselector_tests.cpp:1190 in 0a4548589f outdated

1186 | +        SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
1187 | +        for (int i = 0; i < 10; i++) {
1188 | +            add_coin(2 * COIN, i,expected_result);
1189 | +        }
1190 | +        for (int j = 0; j < 17; ++j) {
1191 | +            add_coin(0.33 * COIN, j + 10, expected_result);

Prabhat1308 commented at 7:33 PM on January 17, 2025:

nit: there seems to be a whitespace needed before expected_result in the first loop. please run a formatter over the code if not done already.

yancyribbens commented at 10:16 PM on January 20, 2025:

nit: there seems to be a whitespace needed before expected_result in the first loop.

Thanks, done.

please run a formatter over the code if not done already.

Do you mean git diff -U0 HEAD~1.. | ./contrib/devtools/clang-format-diff.py -p1 -i -v ?

I get an error after running, maybe my version fo clang-format is different.

Formatting src/wallet/test/coinselector_tests.cpp
/home/yancy/Git/bitcoin/src/.clang-format:46:33: error: invalid boolean
BreakBeforeConceptDeclarations: Always
                                ^~~~~~
Error clang-format: Invalid argument

I'm using Debian clang-format version 14.0.6. Maybe I'll open an issue for this.

Prabhat1308 commented at 7:35 PM on January 17, 2025: none

Code ack 0a45485

left some comments

yancyribbens force-pushed on Jan 20, 2025

yancyribbens commented at 10:17 PM on January 20, 2025: contributor

Updated PR to address format fix request.

fanquake requested review from murchandamus on Jan 22, 2025

yancyribbens commented at 8:41 PM on January 24, 2025: contributor

@brunoerg I'm not sure if you're following this PR anymore but I was thinking maybe the commit message should be improved.

I'm a little perplexed by your quote here though:

"Test that two less valuable UTXOs with a combined lower weight are preferred over a more valuable heavier UTXO" and does not increase any test coverage.

Every UTXO in the test is the same weight (272 WU) so there is no heavy or light UTXO.

yancyribbens force-pushed on Jan 27, 2025

yancyribbens commented at 2:40 PM on January 27, 2025: contributor

Improved the commit message to emphasize why the assertion is needed.

yancyribbens commented at 2:41 PM on January 27, 2025: contributor

This is ready for review @brunoerg @Prabhat1308 @murchandamus

yancyribbens commented at 6:04 PM on January 30, 2025: contributor

@theuni maybe you could review this? In short, the test does not test what it purports to without also asserting the expected result.

yancyribbens commented at 10:36 PM on February 1, 2025: contributor

@achow101 @sipa @sr-gi I noticed you acked the PR that added this test, so I think you can probably quickly review this since you understand the code. friendly ping to review.

The test claims to be testing that a "good solution" is found, although in actuality, there's only an assertion that any solution is found. Coin-grinder is looking for a solution with the lowest weight and all UTXOs in the test have the same weight. Therefore, the solution with the fewest UTXOs will have the lowest weight. That means consuming all of the UTXOs with the most value first before using the smaller UTXOs as is shown by the added assertion in this PR.

murchandamus commented at 3:22 PM on February 5, 2025: contributor

ACK 1801e6520569b8c7b1129cdc8467682a4b8e601c

Sure, this doesn’t hurt and might make it more obvious what CoinGrinder does here. It might be good to also adjust the title of this test for CoinGrinder to "3) Test selection when some selections with sufficient funds would exceed the maximum allowed weight" or similar.

The goal of the test is to show that a minimal weight selection of UTXOs is returned by coin-grinder.

Not really. The weight-optimality of CoinGrinder solutions is shown per the fuzz target coin_grinder_is_optimal.

The purpose of this set of tests is to demonstrate that CoinGrinder succeeds for a few simple challenges and fails as expected when there is no solution. If you search for e.g., the target amount, you might notice that the first few tests of this set were copied from the SRD tests. In the context of the CoinGrinder pull request, the tests were also used to demonstrate how later optimizations reduce the count of attempts necessary to determine the optimal solution.

A falsy "res" indicates that no solution was found. So you are right, this test would accept if CoinGrinder found a solution with 9×2 ₿ and 23–27×0.33 ₿ UTXOs, or 10×2 ₿ and 17–26×0.33 ₿ UTXOs. More than 36 UTXOs would exceed the maximum weight. The test’s title should have been adjusted when the test was reused for CoinGrinder, as the "must find a good solution" refers just to selecting enough funds while staying under the weight limit, but CoinGrinder does even more. Since SRD was improved to drop the smallest value UTXO when its selection is overweight, it will succeed to find a solution, but would likely not find the lowest-weight solution. (Knapsack would likely fail to find a solution, as it doesn’t address excess weight explicitly and its two passes would be conducive to surface the valid selections.BnB would also not find a solution here, because the combinations fall outside of the exact match range.)

Given two sets of UTXOs that all have the same weight, where the first set has higher value and the second set has lower value, the optimal solution is obviously to take all of the higher value UTXOs and enough of the lower value ones. CoinGrinder is a deterministic algorithm that traverses the UTXOs sorted by descending effective value on the inclusion branch first, i.e., it will first select all the highest value UTXOs until it exceeds the target unless it exceeds the maximum weight. The first selection set that exceeds the target amount will be the optimal solution of 10×2 ₿ + 17×0.33 ₿, which is why CoinGrinder will always produce the expected_result that is being tested here, even before the later optimizations allow it to determine that this solution is the optimal solution.

The number of attempts CoinGrinder takes to determine that this is the optimal solution goes from failing to do so (by needing more than 100,000 attempts) to 184, and then 37.

DrahtBot requested review from brunoerg on Feb 5, 2025

yancyribbens commented at 10:53 PM on February 6, 2025: contributor

It might be good to also adjust the title of this test for CoinGrinder to "3) Test selection when some selections with sufficient funds would exceed the maximum allowed weight"

I find the use of "selection" twice in the sentence doesn't add much clarity. Now with the added assertions, I feel like the tittle fits the test however I'm open to a better title.

Not really. The weight-optimality of CoinGrinder solutions is shown per the fuzz target coin_grinder_is_optimal.

Interesting. In the rust version of coin-selection I've been working on, I use fuzz tests to show that there is no overflow or panic, and proptests to show the soundness of randomly generated parameters.

as the "must find a good solution" refers just to selecting enough funds while staying under the weight limit,

I agree this gave me the wrong idea since my intuition of a good solution was in the context of coin-grinder. However, with the added assertions, I think the test title now holds.

Since SRD was improved to drop the smallest value UTXO when its selection is overweight, it will succeed to find a solution, but would likely not find the lowest-weight solution.

Interesting, I need to explore this more since I also would like to apply this improvement to the Rust SRD implementation.

Given two sets of UTXOs that all have the same weight, where the first set has higher value and the second set has lower value, the optimal solution is obviously to take all of the higher value UTXOs and enough of the lower value ones. CoinGrinder is a deterministic algorithm that traverses the UTXOs sorted by descending effective value on the inclusion branch first, i.e., it will first select all the highest value UTXOs until it exceeds the target unless it exceeds the maximum weight. The first selection set that exceeds the target amount will be the optimal solution of 10×2 ₿ + 17×0.33 ₿, which is why CoinGrinder will always produce the expected_result that is being tested here, even before the later optimizations allow it to determine that this solution is the optimal solution.

Right. I've explored this with a rust implementation. It's still a bit rough around the edges.

The number of attempts CoinGrinder takes to determine that this is the optimal solution goes from failing to do so (by needing more than 100,000 attempts) to 184, and then 37.

Yep, I found this to be true when I implemented the basic algo without optimizations (that this test never finishes without the performance optimizations).

yancyribbens force-pushed on Feb 18, 2025

yancyribbens commented at 2:34 PM on February 18, 2025: contributor

rebased

janb84 commented at 4:18 PM on February 21, 2025: contributor

tACK,

Ran unit test
Ran all the tests
Validated the code change.

To consider; change title to "must find a fitting solution" in stead of "must find a good solution", but it's a very small nit.

I also wrote a review note on the PR to document my learning journey

yancyribbens commented at 9:10 PM on February 24, 2025: contributor

@janb84, thanks for the review.

To consider; change title to "must find a fitting solution" in stead of "must find a good solution", but it's a very small nit.

I think "good" is just as descriptive as "fine" here although I really don't care either way about the title.

If you search for e.g., the target amount, you might notice that the first few tests of this set were copied from the SRD tests. In the context of the CoinGrinder pull request, the tests were also used to demonstrate how later optimizations reduce the count of attempts necessary to determine the optimal solution. @murchandamus I see that now: https://github.com/bitcoin/bitcoin/blob/e486597f9a57903600656fb5106858941885852f/src/wallet/test/coinselector_tests.cpp#L1379. However, in the parlance of SRD, there is no such thing as a "good solution", only "a solution" since all solutions are random. Since this test is adapted to CoinGrinder, I think it makes sense to strengthen the test by asserting it finds a "good" solution.

murchandamus commented at 8:37 PM on February 25, 2025: contributor

I find the use of "selection" twice in the sentence doesn't add much clarity. Now with the added assertions, I feel like the tittle fits the test however I'm open to a better title.

Fair enough, maybe use

- // 3) Test selection when some coins surpass the max allowed weight while others not. --> must find a good solution
+ // 3) Test that a solution is found when some combinations would exceed the allowed weight

yancyribbens commented at 10:53 PM on February 25, 2025: contributor

@murchandamus

Test that a solution is found when some combinations would exceed the allowed weight.

That is not inaccurate and better, although coin-grinder does more than that.. I see 7 solutions that are less than max allowed weight 10,000, however the solution returned by coin-grinder is of weight 7,344. Another solution 9×2 ₿ and 17×0.33 ₿ is of weight 7616 which is not returned although still less than the allowed weight.

I think this would be a stronger statement:

Test that a solution is the lowest weight that meets or exceeds the target amount.

murchandamus commented at 2:24 PM on February 27, 2025: contributor

That’s more than what I intended to test here, and especially doesn’t mention that some combinations would exceed the maximal weight. I would suggest:

// 3) Test that the lowest-weight solution is found when some combinations would exceed the allowed weight

test: Add expected result assertions

This test returns the lowest weight solution.  Other possibilities
either exceed allowed weight or result in a higher weight.  Add an
assertion which shows that the lowest weight solution is found and
update the test description accordingly.

Remove the check that a result is returned since the expected result
assertion implies a result.

a015b7e13d

yancyribbens force-pushed on Mar 1, 2025

yancyribbens commented at 5:35 PM on March 1, 2025: contributor

@murchandamus sounds good. I added your suggestion to the test description and updated the commit message accordingly. Also rebased to make testing easier.

janb84 commented at 8:25 PM on March 1, 2025: contributor

re ACK a015b7e

murchandamus commented at 10:52 PM on March 18, 2025: contributor

ACK a015b7e13daacdfb6db0eada50563dec70c5afb2

ryanofsky assigned ryanofsky on Mar 24, 2025

ryanofsky merged this on Mar 24, 2025

ryanofsky closed this on Mar 24, 2025