Hacker News Reader

Hacker News

Comment by MarkSweep | Hacker News Reader

Full thread

MarkSweep

For comparison, AVL tress are widely used in illumos. There are some nice big doc comments in these files as well.

https://github.com/illumos/illumos-gate/blob/master/usr/src/...

View on HN

It also represents a stable API and ABI, both in the kernel...

https://illumos.org/man/9F/avl

... and in user mode, via libavl:

https://illumos.org/man/3LIB/libavl

Our debugger, MDB, is able to use the offsets and pointers stored in the tree to provide generic walks through any AVL tree in a live system, core file, or crash dump.

The linux kernel also has some nice comments in its red black tree implementation.

https://github.com/torvalds/linux/blob/master/lib/rbtree.c

What you are showing is an implementation without long macros. It is cleaner and simpler. However, it is slower as compilers often can't inline user-provided comparison functions (though modern compilers seem to do a better job). For integers, extra comparison function calls are costly. With tree.h, you can implement the comparison in a macro. Then compilers will automatically inline the comparison. That is the most efficient way to implement generic binary search trees.

I don't think this matters too much. It's the overhead of an added call/return that is hot in the cache and the CPU has enough cycles of twiddling its thumbs while it's grabbing the next tree level from a lower cache or main memory...

You are right. There are lots of more operations in addition to comparisons. Just done a microbenchmark. The difference between macro- and function-based comparisons is largely indistinguishable.

I wonder if anyone did a comprehensive benchmark comparing all of these

There shouldn't be much difference, particularly between the RB and AVL trees. The limiting factor is memory access latency in all cases since the CPU can't effectively prefetch tree node accesses for the next level down.

While both RB and AVL trees grow at O(lg N) height, the constant for AVL trees is smaller. This means that for a large AVL tree it might be 1 or 2 layers shorter than the equivalent RB tree. This comes at the expense of a higher constant for insertion and deletion.

In certain contexts saving a node transversal will have a meaningful impact on performance.

These are the most well known tree types in CS and banchmark results are unlikely to differ from what is widely published and written about the algorithms. Benchmark winner would depend on what usage pattern and metric you are interested in. Binary trees are simple, AVL is a bit faster to search and slower to update than RB.

For whatever it's worth, I did effectively benchmark the illumos AVL implementation against Rust's B-tree implementation[0], though that was certainly not the intent! Benchmarking the relative BSTs would be interesting, but (absent some small cycle count differences in degenerate cases like a single node) one very much expects BST performance to be dominated by memory behavior -- and the memory footprint (and cache behavior) of the relative implementations is much more likely to affect relative performance than other factors. Of course, systems can surprise, so hopefully someone does the experiment!

[0] http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...

Reply on news.ycombinator.com