wallet: cache IsMine scriptPubKeys to improve performance of descriptor wallets #26008

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

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


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

@@ -31,7 +30,6 @@ static void WalletBalance(benchmark::Bench& bench, const bool set_dirty, const b
        LOCK(wallet.cs_wallet);
        wallet.SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
        wallet.SetupDescriptorScriptPubKeyMans();
-        if (wallet.LoadWallet() != DBErrors::LOAD_OK) assert(false);


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

+    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;


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

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 ac246f6

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 josibake February 15, 2024 14:29

achow101 force-pushed the improve-many-desc-ismine branch from b20d882 to ac246f6 Compare February 15, 2024 17:28

achow101 mentioned this pull request Feb 15, 2024

wallet: pre-HD HDD migratewallet #29438

Closed

DrahtBot requested review from ryanofsky and removed request for josibake February 16, 2024 12:49

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

DrahtBot requested a review from ryanofsky February 16, 2024 14:43

achow101 force-pushed the improve-many-desc-ismine branch from ac246f6 to bf898af Compare February 16, 2024 18:21

furszy reviewed Feb 16, 2024

View reviewed changes

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

src/wallet/wallet.h 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.

achow101 force-pushed the improve-many-desc-ismine branch from bf898af to e041ed9 Compare February 16, 2024 19:37

ryanofsky approved these changes Feb 16, 2024

View reviewed changes

DrahtBot requested review from josibake and furszy February 16, 2024 20:25

josibake reviewed Feb 19, 2024

View reviewed changes

furszy reviewed Feb 19, 2024

View reviewed changes

fanquake merged commit b1a46b2 into bitcoin:master Feb 20, 2024

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

Open

1 task

bitcoin locked and limited conversation to collaborators Feb 19, 2025

wallet: cache IsMine scriptPubKeys to improve performance of descriptor wallets #26008

wallet: cache IsMine scriptPubKeys to improve performance of descriptor wallets #26008

Uh oh!

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!

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.

Uh oh!

Uh oh!

ryanofsky left a comment

Choose a reason for hiding this comment

Uh oh!

josibake left a comment

Choose a reason for hiding this comment

Uh oh!

furszy left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

achow101 commented Sep 4, 2022 •

edited

Loading

DrahtBot commented Sep 5, 2022 •

edited

Loading

w0xlt Sep 21, 2022 •

edited

Loading

ryanofsky left a comment •

edited

Loading

furszy commented Feb 16, 2024 •

edited

Loading