Node storing: Hashmap replacement with Level-wise std::vector #42
Description
The currently used std::unordered_map has many compromises:
- Bad for cache locality
- Hashing has some overhead
- Allocation strategy differs widely between the platforms.
- Higher dimension requires different container
With a level-wise storage has
- better cache locality
- no hash overhead
- less allocation during the creation
- easy level-wise traverse
- bitflag for children can be applied if nodes are level-wise stored
Contra:
- the applied cache locality is suited for BFS instead of DFS
- Replace all bottom-up algorithms with top-down
- Morton Z id removal from everywhere
- Maybe a ParentID is required in the Node
- Bitflag and node order could be problematic with the current creation, which happens in non-children-order.
- Large refactoring with major interface changes
Preliminary proto showed ~15% performance gain in creation, and no performance loss in RayIntersection.
Branch: proto_levelvector_based_storage