Conversation

Modern computers do not quite work in the way most people think.

Quote Tweet

Jul 3, 2019

Attention CSEd Twitter: While Big-O matters, the constant-factors involved in things like cache-hit rate are at least as important. If you're teaching balanced-binary-trees for any reason other than tradition, I'd love to chat.

Replying to

I strongly disagree with the implication that teaching self-balancing binary search trees isn't useful though. B-trees are one of the most cache friendly data structures to the point that they're broadly used on storage and it's natural to learn as a follow-up to red-black trees.

Replying to

and

The time complexity of these data structures does matter a lot and it only takes a few dozen elements to start beating a vector. Constant factors matter a lot too, but it doesn't make the time complexity unimportant. Ordered data is a big part of providing good data locality too.

Replying to

and

Red-black trees are a bad choice in the general case rather than using a B-tree or the special case of generating the map / set once rather than using a sorted vector. However, they do have a crucial use case for intrusive data structures for avoiding dynamic allocation/failure.

1:08 AM · Jul 5, 2019Twitter Web Client

Replying to

and

Even for unordered usage, a B-tree will often outperform a hash table for cases where the data structure is large. The hash table ends up almost guaranteeing a cache miss for each lookup. The B-tree will have a few cache misses for an isolated lookup, which is seemingly worse.

Replying to

and

However, in practice, the lookups will often be clustered / related to the ordering and the B-tree can end up resulting in far fewer cache misses in practice. Also, other than performing worse for more than a few dozen elements, unsorted vector purges far more other cached data.

Show replies