C++ Programming Questions to Ask on Interview (2017)

Re:C++ Programming Questions to Ask on Interview (2017) by OskarS on Friday October 19, 2018 @03:56AM (#18254897)

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

[ Parent | on HN ]

Re:C++ Programming Questions to Ask on Interview (2017) by AstralStorm on Friday October 19, 2018 @04:24AM (#18255048)

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.

[ Parent | on HN ]

Re:C++ Programming Questions to Ask on Interview (2017) by jemfinch on Friday October 19, 2018 @09:23AM (#18256524)

PHK's "B-heaps" are interesting: https://queue.acm.org/detail.cfm?id=1814327 .

[ Parent | on HN ]