mempool: reduce lookups, insertions to cache in UpdateForDescendants #24901

1. 
   Crypt-iQ commented at 4:25 pm on April 17, 2022: contributor

   Before this commit, the stageEntries loop could skip a cache lookup since it was done on the grand-children of updateIt initially and not the direct children. This commit changes the logic so that the cache is queried even for the children of updateIt. Additionally, if updateIt has no children in setExclude, it is possible to avoid the cache lookups. And if updateIt has no parents, it is possible to avoid cache insertions.

   • If updateIt has no children in setExclude, then there’s no need to check the cache for any descendants as only entries in setExclude get into the cache.
   • If updateIt has no parents, then a subsequent iteration of the loop in UpdateTransactionsFromBlock won’t use the cache entry for updateIt.

   Prior to this commit, if we had the following tx chain (tx0 is the ancestor of all):

   0tx0 <- tx1 <- tx2 <- [tx3, not in setExclude]
   

   then the stageEntries.empty loop would only query the cache when updateIt was tx0. When updateIt is tx2 or tx1, the cache would not be queried since one “generation” of descendants is effectively skipped for lookup.

2. mempool: reduce lookups, insertions to cache in UpdateForDescendants

   Before this commit, the stageEntries loop could skip a cache lookup
   since it was done on the grand-children of updateIt initially and
   not the direct children. This commit changes the logic so that the
   cache is queried even for the children of updateIt. Additionally,
   if updateIt has no children in setExclude, it is possible to avoid
   the cache lookups. And if updateIt has no parents, it is possible to
   avoid cache insertions.

   d0116fa6ba
3. 
   JeremyRubin commented at 4:52 pm on April 17, 2022: contributor

   concept ack, will need to do a detailed review before upgrading to a full ack :)
4. DrahtBot added the label Mempool on Apr 17, 2022
5. 
   DrahtBot commented at 3:23 am on April 18, 2022: member

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

   Conflicts

   Reviewers, this pull request conflicts with the following ones:

   • #24158 (Optimize Mempool Reorg logic using Epochs, improving memory usage and runtime. by JeremyRubin)
   • #23962 (Use int32_t type for transaction size/weight consistently by hebasto)

   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.

6. 
   luke-jr commented at 7:09 pm on April 19, 2022: member

   This is just a refactor/optimization, correct?
7. 
   Crypt-iQ commented at 7:38 pm on April 19, 2022: contributor

   This is just a refactor/optimization, correct?

   yes, should the title instead contain refactor or optimization?

8. 
   JeremyRubin commented at 1:56 am on April 20, 2022: contributor

   it needs to be treated as a behavioral change IMO; this code is very subtle
9. 
   Crypt-iQ commented at 5:47 pm on April 25, 2022: contributor

   I think this PR does make things slightly more efficient, but it probably isn’t noticeable except in a pathological case where there are 2 reorgs with long chains of txn’s that cause the cacheMap to blow up and IIUC that leads to a memory DoS and this PR wouldn’t help prevent that. Performance gains are probably instead going to come from using different data structures altogether, so not sure this PR is worth it
10. 
    Crypt-iQ commented at 8:08 pm on May 5, 2022: contributor

    Closing since I don’t see a statistically significant improvement when running a functional test that makes UpdateTransactionsForBlock take ~25s
11. Crypt-iQ closed this on May 5, 2022

    ---

12. Crypt-iQ deleted the branch on May 5, 2022
13. DrahtBot locked this on May 5, 2023

Contributors
Crypt-iQ JeremyRubin DrahtBot luke-jr

Labels
Mempool