Cache vout IsMine() value on `CWallet::AvailableCoins()` #9939

joaopaulofonseca · 2017-03-07T13:59:20Z

This PR tries to improve the performance of the listunspent, fundrawtransaction, sendtoaddress and other RPC calls by improving CWallet::AvailableCoins() iteration through the wallet transactions.

E.g. If a given address is an outpoint of N transactions, I guess there's no point to check N times if the address IsMine().

This PR supersedes #7823 although it's a different approach. In that PR, caching accurately those values was a little tricky because of all the scenarios that could make the cache invalidated (conflicts, double-spends, reorganizations, abandoned transactions, etc, ...).

Still, with this approach I got performance gains up to 90% on CWallet::AvailableCoins() for large wallets.

pedrobranco · 2017-03-07T18:00:30Z

src/wallet/wallet.cpp

+                    mine = mapOutputIsMine[pcoin->tx->vout[i].scriptPubKey] = IsMine(pcoin->tx->vout[i]);
+                }
+
+                if (mine != ISMINE_NO && !(IsSpent(wtxid, i)) &&


I there's an ACK from the community, I would love to see this giant if break down with several early continues (to facilitate the reading), as applied here.

This would seem like a good idea, especially if the continues were documented with new comments. Not really on-topic for this PR, however.

NicolasDorier · 2017-03-08T03:11:04Z

Please check #9167, morcos is working on it

joaopaulofonseca · 2017-03-08T11:26:00Z

@pedrobranco yes, that if is a little mess. I'll also take a look at it.

@NicolasDorier If I understood the @morcos PR correctly, it's related to the isminetype of the transaction inputs and not the outputs, which we need here to find our utxos.

NicolasDorier · 2017-03-08T11:51:18Z

my bad I read too fast.

NicolasDorier · 2017-03-08T12:00:02Z

Why not having the cache scoped to the WalletTransaction type ?
Instead of

IsMine(pcoin->tx->vout[i])

we would have

pcoin->IsMine(i)

where WalletTransaction::IsMine would cache the result at the WalletTransaction level.

this would make it more readable,
this cache could be populated everywhere in the code when IsMine is called,
the cache would span accross different calls to AvailableCoins, making AvailableCoins even faster.

ryanofsky

utACK dca8d8926e655ba6639e748bcd32c560a5539b88

Code seems fine, but I don't know very much about the performance implications of this change, and would leave it for others to discuss. NicolasDorier's suggestion seems like a reasonable alternative, too.

ryanofsky · 2017-03-08T19:13:28Z

src/wallet/wallet.cpp

+                    mine = im->second;
+                } else {
+                    mine = mapOutputIsMine[pcoin->tx->vout[i].scriptPubKey] = IsMine(pcoin->tx->vout[i]);
+                }


Can simplify this as:

+ auto inserted = mapOutputIsMine.emplace(pcoin->tx->vout[i].scriptPubKey, ISMINE_NO); + if (inserted.second) { + inserted.first->second = IsMine(pcoin->tx->vout[i]); + } + isminetype mine = inserted.first->second;

ryanofsky · 2017-03-08T19:15:14Z

src/wallet/wallet.cpp

