wallet: cache IsMine scriptPubKeys to improve performance of descriptor wallets by achow101 · Pull Request #26008 · bitcoin/bitcoin

achow101 · 2022-09-04T23:03:15Z

Wallets that have a ton of non-ranged descriptors (such as a migrated non-HD wallet) perform fairly poorly due to looping through all of the wallet's ScriptPubKeyMans. This is done in various places, such as IsMine, and helper functions for fetching a ScriptPubKeyMan and a SolvingProvider. This also has a bit of a performance impact on standard descriptor wallets, although less noticeable due to the small number of SPKMs.

As these functions are based on doing IsMine for each ScriptPubKeyMan, we can improve this performance by caching IsMine scriptPubKeys for all descriptors and use that to determine which ScriptPubKeyMan to actually use for those things. This cache is used exclusively and we no longer iterate the SPKMs.

Also added a benchmark for IsMine.

achow101 · 2022-09-05T04:35:25Z

Dropped the signing changes as they were causing issues with being able to sign transactions that we have the keys for but not the descriptors. #23417 would allow us to resolve the performance issues for signing while retaining this behavior.

DrahtBot · 2022-09-05T06:27:31Z

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	ryanofsky, josibake, furszy
Concept ACK	aureleoules, darosior, willcl-ark

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#29136 (wallet: addhdkey RPC to add just keys to wallets via new void(KEY) descriptor by achow101)
#29130 (wallet: Add createwalletdescriptor and gethdkeys RPCs for adding new automatically generated descriptors by achow101)
#28574 (wallet: optimize migration process, batch db transactions by furszy)
#28333 (wallet: Construct ScriptPubKeyMans with all data rather than loaded progressively by achow101)
#28201 (Silent Payments: sending by josibake)
#27865 (wallet: Track no-longer-spendable TXOs separately by achow101)
#27286 (wallet: Keep track of the wallet's own transaction outputs in memory by achow101)

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.

w0xlt · 2022-09-21T14:21:12Z

src/wallet/wallet.cpp

Suggested change

m_uncached_spkms.insert(spkm);

if (!ranged) {

for (const auto& script : spkm->GetScriptPubKeys()) {

m_cached_spks[script].insert(spkm);

m_uncached_spkms.erase(spkm);

}

}

if (!ranged) {

for (const auto& script : spkm->GetScriptPubKeys()) {

m_cached_spks[script].insert(spkm);

}

}

else {

m_uncached_spkms.insert(spkm);

}

I prefer the way it was written as it ensures that no spkm will be accidentally missed.

w0xlt · 2022-09-21T14:28:20Z

src/bench/wallet_balance.cpp

What would be the reason to remove this validation ?

It is incorrect, unneeded, and caused a segfault.

It is incorrect because LoadWallet is supposed to be called before SetupDescriptorScriptPubKeyMans. Doing it after will break things that SetupDescriptorScriptPubKeyMans sets, which also caused a segfault. It is also entirely unneeded as loading an empty wallet doesn't do anything, and SetupDescriptorScriptPubKeyMans is doing all of the setup needed.

w0xlt · 2022-09-21T18:00:04Z

src/wallet/wallet.h

I think the names below work better and make the purpose of the variable clearer.

Suggested change

std::unordered_map<CScript, std::unordered_set<ScriptPubKeyMan*>, SaltedSipHasher> m_cached_spks;

//! Set of which descriptors are not in m_cached_spks

std::unordered_set<ScriptPubKeyMan*> m_uncached_spkms;

std::unordered_map<CScript, std::unordered_set<ScriptPubKeyMan*>, SaltedSipHasher> m_ranged_spks;

//! Set of which descriptors are not in m_cached_spks

std::unordered_set<ScriptPubKeyMan*> m_non_ranged_spkms;

I prefer describing the variable with how we expect to use it, rather than what it contains. We're using it as a cache of spkms, the type of spkm doesn't matter.

w0xlt

This change looks good, but adds complexity by adding two caches instead of accessing m_spk_managers directly.

Perhaps the PR description might include benchmark improvement as a reason for the added complexity.

aureleoules

Concept ACK

src/bench/wallet_ismine.cpp

josibake · 2024-02-12T19:04:42Z

reACK a966473

furszy

