5 ms·

I'm curious, what's wrong with array based heaps? I've implemented both Red-black trees and array based heaps in the past. If I had to take a guess I would say

I'm curious, what's wrong with array based heaps? I've implemented both Red-black trees and array based heaps in the past. If I had to take a guess I would say the latter should be noticeably faster. In any case Red-black trees are much harder to implement.

AstralStorm 8y ago
The problem with heaps is cache locality if you have anything different from tiny types like pointers stored inside. Plus that they do have to be resized more often than the other structures and you're forced to allocate a continuous chunk of memory if they're big. (And for small, you actually cannot beat a simple list with a one item sort by a heap.) Both skiplists and rbtrees allow for a tricky but efficient colored pointer implementation and also if you need fine grained locking or lock free implementations.
- kadoban 8y ago
  Red-black trees aren't known for having good spatial locality of reference (heaps aren't either, but I fail to see how this is a point in favor of RB trees). Is there a particular implementation that doesn't share this shortcoming that you had in mind? That would be interesting to me. If allocating a heap as a big chunk were a problem, you could certainly do it as nodes and pointers like a RB tree is traditionally done (reify the tree instead of array-encode it). Though the array-encoding is itself usually an optimization, so I wouldn't think you'd want to do that. Doing one big allocation (and copy) every once in a while (in a table-doubling-esque manner) should be a win over individually allocating nodes, if you can amortize over many operations. And again if that's not true or undesireable, you can just allocate a heap like you'd allocate a tree normally.
  - jstimpfle 8y ago
    I was wondering the same, and was thinking that maybe the RB needs to touch fewer nodes to rebalance after a remove operaiton, thus resulting in better cache friendliness (although GP said cache _locality_)? But it seems unlikely since the heap property is much weaker than the RB-balanced binary tree property.
    - AstralStorm 8y ago
      RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage and are not moved far around as in some balancing trees and are small. Thus you end up with cache locality even when not directly aiming at it. B+trees have some of that property by only keeping data in leaves, but you need a very smart leaf layer to capitalize on it. You end up with more inner nodes though.
      - jstimpfle 8y ago
        > RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage That's true only if you create the nodes in already sorted order. Furthermore, for the RB version of priority queues, you need pointers, which are not needed for the array based variant (the childs of cell x are always 2* x and 2* x+1), which typically adds another 16 bytes of data per node.
    - SamReidHughes 8y ago
      A heap tree has a very specific structure, even if value locations have some flexibility. An RB-tree has more flexibility in its structure, with rigidity in value locations.
  - 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 ago
      Yes, 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 ago
      PHK's "B-heaps" are interesting: https://queue.acm.org/detail.cfm?id=1814327 https://queue.acm.org/detail.cfm?id=1814327 .

AstralStorm 8y ago

The problem with heaps is cache locality if you have anything different from tiny types like pointers stored inside. Plus that they do have to be resized more often than the other structures and you're forced to allocate a continuous chunk of memory if they're big. (And for small, you actually cannot beat a simple list with a one item sort by a heap.) Both skiplists and rbtrees allow for a tricky but efficient colored pointer implementation and also if you need fine grained locking or lock free implementations.

kadoban 8y ago
Red-black trees aren't known for having good spatial locality of reference (heaps aren't either, but I fail to see how this is a point in favor of RB trees). Is there a particular implementation that doesn't share this shortcoming that you had in mind? That would be interesting to me. If allocating a heap as a big chunk were a problem, you could certainly do it as nodes and pointers like a RB tree is traditionally done (reify the tree instead of array-encode it). Though the array-encoding is itself usually an optimization, so I wouldn't think you'd want to do that. Doing one big allocation (and copy) every once in a while (in a table-doubling-esque manner) should be a win over individually allocating nodes, if you can amortize over many operations. And again if that's not true or undesireable, you can just allocate a heap like you'd allocate a tree normally.
- jstimpfle 8y ago
  I was wondering the same, and was thinking that maybe the RB needs to touch fewer nodes to rebalance after a remove operaiton, thus resulting in better cache friendliness (although GP said cache _locality_)? But it seems unlikely since the heap property is much weaker than the RB-balanced binary tree property.
  - AstralStorm 8y ago
    RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage and are not moved far around as in some balancing trees and are small. Thus you end up with cache locality even when not directly aiming at it. B+trees have some of that property by only keeping data in leaves, but you need a very smart leaf layer to capitalize on it. You end up with more inner nodes though.
    - jstimpfle 8y ago
      > RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage That's true only if you create the nodes in already sorted order. Furthermore, for the RB version of priority queues, you need pointers, which are not needed for the array based variant (the childs of cell x are always 2* x and 2* x+1), which typically adds another 16 bytes of data per node.
  - SamReidHughes 8y ago
    A heap tree has a very specific structure, even if value locations have some flexibility. An RB-tree has more flexibility in its structure, with rigidity in value locations.
- 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 ago
    Yes, 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 ago
    PHK's "B-heaps" are interesting: https://queue.acm.org/detail.cfm?id=1814327 https://queue.acm.org/detail.cfm?id=1814327 .