johan torp f910700701 Memory-optimized custom IOStore hash map - 65.7 -> 25.9MB for internal project on Gen5 console ...

Exploits that the map is large (~1M) and rarely modified

Memory saved by:
* TMap saves slot and next-in-slot using 8B / item. FPackageIdMap is built once presorted, next-in-slot is next item. Only use 1bit / item to mark slot end.
* Only store 3/4 of FPackageId key - 1/4 is implicit by slot, which requires min 128K capacity
* Up to 400% load factor using 4-stage lookup, slot -> 2B hash -> 4B hash -> value. 2B array fits 32 items / 64B cache line, enabling a high load factor with little perf loss
* More compact entry handle and entry memory layout
* Deduplicating some entries
* Carefully storing entry data so container ownership is inferable from offset allows dropping 7.5MB of FIoContainerHeader::PackageIds and non-deduped StoreEntries

Surprisingly lookup got >4.5x faster too, despite 4 memory indirections instead of 2. Lookup can be optimized further by vectorizing. Rebuilding the map is also faster.

#rb pj.kack

[CL 29906389 by johan torp in ue5-main branch]

2023-11-23 03:17:18 -05:00

25 KiB

Raw Permalink Blame History

View Raw