3 ms·
In C and C++ code it's common to use a red-black tree implementation where the node is part of the object. For example, using the standard BSD library #inclu
by wahern 10y ago
In C and C++ code it's common to use a red-black tree implementation where the node is part of the object. For example, using the standard BSD library
#include <sys/tree.h>
struct foo {
RB_ENTRY(foo) rbe; // tree node
};
RB_HEAD(foo_tree, foo);
RB_GENERATE(foo_tree, foo, rbe, foo_cmp);
...
struct foo_tree rbt = { 0 };
struct foo *foo;
...
RB_INSERT(foo_tree, &rbt, foo); // no memory allocation
In such implementations the RB tree will be faster. The reason to prefer a B-tree is to minimize the number of cache misses incurred when loading objects _through_ separately allocated nodes. But if the node is part of the object, you've already eliminated that cost entirely and so a B-tree is strictly inferior.
<sys/tree.h> is written in the same vein as <sys/queue.h>, a collection of list implementations originally included with BSD and even provided by glibc. The tree and especially list routines are used for most of the data structures in *BSD kernels and utilities, and the Linux kernel and other systems often use very similar libraries.
The downside to using predefined, preallocated nodes is that you can't mix-and-match types in the same collection. And an object can only be inserted into a single collection unless you define multiple nodes.
In practice this isn't a concern. Especially in systems programming it's uncommon to need or even want to stash random objects in a collection, or for objects to exist in many multiple trees or lists simultaneously.
And it's a very useful property to be able to rely on the fact that insertion can _never_ fail (always for lists; qualified never for trees). That dramatically simplifies code dealing with complex data structures and that must remain robust in the face of resource exhaustion. It means that once you've allocated a new object, you can guarantee insertion into any number of collections. That also simplifies backing out of a transaction because you can make guarantees about consistency--i.e. that an object is definitely a member of this list or that tree. This benefit is often overlooked in Rust and elsewhere because idiomatic Rust code is expected to exit on memory exhaustion anyhow.
I can't remember the last time I actually used a hash table in C that wasn't specialized (e.g. perfect hash function). The fact that a dynamic hash table may need to be resized introduces an undesirable failure mode; it may happen only once in a million insertions, but that's significantly more often than never. For general use I default to a red-black tree, which usefully can serve as a sorted container, too (e.g. for priority queues). When performance matters (i.e. a proven bottleneck) I'll invariably use a more specialized data structure and implementation suited to the particular problem, perhaps also refactoring other aspects of the code as appropriate.
IMHO, all this concern about the fastest general purpose algorithm and implementation seems like bike shedding. When performance _truly_, _manifestly_ matters, a general purpose implementation is unlikely to suffice.