4 ms·
If cache locality is a big concern, you should either think about implementing some variation of a B-tree, or do very fancy things like design trees with van Em
by OskarS 8y ago
If cache locality is a big concern, you should either think about implementing some variation of a B-tree, or do very fancy things like design trees with van Emde Boas layouts (which are cache oblivious and thus has excellent cache performance) [0]. Or both, at once!
Both of these things are significantly more complex than just implementing a simple max-heap, which will almost certainly perform well enough for most any practical purpose. A red-black tree will probably have significantly worse cache behaviour than a max heap, since every dereference is jumping around in memory. In a max-heap, you can count on having at least a couple of the first levels in cache when you start.
[0]: http://tildeweb.au.dk/au121/papers/soda02.pdf http://tildeweb.au.dk/au121/papers/soda02.pdf
- AstralStorm 8y agoYes, if you're keeping pointers. The thing is, the gain is completely wiped out by maintaining the heap invariant which has to copy the whole thing instead of walking a single branch. The same memory bandwidth issue plagues B trees. This shows up with big trees. For small, again, you're better off with a list. Van Emde Boas trees are better but yet more complex still. (And colored pointer variant is not available for them) The tradeoff is speed of write vs read in case of heaps. They have pretty bad write performance.
- jemfinch 8y agoPHK's "B-heaps" are interesting: https://queue.acm.org/detail.cfm?id=1814327 https://queue.acm.org/detail.cfm?id=1814327 .