wallet: reduce loading time by using unordered maps #16910

achow101 · 2019-09-18T21:16:12Z

For large wallets with many transactions and keys, inserting and fetching from a std::map can have a performance impact. Since we largely do not rely on the sorting properties of std::map, we can use std::unordered_map instead which is a hash table and insertion and retrieval are constant time. We also use std::unordered_multimap for some things that were std::multimap.

The changed maps are:

mapWallet: Map of all transactions
mapTxSpends: Map of outpoints to the txids of the txs that spent them
*mapKeyMetadata: Map of key metadata
*mapScriptMetadata: Map of script metadata
*mapKeys: Map of private keys
*mapCryptedKeys: Map of encrypted private keys
*mapWatchKeys: Set of watch only keys.
*setWatchOnly: Set of watch only scripts (std::unordered_set, not a map)

Change mapWallet and mapTxSpends did require a few other changes and thus they are in their own commits. Additionally, the GUI relied on getting transactions from the wallet in a sorted order which unordered_map does not provide, so the commit "Change getWalletTxs to return a set instead of a vector" is needed in order to put all of the txs into a std::set (which is ordered) instead of a vector in order to retain the same behavior.

mapTxSpends also relied on the sorted order to have some quick lookups, but these were changed to just do normal lookups over the same thing. It should be just as fast, or even faster, since std::unordered_map is a hash table.

The hash function used for these unordered maps and sets is SipHash, using the SipHash module that we already have. SaltedTxidHasher and SaltedOutPointHasher were moved from their original locations in utxo set and validation code in order to also be used from the wallet. Additionally SaltedIDHasher was added to hash uint160s (i.e. CKeyID and CScriptID) and SaltedScriptHasher was added to hash CScripts.

I did some becnhmarks with a large wallet I created on regtest using this script. This wallet is 169 MB in size with 117035 transactions and 103264 keys. It took ~20 secs to load on master, and ~18 secs with this change. So this change reduces wallet loading time by ~10%.

achow101 · 2019-09-18T21:36:55Z

Shuffled some things around to get rid of the circular dependency. Also fixed a typo

promag · 2019-09-18T21:47:55Z

Concept ACK, especially improvements targeting big wallets (either lots of keys or lots of transactions).

jonatack

Concept ACK, will review and run valgrind+massif visualizer and flamegraphs to compare. Anywhere we can get a big wallet file? EDIT: Saw the script you posted in the PR body above... running.

achow101 · 2019-09-18T22:09:12Z

To benchmark this, I applied this commit: achow101@16ebe13. It adds logging of the load time and also stops bitcoind after the wallet has been loaded in order to get more consistent results.

Here are a couple graphs that may be interesting to people.

