BTreeMap documentation has confusing wording about binary search tree performance issues

[danielrainer]

Location

rust/library/alloc/src/collections/btree/map.rs

Lines 48 to 49 in f6cb952

	/// is stored in its own individually heap-allocated node. This means that every single insertion
	/// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these

Summary

In the discussion of performance issues of binary search trees, it is written that [...] every single comparison should be a cache-miss.

I think this is confusing in the following ways:

• Comparisons are not cache misses. They operate on values which are already loaded into registers. Of course, the nodes need to be loaded in order to perform the comparisons, but that is not what is written in the relevant sentence.
• The use of should could be understood as a value judgement. I doubt it was intended as one, but rather to express that a cache miss is expected. However, even this interpretations is not fully accurate, since the next node for the tree traversal might be cached (because it was recently accessed or close enough in memory to something recently accessed that it was cached alongside).

I suggest replacing the last two sentences of the paragraph with something like This means that every single insertion triggers a heap-allocation, and for every comparison a node needs to be loaded, which could result in a cache miss. Since both heap-allocations and cache-misses are notably expensive in practise, we are forced to, at the very least, reconsider the BST strategy.

[workingjubilee]

I feel that in 2024 the section on binary search trees is a bit of a distraction.

I think It is sufficient to say something like,

"A B-tree resembles a binary search tree but instead of a single element per leaf node, each leaf is an entire array. Searches traverse the tree itself in logarithmic time, but then perform a simple linear search on that array, which is extremely fast on modern hardware. The exact size of the array used by BTreeMap is not specified."

Done, no need to explain the exact reasons. If we do wish to explain the theory behind B-tree performance, we can do it near the end, when we are not crushed for time and space. I say we are short on such because our first primary goal is not to explain "why not BinarySearchTreeMap?" We don't have a BinarySearchTreeMap, but we do have HashMap, so our first task is "why should you EVER look at this data structure and not HashMap?" This is true even if we never directly compare, in the type's docs, against HashMap.

[danielrainer]

Yes, I think this is a more reasonable approach.