Date: Sun, 14 May 2017 07:02:20 +0200 From: Jens Stimpfle <jfs@jstimpfle.de> To: freebsd-hackers@freebsd.org Subject: Improved Red-black tree implementation Message-ID: <20170514050220.GA768@jstimpfle.de>
next in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20170514050220.GA768>