5 ms·

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

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/common/avl/avl.c https://github.com/illumos/illumos-gate/blob/master/usr/src/... https://github.com/illumos/illumos-gate/blob/master/usr/src/uts/common/sys/avl.h https://github.com/illumos/illumos-gate/blob/master/usr/src/...

jclulow 6y ago
It also represents a stable API and ABI, both in the kernel... https://illumos.org/man/9F/avl https://illumos.org/man/9F/avl ... and in user mode, via libavl: https://illumos.org/man/3LIB/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.
uyt 6y ago
I wonder if anyone did a comprehensive benchmark comparing all of these
- eqvinox 6y ago
  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.
  - metric10 6y ago
    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.
- fulafel 6y ago
  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.
- bcantrill 6y ago
  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-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...
keeperofdakeys 6y ago
The linux kernel also has some nice comments in its red black tree implementation. https://github.com/torvalds/linux/blob/master/lib/rbtree.c https://github.com/torvalds/linux/blob/master/lib/rbtree.c
attractivechaos 6y ago
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.
- eqvinox 6y ago
  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...
  - attractivechaos 6y ago
    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.

jclulow 6y ago

It also represents a stable API and ABI, both in the kernel... https://illumos.org/man/9F/avl https://illumos.org/man/9F/avl ... and in user mode, via libavl: https://illumos.org/man/3LIB/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.

uyt 6y ago

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

eqvinox 6y ago
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.
- metric10 6y ago
  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.
fulafel 6y ago
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.
bcantrill 6y ago
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-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...

keeperofdakeys 6y ago

The linux kernel also has some nice comments in its red black tree implementation. https://github.com/torvalds/linux/blob/master/lib/rbtree.c https://github.com/torvalds/linux/blob/master/lib/rbtree.c

attractivechaos 6y ago

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.

eqvinox 6y ago
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...
- attractivechaos 6y ago
  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.