Improved Red-black tree implementation

[Alan Somers]

On Sat, May 13, 2017 at 11:02 PM, Jens Stimpfle <jfs at jstimpfle.de> wrote:
> Hello,
>
> the BSD tree.h Red-black tree implementation has a design issue in that
> it doesn't share code between generated instances. Each instanciated
> tree costs about 3K of machine code (on amd64). Making multiple
> instances means increased pressure on the instruction cache (often 64K
> these days).
>
> In the last weeks I've designed a very efficient implementation that
> shares most of the machine code between all instances. There are macros
> for type safety equivalent to tree.h's, but they are only thin wrappers
> around the generic code. The implementation is about 15% faster than
> tree.h on my benchmark.
>
> It is quite similar in overall design (e.g. intrusively linked, no
> memory allocation). A notable difference is that color information is
> stored in the low child pointer bits, which might trouble some people,
> but it saves memory. It includes a shim for the tree.h API. A few
> touches are still missing, but it can probably work as drop-in
> replacement for most client code.
>
> Furthermore it allows for more flexible usage, for example search
> functions that receive additional context besides a search key.
>
> The code is currently at
> https://github.com/jstimpfle/sil/tree/master/rb3ptr
>
> Could FreeBSD profit from this improved implementation? I can adapt
> future development to simplify integration into the tree.
>
> Jens Stimpfle

Nice work, Jens.  This certainly sounds like an improvement.  A few questions:
1) Are there any automated tests?  I would definitely want robust
coverage for something this complicated.
2) FreeBSD can't rely on any Python code during the build.  Does
gen-macros.py need to be run on every build?  Or is it more like
autoreconf, something that gets run when a developer modifies the RB
code, and then checks in its output?
3) Do you know of any examples of programs that use multiple instances
of RB trees?

-Alan