From owner-freebsd-hackers@freebsd.org Sat May 20 16:53:13 2017 Return-Path: Delivered-To: freebsd-hackers@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 8EF37D76E0B for ; Sat, 20 May 2017 16:53:13 +0000 (UTC) (envelope-from jfs@jstimpfle.de) Received: from h1929017.stratoserver.net (jstimpfle.de [85.214.245.181]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 593F41C07 for ; Sat, 20 May 2017 16:53:12 +0000 (UTC) (envelope-from jfs@jstimpfle.de) Received: from jfs by h1929017.stratoserver.net with local (Exim 4.84_2) (envelope-from ) id 1dC7cl-0005ro-RL; Sat, 20 May 2017 18:53:03 +0200 Date: Sat, 20 May 2017 18:53:03 +0200 From: Jens Stimpfle To: Sebastian Huber , freebsd-hackers@freebsd.org Subject: Re: Improved Red-black tree implementation Message-ID: <20170520165303.GA22452@jstimpfle.de> References: <20170514050220.GA768@jstimpfle.de> <591EA74A.3080500@embedded-brains.de> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <591EA74A.3080500@embedded-brains.de> User-Agent: Mutt/1.5.23 (2014-03-12) X-Mailman-Approved-At: Sun, 21 May 2017 04:09:14 +0000 X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 20 May 2017 16:53:13 -0000 On Fri, May 19, 2017 at 10:05:30AM +0200, Sebastian Huber wrote: > I use the BSD 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 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