Walletwasabi: Wallet takes O(n2) time to open on the number of transactions.

[NicolasDorier]

General Description

If you have a big wallet, wasabi takes very long time to open.

Reason

The ProcessNoLock is called once per transaction.
For each iteration, all the coins, even those already spent are iterated on.
This mean that the wallet becomes slower to open in O(n2).

Version

v1.1.10.2

[NicolasDorier]

Will also need to fix the same issues happening on the KeyManager.

[nopara73]

A thing to improve, which I never got to is that we check all the keys while we shouldn't, we could only check up to the gap limit.

Consider this:

1. Create wallet - Have 3 keys.
1. Close and open wallet, it'll iterate through 3 keys.
1. Got money to key 3, 3 new key will be generated, so have 6 keys.
1. Close and open wallet, it'll iterate through 6 keys.

At the second reopen it doesn't need to iterate through 6 keys for every transaction it could be iterating through 3 keys only until the tx is found to come for key 3, which would increase the temporary gap limit to 6 keys so the next txs would be iterated through 6 keys only.

[NicolasDorier]

https://github.com/zkSNACKs/WalletWasabi/pull/3084 solved 50% of the problem. Now there is the same issue to solve with the iterations over the keys (see the hotspot in my screenshot above)

[nopara73]

Oh, indeed, the same caching can apply there too. Plus improving the keypaths as I described in my comment. The wallet will be on steroids after this :)

[nopara73]

Actually my previous comment about the KeyPaths is not a good idea, because when we launched Wasabi wallets were bloated and those wallets would stop working properly (not sure if anyone is using such old wallets anymore though).

But this one is very performant: https://github.com/zkSNACKs/WalletWasabi/pull/3105

[nopara73]

With finishing up https://github.com/zkSNACKs/WalletWasabi/pull/3108 the wallet will load 7.56 times faster than what it was when this PR was created.

[NicolasDorier]

@nopara73 well if you changed from O(n2) to O(n) it can go infinitely faster.

[nopara73]

@NicolasDorier thanks for bringing the VS profiler tool to my attention. With PR https://github.com/zkSNACKs/WalletWasabi/pull/3132 I achieved another 3.6x speed increase. Which would make the overall speed increase from the released version to be 27.2x.