refactor: improve complexity of removing preselected coins #24814

rag-hav · 2022-04-09T13:48:54Z

Improve the complexity of removing pre-selected coins from the pool to linear from quadratic.

jonatack

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).

jonatack · 2022-04-09T14:55:08Z

src/wallet/spend.cpp

+            if (!preset_coins.count(it->outpoint))
+                vCoins_filtered.push_back(*it);
+        }
+        swap(vCoins_filtered, vCoins);


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.

made these changes

Eunoia1729

Concept ACK

mzumsande

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

jonatack · 2022-04-09T22:29:31Z

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 · 2022-04-10T03:22:51Z

Concept ACK

rag-hav · 2022-04-10T18:10:24Z

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

#24821

DrahtBot · 2022-04-11T01:42:17Z

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 · 2022-04-12T17:08:15Z

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

jonatack · 2022-04-12T17:31:12Z

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 · 2022-04-13T02:09:02Z

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 · 2022-04-13T06:22:52Z

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 · 2022-04-13T11:48:00Z

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 · 2022-04-13T22:31:32Z

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.

achow101 · 2022-04-14T15:47:30Z

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 · 2022-06-08T19:21:57Z

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 · 2022-07-28T23:01:29Z

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

_{Want to unsubscribe from rebase notifications on this pull request? Just convert this pull request to a "draft".}

mzumsande · 2022-07-29T13:52:43Z

Looks like this can be closed, #24584 changed this spot to use the remove-erase idiom.

furszy · 2022-07-29T14:22:52Z

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.

rag-hav changed the title ~~improve complexity of removing preselected coins~~ refactor: improve complexity of removing preselected coins Apr 9, 2022

jonatack reviewed Apr 9, 2022

View reviewed changes

DrahtBot added Refactoring Wallet labels Apr 9, 2022

Eunoia1729 reviewed Apr 9, 2022

View reviewed changes

mzumsande reviewed Apr 9, 2022

View reviewed changes

improve complexity of removing preselected coins

236011b

bitcoin deleted a comment from joshuadbryant1985 Apr 10, 2022

rag-hav force-pushed the remove-preselect branch from 986b355 to 236011b Compare April 10, 2022 11:41

rag-hav mentioned this pull request Apr 10, 2022

refactor: remove preset coins in linear time with remove-erase idiom #24821

Closed

rag-hav requested a review from jonatack April 11, 2022 09:19

bitcoin deleted a comment from joshuadbryant1985 Apr 14, 2022

DrahtBot mentioned this pull request Apr 24, 2022

wallet: avoid mixing different OutputTypes during coin selection #24584

Merged

This was referenced Jul 18, 2022

rpc: Filter inputs by type during CoinSelection #25183

Closed

wallet: Faster transaction creation by removing pre-set-inputs fetching responsibility from Coin Selection #25685

Merged

DrahtBot mentioned this pull request Jul 28, 2022

wallet: Check max transaction weight in CoinSelection #25729

Merged

DrahtBot added the Needs rebase label Jul 28, 2022

maflcko closed this Jul 29, 2022

bitcoin locked and limited conversation to collaborators Jul 29, 2023

refactor: improve complexity of removing preselected coins #24814

refactor: improve complexity of removing preselected coins #24814

Uh oh!

Conversation

rag-hav commented Apr 9, 2022

Uh oh!

jonatack left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jonatack Apr 9, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

rag-hav Apr 10, 2022

Choose a reason for hiding this comment

Uh oh!

Eunoia1729 left a comment

Choose a reason for hiding this comment

Uh oh!

mzumsande left a comment

Choose a reason for hiding this comment

Uh oh!

jonatack commented Apr 9, 2022

Uh oh!

theStack commented Apr 10, 2022

Uh oh!

rag-hav commented Apr 10, 2022

Uh oh!

DrahtBot commented Apr 11, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

rag-hav commented Apr 12, 2022

Uh oh!

jonatack commented Apr 12, 2022

Uh oh!

luke-jr commented Apr 13, 2022

Uh oh!

rag-hav commented Apr 13, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mzumsande commented Apr 13, 2022

Uh oh!

Eunoia1729 commented Apr 13, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

achow101 commented Apr 14, 2022

Uh oh!

anibilthare commented Jun 8, 2022

Uh oh!

DrahtBot commented Jul 28, 2022

Uh oh!

mzumsande commented Jul 29, 2022

Uh oh!

furszy commented Jul 29, 2022

Uh oh!

Uh oh!

jonatack left a comment •

edited

Loading

jonatack Apr 9, 2022 •

edited

Loading

DrahtBot commented Apr 11, 2022 •

edited

Loading

rag-hav commented Apr 13, 2022 •

edited

Loading

Eunoia1729 commented Apr 13, 2022 •

edited

Loading