+                    mine = mapOutputIsMine[pcoin->tx->vout[i].scriptPubKey] = IsMine(pcoin->tx->vout[i]);
+                }
+
+                if (mine != ISMINE_NO && !(IsSpent(wtxid, i)) &&


This would seem like a good idea, especially if the continues were documented with new comments. Not really on-topic for this PR, however.

joaopaulofonseca · 2017-03-10T12:13:19Z

@NicolasDorier that's a good suggestion. Actually a while ago I was trying to create a cache to store these values, but at the wallet level. But couldn't manage to successfully achieve a solution with both reliability and speed. But I will look into your approach.

@ryanofsky Ok, I like it. I'll simplify that piece of code.

RHavar · 2017-06-01T19:05:37Z

I've tested 46cbc0a

Before median time of listunspent after a few runs on my wallet was 14.4 seconds, now it's 12.8s.

So it seems faster, but not earth shatteringly so. For reference my wallet has about ~520k transactions in it, where of them ~168k are mine (outgoing transactions).

--

To me it seems like @NicolasDorier's suggestion is the way to go, I suspect the reuse of the cache is going to help a lot.

laanwj · 2017-06-05T15:28:43Z

@RHavar thanks for testing!

joaopaulofonseca · 2017-06-05T15:48:05Z

@RHavar thanks a lot for your feedback! The current implementation of listunspent is a little tricky to optimize without a larger refactor.

I've tried to optimize each of the two heavier calls within listunspent: IsMine() and IsSpent(). But without optimizing both, they will only fix different use cases separately, which will behave very differently for large wallet vs large amount of unspents.

I haven't had much time to work on this lately, but it's a problem I'd like to come up with a clean solution in the near future, since it's an issue affecting almost everyone with large wallets.

ryanofsky

utACK 46cbc0a. Code is slightly simplified since last review, and change looks good assuming performance improvements warrant it.

NicolasDorier · 2017-07-26T02:37:00Z

utACK 46cbc0a, it is simple enough. Can keep wallet level caching for later PR.

ryanofsky · 2017-10-12T17:21:47Z

Change is simple and has multiple acks, but needs to be rebased.

maflcko · 2017-11-10T18:30:16Z

Not rebased in 30 days.

This is now up for grabs.

joaopaulofonseca · 2017-11-12T14:33:25Z

Sorry guys, haven't had much time to work on this lately.. Although this improves the speed, the last tests I did showed there are still some edge cases where the unspent count differs which means that the cache is not accurate.. I'll try to pick this up in the future, and reopen if needed.

ryanofsky · 2018-01-08T22:34:11Z

Could add up for grabs label

@joaopaulofonseca

Special thanks to @joaopaulofonseca for contributing this to the Bitcoin repo bitcoin/bitcoin#9939

joaopaulofonseca mentioned this pull request Mar 7, 2017

Add index to wallet UTXO #7823

Closed

laanwj added the Wallet label Mar 7, 2017

pedrobranco reviewed Mar 7, 2017

View reviewed changes

ryanofsky reviewed Mar 8, 2017

View reviewed changes

Cache vout IsMine() value on CWallet::AvailableCoins()

46cbc0a

joaopaulofonseca force-pushed the enhancement/cache-wallet-available-coins-output-ismine branch from dca8d89 to 46cbc0a Compare March 13, 2017 17:30

laanwj mentioned this pull request Jun 1, 2017

listunspent is really slow #10492

Closed

ryanofsky reviewed Jul 25, 2017

View reviewed changes

maflcko closed this Nov 10, 2017

maflcko added the Up for grabs label Jan 11, 2018

giaki3003 added a commit to LUX-Core/lux that referenced this pull request May 2, 2019

[db] Cache vout IsMine() value on CWallet::AvailableCoins()

96c79c9

Special thanks to @joaopaulofonseca for contributing this to the Bitcoin repo bitcoin/bitcoin#9939

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Cache vout IsMine() value on CWallet::AvailableCoins() #9939

Cache vout IsMine() value on CWallet::AvailableCoins() #9939

Uh oh!

Conversation

joaopaulofonseca commented Mar 7, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

pedrobranco Mar 7, 2017 • 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!

ryanofsky Mar 8, 2017

Choose a reason for hiding this comment

Uh oh!

NicolasDorier commented Mar 8, 2017

Uh oh!

joaopaulofonseca commented Mar 8, 2017

Uh oh!

NicolasDorier commented Mar 8, 2017

Uh oh!

NicolasDorier commented Mar 8, 2017

Uh oh!

ryanofsky left a comment

Choose a reason for hiding this comment

Uh oh!

ryanofsky Mar 8, 2017

Choose a reason for hiding this comment

Uh oh!

ryanofsky Mar 8, 2017

Choose a reason for hiding this comment

Uh oh!

joaopaulofonseca commented Mar 10, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

RHavar commented Jun 1, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

laanwj commented Jun 5, 2017

Uh oh!

joaopaulofonseca commented Jun 5, 2017 • 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!

NicolasDorier commented Jul 26, 2017

Uh oh!

ryanofsky commented Oct 12, 2017

Uh oh!

maflcko commented Nov 10, 2017

Uh oh!

joaopaulofonseca commented Nov 12, 2017

Uh oh!

ryanofsky commented Jan 8, 2018

Uh oh!

Uh oh!

Cache vout IsMine() value on `CWallet::AvailableCoins()` #9939

Cache vout IsMine() value on `CWallet::AvailableCoins()` #9939

joaopaulofonseca commented Mar 7, 2017 •

edited

Loading

pedrobranco Mar 7, 2017 •

edited

Loading

joaopaulofonseca commented Mar 10, 2017 •

edited

Loading

RHavar commented Jun 1, 2017 •

edited

Loading

joaopaulofonseca commented Jun 5, 2017 •

edited

Loading