wallet: Remove redundant waste calculation #26061
There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
|
|
@@ -93,19 +93,24 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo | |
| bool backtrack = false; | ||
| if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value. | ||
| curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch | ||
| (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0) { // Don't select more things if the current fee rate is expensive. | ||
| backtrack = true; | ||
| } else if (curr_value >= selection_target) { // Selected value is within range | ||
|
|
||
| // This is the excess waste for the current iteration. | ||
| curr_waste = (curr_value - selection_target); | ||
|
There was a problem hiding this comment. This is just the excess not the waste. Check line42 in this file or There was a problem hiding this comment. @S3RK shouldn't the variable be called There was a problem hiding this comment. No, |
||
|
|
||
| // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee. | ||
| // However we are not going to explore that because this optimization for the waste is only done when we have hit our target | ||
| // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to | ||
| // explore any more UTXOs to avoid burning money like that. | ||
|
|
||
| // Don't select things which we know will be more wasteful. | ||
| if (curr_waste <= best_waste) { | ||
| best_selection = curr_selection; | ||
| best_waste = curr_waste; | ||
| } | ||
|
|
||
| backtrack = true; | ||
| } | ||
|
|
||
|
|
@@ -123,7 +128,6 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo | |
| assert(utxo_pool_index == curr_selection.back()); | ||
| OutputGroup& utxo = utxo_pool.at(utxo_pool_index); | ||
| curr_value -= utxo.GetSelectionAmount(); | ||
| curr_selection.pop_back(); | ||
| } else { // Moving forwards, continuing down this branch | ||
| OutputGroup& utxo = utxo_pool.at(utxo_pool_index); | ||
|
|
@@ -142,7 +146,6 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo | |
| // Inclusion branch first (Largest First Exploration) | ||
| curr_selection.push_back(utxo_pool_index); | ||
| curr_value += utxo.GetSelectionAmount(); | ||
| } | ||
| } | ||
| } | ||
|
|
@@ -157,7 +160,6 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo | |
| result.AddInput(utxo_pool.at(i)); | ||
| } | ||
| result.ComputeAndSetWaste(cost_of_change, cost_of_change, CAmount{0}); | ||
|
|
||
| return result; | ||
| } | ||
|
|
||
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
By removing this criteria for backtracking you significantly expand the search space that will lead a) to longer execution time b) overall less less solutions found due to hard cap of
TOTAL_TRIES.There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This doesn't change the search space. With this extra condition removed, this code path is used instead. And in the case where
curr_waste > best_wasteusing the code path L98, nothing different happens because of this condition. Sincebest_wasteis better thancurr_waste, nothing happens and in both branches,backtrack=trueis set. Running the benchmarks will show there's no difference.Uh oh!
There was an error while loading. Please reload this page.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
@S3RK The search space is not changed. The code is now simpler, however, the change could be pulled from this PR and added to a new PR since it's independent of other improvements.
Uh oh!
There was an error while loading. Please reload this page.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I agree that without limitation to the number of iterations you'd get the same result with your algorithm. But we actually have a hard limit of
TOTAL_TRIES. That means if there are more combinations of coins thanTOTAL_TRIESwe're not going to explore all of them. This is why we want to exit as early as possible, in particular this condition allows to cut off branches where we didn't reach the target yet but the solution is already worse than our current best.