Depending on the size of your wallet and number of UTXOs, performance gains may be up to 98%.

Yes, this makes sense.

How does it affect memory usage?

Concept ACK, it's silly that we didn't have this.

Memory usage: I expect it to consume around 80 bytes per unspent output on 64-bit platforms.

ACK

Rename first commit to something like Add index to wallet UTXO

The overall memory usage will depend on the wallet size, more particularly on the UTXO count. Given the info being stored per UTXO (an outpoint and a pair with isminetype and pointer to Tx), the extra memory increment won't be that much.

@promag that makes sense. This is not a cache, but more like an index..

Tested ACK.

In my case the improvements of listunspent are from 12s. to 0.1s .

Nice work!
Concept ACK.

Given the info being stored per UTXO (an outpoint and a pair with isminetype and pointer to Tx), the extra memory increment won't be that much.

So this only uses (~80 bytes) memory per actually unspent output that is in the wallet? That's great. I then don't expect the extra memory use for that to be significant. The bulk is wasted on keeping historical transactions anyway.

Concept ACK.

Concept ACK. Thanks for working on this.

Solves #6573.

lightly tested ACK

This change greatly improves the performance of AvailableCoins and indirectly listunspent and others. Is it reasonable to expect this in next 0.12 update?

@promag Only bug fixes and consensus changes are backported to old releases. It's well on track for 0.13, though.

I think this needs at least one more code review ACK before merge (to master, not 0.12)

How does this deal with:

• reorganizations (coins marked as spent may go back to being unspent)?
• conflicts (there may be multiple unconfirmed transactions at the tip, and which set of them is accepted can change easily)?
• abandoned transactions?

This needs a rebase.

@jpdffonseca Feel like answering my questions above?

@sipa I'm working to unify mapTxSpends and mapTxUnspents.

@jpdffonseca Are you still working on this? We need performance improvements especially for large wallets.

Needs rebase.

@paveljanik lately I haven't had too much time to work on it. After testing more deeply, I realized that this solution does not always handles well some of the cases mentioned above by @sipa, so it should have a different approach.

I've been trying another improvements that optimize not the unspents list itself but other values necessary to calculate the unspents, such as the call CWallet::IsMine().
With that I obtained satisfactory results, around 50% for large wallets. I'll finish that and submit PR.

Closing due to inactivity. @joaopaulofonseca if you do end up finishing work on your other improvements PRs are welcome.

Deprecated partially by #9939. Caching accurately these values gets a little tricky because of all the scenarios that could make the cache invalidated (conflicts, double-spends, reorganizations, abandoned transactions, etc, ...).