Try storing Node directly in Entry - Githubissues

tzaeschke / phtree-cpp

PH-Tree C++ implementation

Apache License 2.0

28 stars 9 forks source link

Try storing Node directly in Entry #39

Closed tzaeschke closed 2 years ago

tzaeschke commented 2 years ago

Store Node directly in Entry instead of storing a pointer. Nodes are quite small (the entries are in a separate container) so we could avoid a memory indirection at the cost of slightly larger Entries.

tzaeschke commented 2 years ago

This branch demonstrates this. Issue: array_map does not work because it tries to directly instantiate the full tree. Workaround: disable array_map in node.h.

Results:

query_mm_box_d and update_mm_box_d are about 5-10% faster. They are 6D, so this shows that embedding nodes in entries has a benefit.
query_mm_d is 10% faster. This is also due to using sparse_map instead of array_map for 3D.
update_mm_d is about 30% slower. Again, this is due to using sparse_map instead of array_map for 3D.

Conclusion:

Avoiding one memory indirection is worthwhile.
Instead of storing Nodes in Entries, on should consider turning sparse_map into a "flat" map that avoids some indirection.
We should check again why array_map is considerable slower that sparse_map for queries. That should not be the case.