bnb: exit selection when best_waste is 0 #18262
Conversation
If we find a solution which has no waste, just use that. This solution is what we would consider to be optimal, and other solutions we find would have to also have 0 waste, so they are equivalent to the first one with 0 waste. Thus we can optimize by just choosing the first one with 0 waste.
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. ConflictsReviewers, this pull request conflicts with the following ones:
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. |
|
Concept ACK |
|
Concept ACK on this as it is an improvement! However, looking at this I had another thought: given we have two possible solutions with 0 waste, would we not want to minimize fees by selecting the one with fewer inputs? So, instead of stopping early we could still run through all the tries and select the best waste option with the least inputs. Actually this could be an additional breaker between any equal waste options. |
Fewer inputs does not necessarily minimize fees. It depends on the exact scripts being used. Regardless, I don't think an explicit check for fees is needed. So long as |
just to nit, in this case, |
|
aka concept ACK |
| @@ -176,8 +176,8 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) | |||
| selection.clear(); | |||
|
|
|||
| // Select 5 Cent | |||
| add_coin(3 * CENT, 3, actual_selection); | |||
| add_coin(2 * CENT, 2, actual_selection); | |||
| add_coin(4 * CENT, 4, actual_selection); | |||
There was a problem hiding this comment.
There is an optimal result earlier in the selection so that changes the outcome here.
|
Obvious concept ACK. |
That's also a question I have. My intuition is it's very unlikely to have an exact match in practice. Also, I think If the cost of change is sufficiently small, its unlikely to have any match including an exact match. |
|
I think this condition is fairly hard to hit and probably doesn't make much of a difference. I think that most wallets will hit the iteration limit in BnB as we do search for more solutions after finding the first one, so exiting early probably isn't helping that much anyways. |
|
I think this extra logic is really easy to understand and maintainable, therefore should be merged(provided proper review) regardless or not how theoretical people find it. |
|
utACK 9b5950d |
9b5950d bnb: exit selection when best_waste is 0 (Andrew Chow) Pull request description: If we find a solution which has no waste, just use that. This solution is what we would consider to be optimal, and other solutions we find would have to also have 0 waste, so they are equivalent to the first one with 0 waste. Thus we can optimize by just choosing the first one with 0 waste. Closes bitcoin#18257 ACKs for top commit: instagibbs: utACK bitcoin@9b5950d meshcollider: utACK 9b5950d Tree-SHA512: 59565ff4a3d8281e7bc0ce87065a34c8d8bf8a95f628ba96b4fe89f1274979165aea6312e5f1f21b418c8c484aafc5166d22d9eff9d127a8192498625d58c557
9b5950d bnb: exit selection when best_waste is 0 (Andrew Chow) Pull request description: If we find a solution which has no waste, just use that. This solution is what we would consider to be optimal, and other solutions we find would have to also have 0 waste, so they are equivalent to the first one with 0 waste. Thus we can optimize by just choosing the first one with 0 waste. Closes bitcoin#18257 ACKs for top commit: instagibbs: utACK bitcoin@9b5950d meshcollider: utACK 9b5950d Tree-SHA512: 59565ff4a3d8281e7bc0ce87065a34c8d8bf8a95f628ba96b4fe89f1274979165aea6312e5f1f21b418c8c484aafc5166d22d9eff9d127a8192498625d58c557
Summary: 9b5950db8683f9b4be03f79ee0aae8a780b01a4b bnb: exit selection when best_waste is 0 (Andrew Chow) Pull request description: If we find a solution which has no waste, just use that. This solution is what we would consider to be optimal, and other solutions we find would have to also have 0 waste, so they are equivalent to the first one with 0 waste. Thus we can optimize by just choosing the first one with 0 waste. Closes #18257 Backport of Core [[bitcoin/bitcoin#18262 | PR18262]] Test Plan: ninja check Reviewers: #bitcoin_abc, deadalnix Reviewed By: #bitcoin_abc, deadalnix Differential Revision: https://reviews.bitcoinabc.org/D8064
9b5950d bnb: exit selection when best_waste is 0 (Andrew Chow) Pull request description: If we find a solution which has no waste, just use that. This solution is what we would consider to be optimal, and other solutions we find would have to also have 0 waste, so they are equivalent to the first one with 0 waste. Thus we can optimize by just choosing the first one with 0 waste. Closes bitcoin#18257 ACKs for top commit: instagibbs: utACK bitcoin@9b5950d meshcollider: utACK 9b5950d Tree-SHA512: 59565ff4a3d8281e7bc0ce87065a34c8d8bf8a95f628ba96b4fe89f1274979165aea6312e5f1f21b418c8c484aafc5166d22d9eff9d127a8192498625d58c557
9b5950d bnb: exit selection when best_waste is 0 (Andrew Chow) Pull request description: If we find a solution which has no waste, just use that. This solution is what we would consider to be optimal, and other solutions we find would have to also have 0 waste, so they are equivalent to the first one with 0 waste. Thus we can optimize by just choosing the first one with 0 waste. Closes bitcoin#18257 ACKs for top commit: instagibbs: utACK bitcoin@9b5950d meshcollider: utACK 9b5950d Tree-SHA512: 59565ff4a3d8281e7bc0ce87065a34c8d8bf8a95f628ba96b4fe89f1274979165aea6312e5f1f21b418c8c484aafc5166d22d9eff9d127a8192498625d58c557
9b5950d bnb: exit selection when best_waste is 0 (Andrew Chow) Pull request description: If we find a solution which has no waste, just use that. This solution is what we would consider to be optimal, and other solutions we find would have to also have 0 waste, so they are equivalent to the first one with 0 waste. Thus we can optimize by just choosing the first one with 0 waste. Closes bitcoin#18257 ACKs for top commit: instagibbs: utACK bitcoin@9b5950d meshcollider: utACK 9b5950d Tree-SHA512: 59565ff4a3d8281e7bc0ce87065a34c8d8bf8a95f628ba96b4fe89f1274979165aea6312e5f1f21b418c8c484aafc5166d22d9eff9d127a8192498625d58c557
9b5950d bnb: exit selection when best_waste is 0 (Andrew Chow) Pull request description: If we find a solution which has no waste, just use that. This solution is what we would consider to be optimal, and other solutions we find would have to also have 0 waste, so they are equivalent to the first one with 0 waste. Thus we can optimize by just choosing the first one with 0 waste. Closes bitcoin#18257 ACKs for top commit: instagibbs: utACK bitcoin@9b5950d meshcollider: utACK 9b5950d Tree-SHA512: 59565ff4a3d8281e7bc0ce87065a34c8d8bf8a95f628ba96b4fe89f1274979165aea6312e5f1f21b418c8c484aafc5166d22d9eff9d127a8192498625d58c557
If we find a solution which has no waste, just use that. This solution
is what we would consider to be optimal, and other solutions we find
would have to also have 0 waste, so they are equivalent to the first
one with 0 waste. Thus we can optimize by just choosing the first one
with 0 waste.
Closes #18257