5 ms·

Tree.h in OpenBSD: dependency-free intrusive binary tree (2002)

rurban 6y ago
And? rb and splay tree, not particularly fast. Normally you would use a btree, just when you need pointer and iterator stability you'd need these slower pointer chasing ones. This is not even documented.
- deleted 6y ago
  [deleted]
- JoachimSchipper 6y ago
  tree.h is production-proven and available under a very liberal license (ISC). tree.h is also fairly extensively documented (e.g. https://man.openbsd.org/tree.3); https://man.openbsd.org/tree.3); the only real footgun the API allows is documented under "NOTES". You are, of course, right that pointer-heavy data structures do not perform optimally on modern hardware. But I've still reached for tree.h quite a few times, because it gives you a very flexible data structure that Just Works with little fuss and minimal dependencies.
  - Datagenerator 6y ago
    The link needs some TLC
    - brohee 6y ago
      https://man.openbsd.org/tree.3 https://man.openbsd.org/tree.3
MarkSweep 6y ago
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...
_delirium 6y ago
For the curious: The author of this, Niels Provos, is now the head of security at Stripe. He wrote it when he was a PhD student at the University of Michigan.
- jcims 6y ago
  I had the pleasure of meeting Niels during a short stint at Google. Didn’t help my imposter syndrome xD.
lflux 6y ago
The URL and (2002) make it seem like it hasn't be updated since, but the latest commit to it is from october. These macros, along with the list/queue macros in queue.h are super useful. I've inclduded them in several projects and it's super simple to just drop in the header file since it's BSD licensed
gorgoiler 6y ago
Why is the code written using defines? I haven’t read much C and I’ve never seen C written this way before.
- branko_d 6y ago
  Looks like they are emulating generics (what would be accomplished with templates in C++).
  - wahern 6y ago
    tree.h implements intrusive data structures using code generation. Even in C++, to support an object being in multiple containers intrusively the templates get quite complex because you need to parameterize on the member field name. Some older implementation simply fallback to external code generation, including use of macros. C application code using these data structures, particularly of the finely honed interfaces defined by queue.h and tree.h in BSD, tend to be extremely clear and simple. And at least the implementation of intrusive lists, particularly queue.h, is also quite straightforward, even considering the backslash-escaped multiline macros. (tree.h is admittedly hairier, but it's implementing an intrusive, non-recursive, type-safe red-black tree. Multiline macros are the least of your problems.) None of the C-like languages make this easy at the type level. I'm not familiar with any statically-typed functional languages; but I doubt it's any easier because intrusive, inside-out struct/record object relations tend to be even more foreign. By resorting to rudimentary string interpolation (i.e. C macros), it's counter intuitively quite easy to implement this stuff in C. I suppose it's also easier in s-expression based languages, but s-expressions lend themselves to dynamic code generation.
  - eqvinox 6y ago
    This is indeed one of the two ways to get "generics" in C. The other way is to set up a set of #defines before #including a file, so the #defines rename everything in the include. (The include can also be included multiple times in this pattern.) The latter seems to be more rare.
    - kevin_thibedeau 6y ago
voodoochilo 6y ago
Why use a C compiler if you can use a preprocessor. Jesus!
eqvinox 6y ago
Typesafe wrapper around the same code: https://github.com/FRRouting/frr/blob/master/lib/typerb.h https://github.com/FRRouting/frr/blob/master/lib/typerb.h https://github.com/FRRouting/frr/blob/master/lib/typerb.c https://github.com/FRRouting/frr/blob/master/lib/typerb.c Typesafe wrapper with identical API around linked lists, heap & hash: https://github.com/FRRouting/frr/blob/master/lib/typesafe.h https://github.com/FRRouting/frr/blob/master/lib/typesafe.h https://github.com/FRRouting/frr/blob/master/lib/typesafe.c https://github.com/FRRouting/frr/blob/master/lib/typesafe.c Docs: http://docs.frrouting.org/projects/dev-guide/en/latest/lists.html http://docs.frrouting.org/projects/dev-guide/en/latest/lists... Typesafe = each tree/list/... uses its own struct and the APIs directly use pointers to the actual member data structures rather than the tree implementation structs. Disclaimer: I wrote these (only the wrapper in case of the RB tree, the entire thing for the others)
butterisgood 6y ago
But is it cache-friendly? Linked structures are great and all, but it seems that nowadays even in-memory B-trees might be better than overly-linked structures for the same reasons B-trees were efficient for on-disk storage (less moving around = better locality). I suppose some cache-friendliness may also come from the chosen memory allocator for allocating new nodes. If objects are all the same size, a reasonably good slab allocator might continue to provide cache-friendliness. I think I need an adult! Can someone help me sort this out?
- attractivechaos 6y ago
  In-memory B-tree is faster and uses less memory for small keys [1]. However, intrusive binary search trees (BSTs) are much more flexible and are the right choice for implementing kernels and malloc(). In addition, intrusive BSTs are often used to organize memory blocks scattered around. In-memory B-tree would lose its cache-efficiency in this case anyway. [1] https://attractivechaos.wordpress.com/2008/09/24/b-tree-vs-binary-search-tree/ https://attractivechaos.wordpress.com/2008/09/24/b-tree-vs-b...
- louai 6y ago
  A characteristic of intrusive data structures is generally good cache friendliness. In this context "intrusive" means that the data structure is embedded with the data that's being stores. In C terms as in this case that means that the pointers required of individual nodes aren't allocated in separate structs and are instead embedded in one struct that also includes the payload. This means that the cache behavior is improved, as a given node is stored in a single location. Once you access a node the associated data is already in the cache, instead of having to be fetched via a separate pointer dereference.
- loeg 6y ago
  Not especially cache efficient compared to trees with higher branching factor, true. But intrusive data structures can be manipulated without memory allocation, such as when holding locks. That is the main reason they are useful in place of B-trees.
huhtenberg 6y ago
Beware of splay trees being modified on read access. Meaning that in a threaded environment merely traversing or searching the tree will cause hidden performance issues due to the cache invalidation. Issues that don't exist with other balanced tree types. That is, splay trees are a distinctly specialized binary tree type. Use with due care.
McGlockenshire 6y ago
My C skills aren't particularly great. I can't identify the syntax of "name##" in the macros and function definitions. Can someone tell me what this is called?
- huhtenberg 6y ago
  https://gcc.gnu.org/onlinedocs/cpp/Concatenation.html https://gcc.gnu.org/onlinedocs/cpp/Concatenation.html
haolez 6y ago
I had forgotten how much I like C an admire its combination of simplicity and expressivity. Thanks for reminding me :)
codr7 6y ago
I have a fairly comprehensible left leaning rb tree implementation that I've been porting along my travels. I keep it around for situations where a binary searched array isn't doable or good enough, but I still want ordered set functionality that isn't in the stdlib. https://github.com/codr7/whirlog/blob/main/rb.lisp https://github.com/codr7/whirlog/blob/main/rb.lisp https://github.com/codr7/libcodr7/blob/master/source/codr7/tree_node.c https://github.com/codr7/libcodr7/blob/master/source/codr7/t...
loeg 6y ago
Related, maybe interesting to this crowd: In FreeBSD, the RB tree implementation has been replaced with a "weak AVL" tree implementation: https://github.com/freebsd/freebsd-src/commit/504ba65c8c9f7a3bf25303ff539f6432b9c76848 https://github.com/freebsd/freebsd-src/commit/504ba65c8c9f7a... > Weak AVL (Wavl) trees sit between AVL and red-black trees in terms of how strictly balance is enforced. They have the stricter balance of AVL trees as the tree is built - a wavl tree is an AVL tree until the first deletion. Once removals start, wavl trees are lazier about rebalancing than AVL trees, so that removals can be fast, but the balance of the tree can decay to that of a red-black tree. Subsequent insertions can push balance back toward the stricter AVL conditions. > ... > Testing has shown that for the cases where red-black trees do worst, wavl trees better balance leads to faster lookups, so that if lookups outnumber insertions by a nontrivial amount, lookup time saved exceeds the extra cost of balancing.

And? rb and splay tree, not particularly fast. Normally you would use a btree, just when you need pointer and iterator stability you'd need these slower pointer chasing ones. This is not even documented.

deleted 6y ago
[deleted]
JoachimSchipper 6y ago
tree.h is production-proven and available under a very liberal license (ISC). tree.h is also fairly extensively documented (e.g. https://man.openbsd.org/tree.3); https://man.openbsd.org/tree.3); the only real footgun the API allows is documented under "NOTES". You are, of course, right that pointer-heavy data structures do not perform optimally on modern hardware. But I've still reached for tree.h quite a few times, because it gives you a very flexible data structure that Just Works with little fuss and minimal dependencies.
- Datagenerator 6y ago
  The link needs some TLC
  - brohee 6y ago
    https://man.openbsd.org/tree.3 https://man.openbsd.org/tree.3

MarkSweep 6y ago

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...

_delirium 6y ago

For the curious: The author of this, Niels Provos, is now the head of security at Stripe. He wrote it when he was a PhD student at the University of Michigan.

jcims 6y ago
I had the pleasure of meeting Niels during a short stint at Google. Didn’t help my imposter syndrome xD.

lflux 6y ago

The URL and (2002) make it seem like it hasn't be updated since, but the latest commit to it is from october. These macros, along with the list/queue macros in queue.h are super useful. I've inclduded them in several projects and it's super simple to just drop in the header file since it's BSD licensed

gorgoiler 6y ago

Why is the code written using defines? I haven’t read much C and I’ve never seen C written this way before.

branko_d 6y ago
Looks like they are emulating generics (what would be accomplished with templates in C++).
- wahern 6y ago
  tree.h implements intrusive data structures using code generation. Even in C++, to support an object being in multiple containers intrusively the templates get quite complex because you need to parameterize on the member field name. Some older implementation simply fallback to external code generation, including use of macros. C application code using these data structures, particularly of the finely honed interfaces defined by queue.h and tree.h in BSD, tend to be extremely clear and simple. And at least the implementation of intrusive lists, particularly queue.h, is also quite straightforward, even considering the backslash-escaped multiline macros. (tree.h is admittedly hairier, but it's implementing an intrusive, non-recursive, type-safe red-black tree. Multiline macros are the least of your problems.) None of the C-like languages make this easy at the type level. I'm not familiar with any statically-typed functional languages; but I doubt it's any easier because intrusive, inside-out struct/record object relations tend to be even more foreign. By resorting to rudimentary string interpolation (i.e. C macros), it's counter intuitively quite easy to implement this stuff in C. I suppose it's also easier in s-expression based languages, but s-expressions lend themselves to dynamic code generation.
- eqvinox 6y ago
  This is indeed one of the two ways to get "generics" in C. The other way is to set up a set of #defines before #including a file, so the #defines rename everything in the include. (The include can also be included multiple times in this pattern.) The latter seems to be more rare.
  - kevin_thibedeau 6y ago

voodoochilo 6y ago

Why use a C compiler if you can use a preprocessor. Jesus!

eqvinox 6y ago

Typesafe wrapper around the same code: https://github.com/FRRouting/frr/blob/master/lib/typerb.h https://github.com/FRRouting/frr/blob/master/lib/typerb.h https://github.com/FRRouting/frr/blob/master/lib/typerb.c https://github.com/FRRouting/frr/blob/master/lib/typerb.c Typesafe wrapper with identical API around linked lists, heap & hash: https://github.com/FRRouting/frr/blob/master/lib/typesafe.h https://github.com/FRRouting/frr/blob/master/lib/typesafe.h https://github.com/FRRouting/frr/blob/master/lib/typesafe.c https://github.com/FRRouting/frr/blob/master/lib/typesafe.c Docs: http://docs.frrouting.org/projects/dev-guide/en/latest/lists.html http://docs.frrouting.org/projects/dev-guide/en/latest/lists... Typesafe = each tree/list/... uses its own struct and the APIs directly use pointers to the actual member data structures rather than the tree implementation structs. Disclaimer: I wrote these (only the wrapper in case of the RB tree, the entire thing for the others)

butterisgood 6y ago

But is it cache-friendly? Linked structures are great and all, but it seems that nowadays even in-memory B-trees might be better than overly-linked structures for the same reasons B-trees were efficient for on-disk storage (less moving around = better locality). I suppose some cache-friendliness may also come from the chosen memory allocator for allocating new nodes. If objects are all the same size, a reasonably good slab allocator might continue to provide cache-friendliness. I think I need an adult! Can someone help me sort this out?

attractivechaos 6y ago
In-memory B-tree is faster and uses less memory for small keys [1]. However, intrusive binary search trees (BSTs) are much more flexible and are the right choice for implementing kernels and malloc(). In addition, intrusive BSTs are often used to organize memory blocks scattered around. In-memory B-tree would lose its cache-efficiency in this case anyway. [1] https://attractivechaos.wordpress.com/2008/09/24/b-tree-vs-binary-search-tree/ https://attractivechaos.wordpress.com/2008/09/24/b-tree-vs-b...
louai 6y ago
A characteristic of intrusive data structures is generally good cache friendliness. In this context "intrusive" means that the data structure is embedded with the data that's being stores. In C terms as in this case that means that the pointers required of individual nodes aren't allocated in separate structs and are instead embedded in one struct that also includes the payload. This means that the cache behavior is improved, as a given node is stored in a single location. Once you access a node the associated data is already in the cache, instead of having to be fetched via a separate pointer dereference.
loeg 6y ago
Not especially cache efficient compared to trees with higher branching factor, true. But intrusive data structures can be manipulated without memory allocation, such as when holding locks. That is the main reason they are useful in place of B-trees.

huhtenberg 6y ago

Beware of splay trees being modified on read access. Meaning that in a threaded environment merely traversing or searching the tree will cause hidden performance issues due to the cache invalidation. Issues that don't exist with other balanced tree types. That is, splay trees are a distinctly specialized binary tree type. Use with due care.

McGlockenshire 6y ago

My C skills aren't particularly great. I can't identify the syntax of "name##" in the macros and function definitions. Can someone tell me what this is called?

huhtenberg 6y ago
https://gcc.gnu.org/onlinedocs/cpp/Concatenation.html https://gcc.gnu.org/onlinedocs/cpp/Concatenation.html

haolez 6y ago

I had forgotten how much I like C an admire its combination of simplicity and expressivity. Thanks for reminding me :)

codr7 6y ago

I have a fairly comprehensible left leaning rb tree implementation that I've been porting along my travels. I keep it around for situations where a binary searched array isn't doable or good enough, but I still want ordered set functionality that isn't in the stdlib. https://github.com/codr7/whirlog/blob/main/rb.lisp https://github.com/codr7/whirlog/blob/main/rb.lisp https://github.com/codr7/libcodr7/blob/master/source/codr7/tree_node.c https://github.com/codr7/libcodr7/blob/master/source/codr7/t...

loeg 6y ago

Related, maybe interesting to this crowd: In FreeBSD, the RB tree implementation has been replaced with a "weak AVL" tree implementation: https://github.com/freebsd/freebsd-src/commit/504ba65c8c9f7a3bf25303ff539f6432b9c76848 https://github.com/freebsd/freebsd-src/commit/504ba65c8c9f7a... > Weak AVL (Wavl) trees sit between AVL and red-black trees in terms of how strictly balance is enforced. They have the stricter balance of AVL trees as the tree is built - a wavl tree is an AVL tree until the first deletion. Once removals start, wavl trees are lazier about rebalancing than AVL trees, so that removals can be fast, but the balance of the tree can decay to that of a red-black tree. Subsequent insertions can push balance back toward the stricter AVL conditions. > ... > Testing has shown that for the cases where red-black trees do worst, wavl trees better balance leads to faster lookups, so that if lookups outnumber insertions by a nontrivial amount, lookup time saved exceeds the extra cost of balancing.