3 ms·
> The other popular self-balancing trees are good candidates as well (AVL and LLRB/Red-black). While they do essentially the same, they can have very different
by loeg 10y ago
> The other popular self-balancing trees are good candidates as well (AVL and LLRB/Red-black). While they do essentially the same, they can have very different performance characteristics, and switching can influence the program’s performance vastly.
In what scenario would you prefer an RB-tree (or AVL tree) to a B-tree?
My understanding is that the performance characteristics of RB/AVL trees can mostly be described as "worse." Maybe insert speed? But in that case, you'd really prefer an LSM tree.
The author is also very confused about how hash table DoS attacks are protected. And what a cryptographic hash is. There are very fast non-cryptographic hash functions like xxHash (in fact, I thought siphash was much faster than 1GB/s, but I could be misremembering).
- wahern 10y agoIn 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.
- aidenn0 10y agoGB/s is a fairly useless metric for hash-functions designed to be used in hash tables. This is because the keys for hash tables are usually very short, and keyed hashes can have long setup times. I don't know the speed of sip-hash for bulk data, but I wouldn't be surprised to see that VMAC is probably faster than siphash for large data, but VMAC has a long setup time (on the order of 5000 cycles IIRC compared to siphash24 at on the order of 100). Heck, for large inputs, python's random hash isn't much faster than hmacmd5, but for 8 byte inputs python's random hash is faster than siphash24. The better measurement is X hashes per second at N key size, and then perform that at a few key sizes. [edit] I finally found a comparison that does this and includes siphash: http://cglab.ca/~abeinges/blah/hash-rs/ http://cglab.ca/~abeinges/blah/hash-rs/ Note that siphash is competitive with everything except FNV for small inputs, but FNV blows it away up to about 60 bytes.
- loeg 10y agoGood point.
- kibwen 10y ago> but for 8 byte inputs python's random hash is faster > than siphash24. For reference, note that Rust recently switched its default hash function from SipHash 2-4 to SipHash 1-3, which should lead to improved performance while retaining the usual flood-resistant properties (at least, that's what the algorithm's creator advised us to do :P ).
- aidenn0 10y agoAlso python adopted siphash in 3.4, due to security concerns around its hash function (see PEP-456).
- Gankro 10y agoThese benchmarks are out of date -- Rust recently updated its SipHash impl from Sip2-4 to Sip1-3, making it actually the fastest for 8-64 bytes in some workloads (looking at the hashers outside of the context of using them in a map gives deceptive results). (I need to get clearance to post updated results)