Date: Mon, 15 May 2017 10:34:10 -0600 From: Alan Somers <asomers@freebsd.org> To: Jens Stimpfle <jfs@jstimpfle.de> Cc: "freebsd-hackers@freebsd.org" <freebsd-hackers@freebsd.org> Subject: Re: Improved Red-black tree implementation Message-ID: <CAOtMX2iU7kYsrROhwn2j78VKj2iTW08DhE8H0j1aSEKtRE29cQ@mail.gmail.com> In-Reply-To: <20170514050220.GA768@jstimpfle.de> References: <20170514050220.GA768@jstimpfle.de>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sat, May 13, 2017 at 11:02 PM, Jens Stimpfle <jfs@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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAOtMX2iU7kYsrROhwn2j78VKj2iTW08DhE8H0j1aSEKtRE29cQ>