4 ms·
It's not just cache locality, but also at least the effectiveness of cache prefetching and the ability to use wider operations.. simple array loops are somethin
by dmw_ng 3y ago
It's not just cache locality, but also at least the effectiveness of cache prefetching and the ability to use wider operations.. simple array loops are something compilers can often vectorize without assistance.
- dgreensp 3y agoYes, but, operations like, “Does this node have children or is it a leaf?” should not require reading the entire array. Or, how many children; get the first child. Traversing the tree in pre-order or post-order doesn’t just have less cache locality than a B tree (say), it involves sorting a vector of vectors and is at best N log N and O(N) extra space. Deleting a node requires a O(N) writes. Every little operation is massively less local and less efficient. I stand by the lack of integrity that I got downvoted for pointing out! I’ll die on that hill.
- ninepoints 3y agoNo idea why your parent comment was flagged. The proposed data structure is truly horrendous but somehow, this post remains on the front page...