Flame graph (svg hosted on my website, couldn't inline in this comment) of master: https://achow101.com/bitcoin-master-flame.svg

Flame graph of this PR: https://achow101.com/bitcoin-reduce-wallet-load-flame.svg

Massif (heap profiler) memory usage over time on master:

Massif memory usage over time on this PR:

ryanofsky · 2019-09-18T23:27:34Z

src/wallet/wallet.cpp

@@ -749,7 +749,7 @@ std::set<uint256> CWallet::GetConflicts(const uint256& txid) const
 bool CWallet::HasWalletSpend(const uint256& txid) const
 {
    AssertLockHeld(cs_wallet);
-    auto iter = mapTxSpends.lower_bound(COutPoint(txid, 0));
+    auto iter = mapTxSpends.find(COutPoint(txid, 0));


Looks like a bug here. Previously it would return true if any output was spent, now it will only return true if the first output was spent. Could fix pretty easily by passing const CTransaction& instead of txid, and looping over the outputs.

Looks like a bug here. Previously it would return true if any output was spent, now it will only return true if the first output was spent. Could fix pretty easily by passing const CTransaction& instead of txid, and looping over the outputs.

A suggestion for a followup: it could be useful to add a test for it to prevent regressions in the future.

DrahtBot · 2019-09-19T00:55:41Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

wallet: Remove -zapwallettxes #19671 (wallet: Remove -zapwallettxes by achow101)
wallet: Replace -zapwallettxes with zapwallettxes RPC #19653 (wallet: Replace -zapwallettxes with zapwallettxes RPC by achow101)
wallet: GetWalletTx and IsMine require cs_wallet lock #19289 (wallet: GetWalletTx and IsMine require cs_wallet lock by promag)

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.

achow101 · 2019-09-19T22:11:20Z

I did 1000 runs of my wallet loading benchmark. The mean loading time on master was 18408.14423 ms and the mean loading time on with this PR was 17498.71984. This is ~1 second faster, which is a ~5% performance increase with this PR. I also did a 2 sample t-test to check that these results are statistically significant, and it appears that they are.

hebasto · 2020-06-27T14:33:39Z

Concept ACK on using hashed containers.

hebasto

Why not using auto for iterators type? It could improve readability a bit :)

hebasto

05afffb changes look correct.

In commit 05afffb message s/mapScriptMetadata/m_script_metadata/

src/saltedhash.h

hebasto · 2020-06-27T14:57:58Z

src/saltedhash.h

+     * This *must* return size_t. With Boost 1.46 on 32-bit systems the
+     * unordered_map will behave unpredictably if the custom hasher returns a
+     * uint64_t, resulting in failures when syncing the chain (#4634).


42bc524

This comment could be dropped as all available reference docs refer to the size_t return type for a hasher operator().

Since this is just moved code, I'm going to leave as is.

achow101 · 2020-06-29T18:15:39Z

Why not using auto for iterators type? It could improve readability a bit :)

Done

src/wallet/wallet.h

src/script/signingprovider.h

src/wallet/scriptpubkeyman.h

achow101 · 2020-06-29T19:04:25Z

Had to rebase onto master to pick up the uint160 changes to CKeyID and CScriptID

hebasto

ACK 4b3439f, tested on Linux Mint 20 (x86_64).

Did not make benchmarks, though.

e89c19a
Why are operator() definitions not placed in the header, that could imply inlining?

src/primitives/transaction.h

src/saltedhash.cpp

achow101 · 2020-07-02T14:56:29Z

Why are operator() definitions not placed in the header, that could imply inlining?

I'm not sure that it matters since we never call operator() directly ourselves.

SaltedKeyIDHasher uses CSipHasher for hashing CKeyIDs SaltedScriptIDHasher uses CSipHasher for hashing CScriptIDs SaltedPubkeyasher uses CSipHasher for hashing CPubKeys SaltedScriptHasher uses CSipHasher for hashing CScripts

…e wallet Change mapKeys, mapScripts, mapCryptedKeys, mapKeyMetadata, m_script_metadata, mapWatchKeys to use std::unordered_map. Change setWatchOnly to use std::unordered_set

hebasto

re-ACK 8e3d1e7, only suggested changes since the previous review.

achow101 · 2020-08-10T16:00:01Z

This has been open for a while without much review. Closing for now, I'll try to integrate some of these changes the next time I touch the relevant places (e.g. mapWallet when I get around to changing how transactions are stored).

DrahtBot added Mempool Tests UTXO Db and Indexes Wallet labels Sep 18, 2019

achow101 force-pushed the reduce-wallet-load branch from e963dd5 to 4ed9dd6 Compare September 18, 2019 21:36

jonatack reviewed Sep 18, 2019

View reviewed changes

ryanofsky reviewed Sep 18, 2019

View reviewed changes

achow101 force-pushed the reduce-wallet-load branch 4 times, most recently from f97e249 to 45a3ec5 Compare September 19, 2019 00:38

fanquake removed the Tests label Sep 19, 2019

achow101 mentioned this pull request Sep 19, 2019

wallet: Only check the hash of transactions loaded from disk #16911

Merged

achow101 force-pushed the reduce-wallet-load branch from 45a3ec5 to 73bb122 Compare September 19, 2019 22:45

DrahtBot added the Needs rebase label Sep 30, 2019

achow101 force-pushed the reduce-wallet-load branch from 73bb122 to de0f388 Compare September 30, 2019 19:52

DrahtBot removed the Needs rebase label Sep 30, 2019

laanwj added the Resource usage label Oct 2, 2019

jonatack mentioned this pull request Oct 10, 2019

Future PRs bitcoin-core-review-club/website#14

Closed

DrahtBot added the Needs rebase label Oct 15, 2019

achow101 force-pushed the reduce-wallet-load branch 2 times, most recently from 3324a42 to c26b49f Compare October 21, 2019 16:09

DrahtBot removed the Needs rebase label Oct 21, 2019

DrahtBot added the Needs rebase label Oct 29, 2019

achow101 force-pushed the reduce-wallet-load branch from c26b49f to fe0b951 Compare October 29, 2019 17:59

achow101 force-pushed the reduce-wallet-load branch from f5428d4 to 05afffb Compare May 12, 2020 17:56

DrahtBot removed the Needs rebase label May 12, 2020

This was referenced Jun 15, 2020

wallet, refactor: Remove duplicate/unnecessary lookups #19279

Closed

wallet: GetWalletTx and IsMine require cs_wallet lock #19289

Merged

hebasto reviewed Jun 27, 2020

View reviewed changes

achow101 force-pushed the reduce-wallet-load branch from 05afffb to f9304b6 Compare June 29, 2020 18:14

hebasto reviewed Jun 29, 2020

View reviewed changes

src/wallet/wallet.h Show resolved Hide resolved

hebasto reviewed Jun 29, 2020

View reviewed changes

src/script/signingprovider.h Show resolved Hide resolved

hebasto reviewed Jun 29, 2020

View reviewed changes

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

achow101 force-pushed the reduce-wallet-load branch from f9304b6 to 4b3439f Compare June 29, 2020 19:03

hebasto mentioned this pull request Jun 30, 2020

refactor: Drop g_orphan_list global #19374

Closed

hebasto approved these changes Jul 2, 2020

View reviewed changes

src/primitives/transaction.h Outdated Show resolved Hide resolved

src/saltedhash.cpp Show resolved Hide resolved

achow101 added 6 commits July 2, 2020 10:58

Move SaltedTxidHasher and SaltedOutPointHasher to saltedhash.{cpp/h}

76bd5b0

Change getWalletTxs to return a set instead of a vector

23eb02c

Change mapWallet to be a std::unordered_map

864bc3b

Change mapTxSpends to be a std::unordered_multimap

dec73a3

Add SaltedHashers for CKeyID, CScriptID, CPubKey, and CScript

11d172c

SaltedKeyIDHasher uses CSipHasher for hashing CKeyIDs SaltedScriptIDHasher uses CSipHasher for hashing CScriptIDs SaltedPubkeyasher uses CSipHasher for hashing CPubKeys SaltedScriptHasher uses CSipHasher for hashing CScripts

Use std::unordered_map and std::unordered_set in various places in th…

8e3d1e7

…e wallet Change mapKeys, mapScripts, mapCryptedKeys, mapKeyMetadata, m_script_metadata, mapWatchKeys to use std::unordered_map. Change setWatchOnly to use std::unordered_set

achow101 force-pushed the reduce-wallet-load branch from 4b3439f to 8e3d1e7 Compare July 2, 2020 15:10

hebasto approved these changes Jul 2, 2020

View reviewed changes

This was referenced Aug 4, 2020

wallet: Replace -zapwallettxes with zapwallettxes RPC #19653

Closed

wallet: Remove -zapwallettxes #19671

Merged

achow101 closed this Aug 10, 2020

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

wallet: reduce loading time by using unordered maps #16910

wallet: reduce loading time by using unordered maps #16910

Uh oh!

Conversation

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

Uh oh!

Uh oh!

achow101 commented Sep 18, 2019

Uh oh!

promag commented Sep 18, 2019

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!

achow101 commented Sep 18, 2019

Uh oh!

ryanofsky Sep 18, 2019 • 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 Sep 19, 2019

Choose a reason for hiding this comment

Uh oh!

hebasto Jul 2, 2020

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Conflicts

Uh oh!

achow101 commented Sep 19, 2019

Uh oh!

hebasto commented Jun 27, 2020

Uh oh!

hebasto left a comment

Choose a reason for hiding this comment

Uh oh!

hebasto left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

hebasto Jun 27, 2020

Choose a reason for hiding this comment

Uh oh!

achow101 Jun 29, 2020

Choose a reason for hiding this comment

Uh oh!

achow101 commented Jun 29, 2020

Uh oh!

Uh oh!

Uh oh!

Uh oh!

achow101 commented Jun 29, 2020

Uh oh!

hebasto left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

achow101 commented Jul 2, 2020

Uh oh!

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

achow101 commented Aug 10, 2020

Uh oh!

Uh oh!

achow101 commented Sep 18, 2019 •

edited

Loading

jonatack left a comment •

edited

Loading

ryanofsky Sep 18, 2019 •

edited

Loading

DrahtBot commented Sep 19, 2019 •

edited

Loading

hebasto left a comment •

edited

Loading