From owner-freebsd-hackers@freebsd.org Sun May 14 05:39:17 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 26497D6C31B for ; Sun, 14 May 2017 05:39:17 +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 E6D4B25C for ; Sun, 14 May 2017 05:39:16 +0000 (UTC) (envelope-from jfs@jstimpfle.de) Received: from jfs by h1929017.stratoserver.net with local (Exim 4.84_2) (envelope-from ) id 1d9lfg-0000E9-Os for freebsd-hackers@freebsd.org; Sun, 14 May 2017 07:02:20 +0200 Date: Sun, 14 May 2017 07:02:20 +0200 From: Jens Stimpfle To: freebsd-hackers@freebsd.org Subject: Improved Red-black tree implementation Message-ID: <20170514050220.GA768@jstimpfle.de> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) X-Mailman-Approved-At: Sun, 14 May 2017 11:17:41 +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: Sun, 14 May 2017 05:39:17 -0000 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