[WIP] add free list to unordered map #25274

1. 
   JeremyRubin commented at 8:50 pm on June 3, 2022: contributor

   This is offered as a “dumb” alternative to @martinus’s very clever #22702, seeking some approach ACK before I spend more time polishing it.

   Instead of using a custom allocator, we just take advantage of the statically assertable fact that a node_handle is smaller than the COutpoint key type (or really, key type or value type, but key type happens to be big enough) to build a free list of extracted nodes that we then don’t have to reallocate to reinsert. This would enable us to initialize a cacheMap with any number of nodes we like by inserting with N sequential COutpoints, and then removing them, or by calling reserve (unclear if any functional difference?).

   In particular, this does not require mucking with any map internals, it’s just using the external guts in a ‘well defined but weird’ way. Perhaps something like this is less scary @laanwj?

   Offered in WIP status for approach ACKs, missing (at least):

   1. Count total allocation size / count elements in free list
   2. Deallocate/clear the free list correctly (nodes in free list remain reinsertable after clear)
   3. make the create_new_cache_coin function have all the emplace-like behaviors we might want
   4. Any thorough review of correctness5.
   5. Generically wrapping it for any map where sizeof(K) >= sizeof(node_type).

   In contrast to #22702, this approach would likely not save any space in allocations, since it can’t allocate pages at a time.

2. [WIP] add free list to unordered map aac74b3465
3. JeremyRubin force-pushed on Jun 3, 2022
4. DrahtBot added the label UTXO Db and Indexes on Jun 3, 2022
5. 
   DrahtBot commented at 0:44 am on June 4, 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:

   • #25325 ([WIP] Add pool based memory resource by martinus)
   • #17487 (coins: allow write to disk without cache drop by jamesob)
   • #9384 (CCoinsViewCache code cleanup & deduplication by ryanofsky)

   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. 
   martinus commented at 6:03 am on June 4, 2022: contributor

   I’m not sure if that approach will be a net benefit. One of the main advantages of the allocator in #22702 is that not every node has to be malloced’, saving the considerable memory overhead. I think the only way to get rid of the many std::unordered_map allocations is to use a custom allocator.

   Another approach to hold on to the memory that should in theory do all what’s done in #22702 is to just use std::pmr::unsynchronized_pool_resource: That memory resource has a pool which holds on to its memory until it is destroyed, exactly like my node_allocator. I don’t know though how its implemented or what memory overhead individual allocations have. https://en.cppreference.com/w/cpp/memory/unsynchronized_pool_resource

   Usage would be relatively simple, like so:

   0using CCoinsMap = std::pmr::unordered_map<COutPoint, CCoinsCacheEntry, SaltedOutpointHasher>;
   1
   2auto options = std::pmr::pool_options();
   3options.largest_required_pool_block = 128; // TODO no idea what good values are
   4options.max_blocks_per_chunk = 262144 / options.largest_required_pool_block;  // TODO no idea what good values are
   5
   6auto mr = std::pmr::unsynchronized_pool_resource();
   7auto map = CCoinsMap{0, SaltedOutpointHasher{}, std::equal_to<COutPoint>{}, &mr};
   

   I did some rudimentary benchmarking with this, but this seemed to be even slower than a plain std::unordered_map so I didn’t follow this more closely.

7. JeremyRubin closed this on Jun 10, 2022

   ---

8. DrahtBot locked this on Jun 10, 2023

Contributors
JeremyRubin DrahtBot martinus

Labels
UTXO Db and Indexes