Left two more comments. They aren't really blocking but I'm still struggling with the memory consumption topic. Isn't std::unordered_map going to store all keys (entire scripts) in memory for duplicated so it can solve hash collisions?

Apart from that, just as an extra note for the future: It seems that we will need to rearrange code so that these functions aren't called so many times within the same process.

src/wallet/wallet.cpp

maflcko · 2024-02-14T10:24:44Z

Tested time loadwallet with my normal regtest wallet (#28510 (comment)), didn't review or check for correctness.

Before:

real	0m35.182s

After:

real	0m3.622s

achow101 · 2024-02-15T01:27:34Z

They aren't really blocking but I'm still struggling with the memory consumption topic. Isn't std::unordered_map going to store all keys (entire scripts) in memory for duplicated so it can solve hash collisions?

Yes.

I've done some memory usage profiling with a large wallet, and various combinations of ordered and unordered maps and sets.

The baseline memory usage of m_map_script_pub_keys, which is the same for all of the following, is 1.2 MiB

std::unordered_map<CScript, std::unorderd_set<ScriptPubKeyMan*>, SaltedSipHasher> m_cached_spks: 3.4 MiB
std::unordered_map<CScript, std::set<ScriptPubKeyMan*>, SaltedSipHasher> m_cached_spks: 2.6 MiB
std::unordered_map<CScript, std::vector<ScriptPubKeyMan*>, SaltedSipHasher> m_cached_spks: 1.2 MiB
std::map<CScript, std::unorderd_set<ScriptPubKeyMan*>, SaltedSipHasher> m_cached_spks: 3.7 MiB
std::map<CScript, std::set<ScriptPubKeyMan*>, SaltedSipHasher> m_cached_spks: 2.9 MiB
std::map<CScript, std::vector<ScriptPubKeyMan*>, SaltedSipHasher> m_cached_spks: 1.5 MiB

The benchmark indicates that there isn't really a meaningful difference between all of these approaches. It seems that not using unordered_* may be slightly faster as hashing is not needed.

In the latest push, I've changed to using std::unordered_map<CScript, std::vector<ScriptPubKeyMan*>, SaltedSipHasher> m_cached_spks so the memory consumption should be about double the size of all scriptPubKeys.

DrahtBot · 2024-02-15T01:54:37Z

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the
documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

_{Debug: https://github.com/bitcoin/bitcoin/runs/21591404299}

maflcko · 2024-02-15T11:11:22Z

I re-checked b20d882fd53c21098eb7858b2dbca84eafd2b344 and re-confirmed time loadwallet (#26008 (comment))

ryanofsky

Code review ACK b20d882fd53c21098eb7858b2dbca84eafd2b344. I don't have much insight into performance impact of this change, but it seems like it should make migrated legacy wallets much faster (10 times faster loading in one case: #26008 (comment)) even if it does increase memory usage, and it seems to be implemented correctly.

re: #26008 (review)

Apart from that, just as an extra note for the future: It seems that we will need to rearrange code so that these functions aren't called so many times within the same process.

I'm not sure what this is referring to, so would be curious

src/wallet/external_signer_scriptpubkeyman.h

src/wallet/wallet.cpp

achow101 · 2024-02-15T17:30:32Z

I've also added one more commit that speeds up loading and migration as I noticed one spot where m_spk_managers was being iterated again during loading.

josibake · 2024-02-16T12:49:32Z

ACK ac246f6

ryanofsky

Code review ac246f68299d0dc208ae513dfad1a8fc91b5e6d4

Looks good, but wondering about a possible bug in the GetScriptPubKeyMans legacy case (see below)

src/wallet/wallet.cpp

furszy

Reviewed. Need to update the second commit description.

src/bench/wallet_ismine.cpp

src/wallet/wallet.h

After TopUp completes, the wallet containing each SPKM will want to know what new scriptPubKeys were generated. In order for all TopUp calls (including ones internal the the SPKM), we use a callback function in the WalletStorage interface.

Have CWallet maintain a cache of all known scriptPubKeys for its DescriptorSPKMs in order to improve performance of the functions that require searching for scriptPubKeys.

Instead of iterating m_spk_managers a DescriptorSPKM has been loaded in order to get it's ID to compare, have LoadDescriptorSPKM return a reference to the loaded DescriptorSPKM so it can be queried directly.

achow101 · 2024-02-16T19:36:52Z

Need to update the second commit description.

Done

furszy · 2024-02-16T19:41:53Z

Apart from that, just as an extra note for the future: It seems that we will need to rearrange code so that these functions aren't called so many times within the same process.

I'm not sure what this is referring to, so would be curious

@ryanofsky.
An easy example is CWallet::AvailableCoins, which calls CWallet::IsMine first, few lines later calls CWallet::GetSolvingProvider and then calls CWallet::CalculateMaximumSignedInputSize which internally calls CWallet::GetSolvingProvider again. So, only this function, traverses the spkm map at least 3 times per output.

ryanofsky

Code review ACK e041ed9. Just suggested changes since last review

josibake

ACK e041ed9

Reviewed diff, looks good!

furszy

Code review ACK e041ed9

It isn't blocking, but I have to admit that I'm still not really happy with the doubled script storage. I think we can do better. Will be experimenting with possible solutions.
A first measure to decrease it and remain fast, without changing the structure, could be to use the cache only for the inactive SPKMs. Since the active ones are limited in number (max 8), they can be checked quickly. However, this approach does not address the issue of handling really large scripts, which could probably be resolved by changing the structure for a probabilistic one.

achow101 marked this pull request as ready for review September 4, 2022 23:03

achow101 force-pushed the improve-many-desc-ismine branch from 4aa65c3 to 23dffde Compare September 4, 2022 23:10

DrahtBot added the Wallet label Sep 5, 2022

achow101 force-pushed the improve-many-desc-ismine branch from 23dffde to 34590dd Compare September 5, 2022 04:32

achow101 force-pushed the improve-many-desc-ismine branch from 34590dd to d4cdc2c Compare September 6, 2022 20:31

DrahtBot mentioned this pull request Sep 15, 2022

build: remove duplicate / unneeded libs from bench_bitcoin #26099

Merged

achow101 force-pushed the improve-many-desc-ismine branch 2 times, most recently from 8945d10 to 020f5b8 Compare September 20, 2022 20:17

DrahtBot added the Needs rebase label Sep 21, 2022

w0xlt reviewed Sep 21, 2022

View reviewed changes

achow101 force-pushed the improve-many-desc-ismine branch from 020f5b8 to f9f467b Compare September 21, 2022 15:11

DrahtBot removed the Needs rebase label Sep 21, 2022

w0xlt reviewed Sep 21, 2022

View reviewed changes

DrahtBot mentioned this pull request Oct 6, 2022

rpc, wallet: addhdseed, infer seed when importing descriptor with xpub #23544

Closed

DrahtBot added the Needs rebase label Oct 27, 2022

achow101 force-pushed the improve-many-desc-ismine branch from f9f467b to fd1b75e Compare November 4, 2022 20:18

DrahtBot removed the Needs rebase label Nov 4, 2022

DrahtBot mentioned this pull request Nov 29, 2022

wallet: Migrate legacy wallets to descriptor wallets without requiring BDB #26596

Merged

aureleoules reviewed Dec 1, 2022

View reviewed changes

src/bench/wallet_ismine.cpp Outdated Show resolved Hide resolved

achow101 force-pushed the improve-many-desc-ismine branch from fd1b75e to 9b248d1 Compare December 2, 2022 19:24

DrahtBot requested a review from furszy February 12, 2024 19:04

furszy reviewed Feb 12, 2024

View reviewed changes

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

DrahtBot requested a review from furszy February 12, 2024 19:44

achow101 force-pushed the improve-many-desc-ismine branch from a966473 to e7c141b Compare February 15, 2024 01:26

achow101 force-pushed the improve-many-desc-ismine branch from e7c141b to b20d882 Compare February 15, 2024 01:54

ryanofsky approved these changes Feb 15, 2024

View reviewed changes

src/wallet/external_signer_scriptpubkeyman.h Outdated Show resolved Hide resolved

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

achow101 mentioned this pull request Feb 15, 2024

wallet: pre-HD HDD migratewallet #29438

Closed

ryanofsky reviewed Feb 16, 2024

View reviewed changes

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

src/wallet/wallet.cpp Outdated Show resolved Hide resolved

furszy reviewed Feb 16, 2024

View reviewed changes

src/bench/wallet_ismine.cpp Outdated Show resolved Hide resolved

src/wallet/wallet.h Outdated Show resolved Hide resolved

achow101 added 7 commits February 16, 2024 14:35

bench: Add a benchmark for ismine

b276825

wallet: Cache scriptPubKeys for all DescriptorSPKMs

3723233

Have CWallet maintain a cache of all known scriptPubKeys for its DescriptorSPKMs in order to improve performance of the functions that require searching for scriptPubKeys.

wallet: Use scriptPubKey cache in IsMine

edf4e73

wallet: Use scriptPubKey cache in GetScriptPubKeyMans

b410f68

wallet: Use scriptPubKeyCache in GetSolvingProvider

39640dd

wallet: Retrieve ID from loaded DescSPKM directly

e041ed9

Instead of iterating m_spk_managers a DescriptorSPKM has been loaded in order to get it's ID to compare, have LoadDescriptorSPKM return a reference to the loaded DescriptorSPKM so it can be queried directly.

ryanofsky approved these changes Feb 16, 2024

View reviewed changes

josibake reviewed Feb 19, 2024

View reviewed changes

furszy reviewed Feb 19, 2024

View reviewed changes

hebasto mentioned this pull request Mar 1, 2024

cmake: Regular rebasing of the cmake-staging branch hebasto/bitcoin#107

Closed

VojtechMyslivec mentioned this pull request Jul 9, 2024

Send RPC calls performance #30416

Closed

1 task

-    m_uncached_spkms.insert(spkm);
-    if (!ranged) {
-        for (const auto& script : spkm->GetScriptPubKeys()) {
-            m_cached_spks[script].insert(spkm);
-            m_uncached_spkms.erase(spkm);
-        }
-    }
+    if (!ranged) {
+        for (const auto& script : spkm->GetScriptPubKeys()) {
+            m_cached_spks[script].insert(spkm);
+        }
+    }
+    else {
+        m_uncached_spkms.insert(spkm);
+    }

-    std::unordered_map<CScript, std::unordered_set<ScriptPubKeyMan*>, SaltedSipHasher> m_cached_spks;
-    //! Set of which descriptors are not in m_cached_spks
-    std::unordered_set<ScriptPubKeyMan*> m_uncached_spkms;
+    std::unordered_map<CScript, std::unordered_set<ScriptPubKeyMan*>, SaltedSipHasher> m_ranged_spks;
+    //! Set of which descriptors are not in m_cached_spks
+    std::unordered_set<ScriptPubKeyMan*> m_non_ranged_spkms;

Conversation

achow101 commented Sep 4, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

achow101 commented Sep 5, 2022

Uh oh!

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

Uh oh!

Code Coverage

Reviews

Conflicts

Uh oh!

w0xlt Sep 21, 2022

Choose a reason for hiding this comment

Uh oh!

achow101 Sep 21, 2022

Choose a reason for hiding this comment

Uh oh!

w0xlt Sep 21, 2022

Choose a reason for hiding this comment

Uh oh!

achow101 Sep 21, 2022

Choose a reason for hiding this comment

Uh oh!

w0xlt Sep 21, 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!

achow101 Jan 23, 2023

Choose a reason for hiding this comment

Uh oh!

w0xlt left a comment

Choose a reason for hiding this comment

Uh oh!

aureleoules left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

josibake commented Feb 12, 2024

Uh oh!

furszy left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

maflcko commented Feb 14, 2024

Uh oh!

achow101 commented Feb 15, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Feb 15, 2024

Uh oh!

maflcko commented Feb 15, 2024

Uh oh!

ryanofsky 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!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

achow101 commented Feb 15, 2024

Uh oh!

josibake commented Feb 16, 2024

Uh oh!

ryanofsky 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!

Uh oh!

Uh oh!

furszy left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

achow101 commented Feb 16, 2024

Uh oh!

furszy commented Feb 16, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

achow101 commented Sep 4, 2022 •

edited

Loading

DrahtBot commented Sep 5, 2022 •

edited

Loading

w0xlt Sep 21, 2022 •

edited

Loading

achow101 commented Feb 15, 2024 •

edited

Loading

ryanofsky left a comment •

edited

Loading

ryanofsky left a comment •

edited

Loading

furszy commented Feb 16, 2024 •

edited

Loading