Hacker News Reader

Comment by damian2000 | Hacker News Reader

damian2000

Anyone know why the STL doesn't use B trees? Are there use cases where Red-Black trees are better?

The STL guarantees both iterator and address stability for the elements of a set, map, or the unordered variants. Those guarantees can't be provided by many more compact representations.

Note that this rules out more than just B-trees: open addressed hash tables and judy array like structures have the same issue.

What do you mean by "iterator and address stability"?

Iterator stability means iterators that point into a container are not invalidated by operations (such as insertions or deletions) on that container.

Address stability means that addresses of elements are not changed by container operations. If you think about it, you can see that maintaining this property rules out contiguous storage of any subset of a container's elements, hence my comment about "compact representations".

It says in the article that B-trees are advantageous when the cost of cache-misses would be worse than the cost of comparisons; e.g., in the case of integers. In comparison, a Red-Black tree would do less comparisons, and hash-table is faster on average but is unordered (more differences?).

In other words, benchmark heavily. And unless you have trees of integers, don't expect the same results.

Without considering cache-miss, Red-black tree is much faster than B-tree. So this b-tree implementation must be tailored to cache-line size, and it may performs badly on some CPUs.

The performance gain on the B-tree container is also largely depends on the size of value. So choose this one carefully.

> So this b-tree implementation must be tailored to cache-line size, and it may performs badly on some CPUs.

Um, no, Btrees are always going to win here as long as key size is relatively small compared to the number of items in the structure. Btrees, for small keyed associations, have a much better "branching factor per cache line." This means that fewer cache misses are needed to find relevant items (insert, delete, read, …), because the trees are shallower, and the cost of a cache miss on a btree node isn't much more expensive than an R-B node.

Benchmark everything and tune your B-Tree container size appropriately, definitely. You could even instantiate the template with multiple different sizes at compile time and benchmark them at run-time, then elect the most efficient implementation for the hardware currently being used.

I don't really think it is possible to say one is better than another without a specific application in mind. Probably just chose whatever one they wanted at the time.

You can, you can talk about which operations need to be fast, as shown by the big-O complexity. You can also talk about constant factors, the cost of specific operations such as comparisons, and locality of reference. In my opinion the latter aspects should be emphasized more because you sometimes come across people who built their careers around slightly more optimal datastructures in terms of big-O complexity, which are nevertheless impractical in any but the most extreme situations due to constant factors (which may only get a footnote mention).

You don't seem to be disagreeing. The point was that you need to know which properties matter to your application before you can truly decide where you should worry about emphasis.

But, for those that want a good example of what you are talking about, it seems to mirror the recent post by Carmack regarding ray tracing. If I recall, the point was that, though ray tracing is better in O terms, it has an outrageous constant factor.

Another wrinkle is that the constant factors can be data-dependent: which data structure to choose can heavily depend on the distribution of data you typically see.

I was disagreeing with the notion that you can only say which algorithm to use if you know the specific application. There are general trade-offs between algorithms which hold independent of any specific application.

But the thought is that the specific application will determine which trade-offs are acceptable and/or applicable. So... I'm still not sure how you are disagreeing.

Now, you can list out the various tradeoffs easily enough. And some algorithms are superior to others, I would imagine. However, which to use and the impact it will have on an application depend more on the application than the datastructure.

Or, am I completely off my rocker?

Reply on news.ycombinator.com