3 ms·
I was recently working some data structures in C++ where I needed to have tree-based structures and sustained performance. The compromise that I hit on was to
by btilly 14y ago
I was recently working some data structures in C++ where I needed to have tree-based structures and sustained performance. The compromise that I hit on was to allocate all of the nodes of a tree out of an std::vector. This allowed me the flexibility of tree-based structures together with all of the locality of reference that I needed. As the tree grew, the vector would resize and move, but the amortized average cost of that is directly proportional to the size of my data structure.
I offer this in case a similar compromise might be useful for someone else. (My guess is that it is probably standard for people who need to know this sort of stuff. I'm just not usually someone who needs to know this sort of stuff.)
- minimax 14y agoHow big of a tree was it and how big were the nodes? I don't see how you get any locality of reference for a large enough tree, and you certainly don't get any of the hardware prefetch. To get any benefit out of this I think you need multiple nodes to fit on a cache line and for tree traversal to hit adjacent nodes in the vector (but how could you guarantee that?)
- btilly 14y agoI had several related data structures, and the details varied. But for the most part 5-1000 nodes per tree, with a node size of 12-32 bytes. And in my use case I'd be walking through a vector with thousands to hundreds of thousands of things, having to do operations involving lookups into 2-3 of these trees at a time. The trick would not make sense for large trees. But it worked out very well for me.
- berkut 14y agoThis is used a lot for things like acceleration structures in 3D graphics - you also get the benefit of being able to store an uint32_t offset instead of a 64-bit pointer, fitting a bigger tree in memory/cache.
- btilly 14y agoI used that trick as well. :-)