refactor: improve complexity of removing preselected coins #24814

pull rag-hav wants to merge 1 commits into bitcoin:master from rag-hav:remove-preselect changing 1 files +7 −6

rag-hav commented at 1:48 PM on April 9, 2022: none

Improve the complexity of removing pre-selected coins from the pool to linear from quadratic.
rag-hav renamed this:
~~improve complexity of removing preselected coins~~
refactor: improve complexity of removing preselected coins
on Apr 9, 2022

in src/wallet/spend.cpp:500 in 986b355655 outdated

 501 | +        for (std::vector<COutput>::iterator it = vCoins.begin(); it != vCoins.end(); it++)
 502 | +        {
 503 | +            if (!preset_coins.count(it->outpoint))
 504 | +                vCoins_filtered.push_back(*it);
 505 | +        }
 506 | +        swap(vCoins_filtered, vCoins);

jonatack commented at 2:55 PM on April 9, 2022:

suggested diff per clang-format and guidelines in doc/developer-notes.md

-    if(coin_control.HasSelected()){
+    if (coin_control.HasSelected()) {
         std::vector<COutput> vCoins_filtered;
-        for (std::vector<COutput>::iterator it = vCoins.begin(); it != vCoins.end(); it++)
-        {
-            if (!preset_coins.count(it->outpoint))
+        for (std::vector<COutput>::iterator it = vCoins.begin(); it != vCoins.end(); ++it) {
+            if (!preset_coins.count(it->outpoint)) {
                 vCoins_filtered.push_back(*it);
+            }

edit: unsure if std::swap(vCoins_filtered, vCoins) or vCoins_filtered.swap(vCoins) would be preferred to swap(vCoins_filtered, vCoins) here.

rag-hav commented at 4:43 PM on April 10, 2022:

made these changes

jonatack commented at 3:04 PM on April 9, 2022: contributor

Concept ACK on replacing O(n) erase with O(1) operations push_back and swap, provided the difference is meaningful (a benchmark comparison might be helpful).
DrahtBot added the label Refactoring on Apr 9, 2022
DrahtBot added the label Wallet on Apr 9, 2022
Eunoia1729 commented at 7:28 PM on April 9, 2022: contributor

Concept ACK
mzumsande commented at 9:43 PM on April 9, 2022: contributor

Could this be solved easier with the erase-remove idiom so you don't need to swap with a second vector?
jonatack commented at 10:29 PM on April 9, 2022: contributor

Or we could wait until C++20 to use constant-time erase_if https://en.cppreference.com/w/cpp/container/vector/erase2, as the currently available https://en.cppreference.com/w/cpp/algorithm/remove has complexity of std::distance(first, last) applications of the predicate.
theStack commented at 3:22 AM on April 10, 2022: contributor

Concept ACK
improve complexity of removing preselected coins 236011bec1
bitcoin deleted a comment on Apr 10, 2022
rag-hav force-pushed on Apr 10, 2022
rag-hav commented at 6:10 PM on April 10, 2022: none

Could this be solved easier with the erase-remove idiom so you don't need to swap with a second vector?

#24821
DrahtBot commented at 1:42 AM on April 11, 2022: contributor


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



Conflicts

Reviewers, this pull request conflicts with the following ones:
- #25729 (wallet: Check max transaction weight in CoinSelection by aureleoules)
- #25685 (wallet: Faster transaction creation by removing pre-set-inputs fetching responsibility from Coin Selection by furszy)
- #25183 (rpc: Segwit-only inputs option for fundrawtransaction by aureleoules)
- #24584 (wallet: avoid mixing different OutputTypes during coin selection by josibake)
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.
rag-hav requested review from jonatack on Apr 11, 2022
rag-hav commented at 5:08 PM on April 12, 2022: none

I am not sure what I am supposed to do right now. Do I wait for more reviewers?
jonatack commented at 5:31 PM on April 12, 2022: contributor

I am not sure what I am supposed to do right now. Do I wait for more reviewers?

Haven't gotten back yet as there are many PRs to review; my suggestions would be the last entry of this section https://github.com/bitcoin/bitcoin/blob/master/CONTRIBUTING.md#finding-reviewers and https://jonatack.github.io/articles/how-to-review-pull-requests-in-bitcoin-core.
luke-jr commented at 2:09 AM on April 13, 2022: member

I am not sure what I am supposed to do right now.

If you wanted to use the remove-erase idiom, you should push that over this PR's branch.
rag-hav commented at 6:22 AM on April 13, 2022: none

If you wanted to use the remove-erase idiom, you should push that over this PR's branch.

I am not sure if the remove-erase idiom is better, it saves memory but is harder to read as well. I prefer the current push_back and swap approach.
mzumsande commented at 11:48 AM on April 13, 2022: contributor
I am not sure if the remove-erase idiom is better, it saves memory but is harder to read as well. I prefer the current push_back and swap approach.

Just FYI, I think it could be quite short like
```
if(coin_control.HasSelected()){
    auto in_preset = [&preset_coins](COutput& x) { return preset_coins.count(x.outpoint); };
    vCoins.erase(std::remove_if(vCoins.begin(), vCoins.end(), in_preset), vCoins.end());
}
```
(didn't test this though) I guess whether that is easier to read depends on whether one is accustomed to the remove-erase idiom / lambdas or not.
Eunoia1729 commented at 10:31 PM on April 13, 2022: contributor

I am not sure if the remove-erase idiom is better, it saves memory but is harder to read as well. I prefer the current push_back and swap approach.

As @jonatack suggested, another option is to wait until C++20. It does both: saves memory and is easier to read.
bitcoin deleted a comment on Apr 14, 2022
achow101 commented at 3:47 PM on April 14, 2022: member

I would also prefer the erase-remove idiom as I think it's clearer as to what is actually happening (although perhaps having both erase and remove is a little bit confusing, but they're both clear that something is being deleted).
anibilthare commented at 7:21 PM on June 8, 2022: none
I am not sure if the remove-erase idiom is better, it saves memory but is harder to read as well. I prefer the current push_back and swap approach.

Just FYI, I think it could be quite short like

if(coin_control.HasSelected()){ auto in_preset = [&preset_coins](COutput& x) { return preset_coins.count(x.outpoint); }; vCoins.erase(std::remove_if(vCoins.begin(), vCoins.end(), in_preset), vCoins.end()); }

(didn't test this though) I guess whether that is easier to read depends on whether one is accustomed to the remove-erase idiom / lambdas or not.
The logic makes sense and all the tests are running fine in my system on applying your suggested code changes.

For people not accustomed with remove-erase idiom: Check this lambdas: this and this
DrahtBot added the label Needs rebase on Jul 28, 2022
DrahtBot commented at 11:01 PM on July 28, 2022: contributor



🐙 This pull request conflicts with the target branch and needs rebase.

<sub>Want to unsubscribe from rebase notifications on this pull request? Just convert this pull request to a "draft".</sub>
mzumsande commented at 1:52 PM on July 29, 2022: contributor

Looks like this can be closed, #24584 changed this spot to use the remove-erase idiom.
MarcoFalke closed this on Jul 29, 2022
furszy commented at 2:22 PM on July 29, 2022: member

Worth to mention that #25685 completely removes the need to erase the pre-selected coins from the available coins vector by not including them there in the first place.
bitcoin locked this on Jul 29, 2023