👍 andrewtoth approved a pull request: "optimization: Reduce cache lookups in CCoinsViewCache::FetchCoin"
(https://github.com/bitcoin/bitcoin/pull/30326#pullrequestreview-2161892129)
ACK 00052ecc0402f2c53e3602b901a937b64aa7f7cc

I benchmarked IBD from a local node connection to block 820k, twice on this branch twice on master.
This branch: 22265 seconds mean time
Master: 22523 seconds mean time

Also benchmarked `-reindex-chainstate` up to block 820k, twice on this branch and twice on master.
This branch: 22085 seconds mean time
Master: 22255 seconds mean time

So it appears to shave off ~3 minutes of time.

💬 sipa commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667729124)
Hmm, it's not at all obvious that this will be faster, as an erase by outpoint involves hashing and lookup in the hash table. It may be worth benchmarking the two options to make sure.

Another option is switching the coinscache map from `std::unordered_map` to a Boost multiindex, which can simultaneously maintain a hashtable and a linked list transparently without needing to hack our own linked list on top.

💬 andrewtoth commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667729456)
> Hmm, it's not at all obvious that this will be faster, as an erase by outpoint involves hashing and lookup in the hash table. It may be worth benchmarking the two options to make sure.

Sorry, I may not have been clear. I am *not* erasing by outpoint. I only erase the spent coins if `erase=false` by outpoint, because that's the only way to find those in constant time.
Otherwise, for a normal erasing flush, we just call `mapCoins.clear()` at the end to wipe them all at once.
I think I have
...

💬 sipa commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667730042)
Isn't this an erase by outpoint?

💬 andrewtoth commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667730311)
Yes, but if `!erase`. This is what `Sync` was doing before I moved this into `BatchWrite`. Only spent outpoint when we don't want to clear the cache. This is what I already benchmarked to be much faster.

💬 andrewtoth commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667730532)
This is the reason we need to have the linked list be `CoinsCachePair`s instead of `CCoinsCacheEntry`s, as you mentioned [here](https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1296524385).

💬 sipa commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667730793)
Ah, thank you! I missed that this was already being done in master.

💬 sipa commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667731169)
I understand now. My point stands that both versions are doing something unnecessary, but I see now it's already a strict improvement:
* For `erase=false`, you erase spent coins where iterating, which involves a hashtable lookup, even though you already have a pointer to the element you're erasing (and it's just due to an interface limitation that this cannot be turned into an iterator that can be erased directly).
* For `erase=true`, you still iterate a second time (inside `mapCoins.clear()`)
...

💬 andrewtoth commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667731296)
Do we want to add more Boost dependencies? I thought we wanted to go the other way.

💬 sipa commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667731593)
Boost multi-index is headers-only, so it's just a build-time dependency, not a runtime one. For the mempool we already realistically can't avoid having something that's functionally equivalent to boost multiindex, so I'm not too worried about adding more reliance on it. I do know @theuni is looking into having a simple ad-hoc replacement for it, though.

💬 andrewtoth commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667731791)
Err, not `master`, but the previous version of this PR that I force pushed over an hour ago.
In `master` it is looping through the entire `cacheCoins` map, and deleting spent entries. With this approach we do have to do a hash and lookup, but it's constant time instead of linear.

💬 andrewtoth commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#issuecomment-2212512381)
Thank you for your thorough review @sipa! Will run some more extensive benchmarks for all the recent changes that should be done in the coming weeks.

💬 sipa commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667733013)
Hmm, right. But so there are still two possible variants for the `erase=false` case?
* 1. One where they are erased during BatchWrite, using outpoint-based erase
* 2. One where all the erasing is done inside `Sync`, and `BatchWrite` only does flag clearing.

(1) has higher CPU cost (due to hashing and hash-table search), while (2) will involves accessing entries' memory twice. Which of the two is faster isn't clear to me, as it'll depend on CPU cache sizes etc.

💬 sipa commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667733399)
Ah, but (2) necessarily also involves an outpoint-based erase, as you only want to erase flagged entries without iterating the non-flagged ones. Right.

💬 andrewtoth commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667733508)
2 also required an outpoint based deletion, so this approach just moves that deletion into the same loop instead of clearing unspent flags in the first loop and then looping through spent entries again in a second loop and deleting them via outpoint.

💬 andrewtoth commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667733587)
If only we could convert a ConsCachePair back into a map iterator...

💬 sipa commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667733924)
In boost::multi_index you can :D (see https://www.boost.org/doc/libs/1_77_0/libs/multi_index/doc/reference/hash_indices.html#iterators, the `iterator_to` function).

I'll shut up now and mark this resolved. Thanks for bearing with me.

💬 andrewtoth commented on pull request "Don't empty dbcache on prune flushes: >30% faster IBD":
(https://github.com/bitcoin/bitcoin/pull/28280#discussion_r1667734233)
> you still iterate a second time (inside mapCoins.clear()),

Hmm I added this in the latest revision because we not had the mapCoins and could clear it.
Before this patch was just not erasing the entries and removing checking that it is empty in ReallocateCache. If the map is destroyed does it not essentially do a clear as well, so this is a wash whether we clear now or on destruction?

💬 paplorinc commented on pull request "optimization: Reduce cache lookups in CCoinsViewCache::FetchCoin":
(https://github.com/bitcoin/bitcoin/pull/30326#issuecomment-2212546977)
Thanks a lot for checking, @andrewtoth!

💬 Prabhat1308 commented on pull request "p2p: Fill reconciliation sets (Erlay) attempt 2":
(https://github.com/bitcoin/bitcoin/pull/30116#discussion_r1667753973)
```suggestion
for (int i = 1; i < inbound_peers; ++i) {
// create 4000 random wtxids so that FANOUT_TARGETS_PER_TX_CACHE_SIZE is breached
for (int j = 0; j < 4000; ++j) {
tracker.ShouldFanoutTo(Wtxid::FromUint256(frc.rand256()), i,
/*inbounds_fanout_tx_relay=*/0, /*outbounds_fanout_tx_relay=*/0);
}
}
```

increases coverage of the units tests to check the cache_size check in ```IsFanoutTarget``` .