Date: Sat, 20 May 2017 18:53:03 +0200 From: Jens Stimpfle <jfs@jstimpfle.de> To: Sebastian Huber <sebastian.huber@embedded-brains.de>, freebsd-hackers@freebsd.org Subject: Re: Improved Red-black tree implementation Message-ID: <20170520165303.GA22452@jstimpfle.de> In-Reply-To: <591EA74A.3080500@embedded-brains.de> References: <20170514050220.GA768@jstimpfle.de> <591EA74A.3080500@embedded-brains.de>
next in thread | previous in thread | raw e-mail | index | archive | help
On Fri, May 19, 2017 at 10:05:30AM +0200, Sebastian Huber wrote: > I use the BSD <sys/tree.h> for RTEMS with a shared extract and insert color > implementation (this is similar to Linux): > > https://git.rtems.org/rtems/tree/cpukit/score/include/rtems/score/rbtree.h#n206 > https://git.rtems.org/rtems/tree/cpukit/score/src/rbtreeextract.c > https://git.rtems.org/rtems/tree/cpukit/score/src/rbtreeinsert.c > > I did also some primitive benchmarking: > > https://github.com/sebhub/rb-bench Thanks Sebastian, I had actually found you bench already and tested an earlier version of my code. It did quite well on my machine, although I would expect it to be faster than BSD ("SIL RB3"): https://raw.githubusercontent.com/jstimpfle/rb-bench/31f111f9c7664d72d5f103bb46adcb28a1cea61a/reports/test-amdx2250.png The second plot is broken maybe because my machine is too fast for the bench... > It would be quite nice to have a <sys/tree.h> implementation which encodes > the color in one of the pointers to save some memory. I have looked at your project and will send you email off-list. Just a few points here: Considering memory savings, have you considered 2-pointer trees (no parent pointer)? They need a temporary search stack for insertion and deletion, but not for iteration ("threaded trees"). The RTEMS red-black tree API seems to be implemented by removing convenience / type-safety from the BSD API to save memory (no multiple instances compiled). While relatively straightforward, replacing tree.h with rb3ptr's BSD shim here would be a lot of layers on top of rb3ptr's core just to expose something like that core again, in the end. And as advertised in another mail, with minimal use of macros convenience and type-safety can be increased without requiring multiple compilation, probably even saving code size. But that would mean changing all client code to use the wrapper API / BSD shim... Jens
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20170520165303.GA22452>