From owner-freebsd-hackers@freebsd.org Mon May 15 16:34:12 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 6D99BD6ECB8 for ; Mon, 15 May 2017 16:34:12 +0000 (UTC) (envelope-from asomers@gmail.com) Received: from mail-yw0-x22f.google.com (mail-yw0-x22f.google.com [IPv6:2607:f8b0:4002:c05::22f]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 23064137F for ; Mon, 15 May 2017 16:34:12 +0000 (UTC) (envelope-from asomers@gmail.com) Received: by mail-yw0-x22f.google.com with SMTP id l14so40427383ywk.1 for ; Mon, 15 May 2017 09:34:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=lGs62v///MRtIqoGt8fKJqVH59M+dNJsKUM6Ff9x4YI=; b=BUL9NeFsGMlmHTUGrzKJZORdf4bQEGWUZ0znI/AUbE+ToKWxAkq0kEDq/zu8b5kboI ZC34nKj5e3HeDWquvxJ3dlVYV1WO94oUfZ8PxaGpDNjuksMdk3jeY5wMwovvcp5bD++y AAi+e4n/jX8GuBqCGl1MlMbCGHZGhcPKhP//H5Pq794SUUbHPfx5px1kKaJ4kbi9nACW mbzocPhywArVZaqhRKlutKdm8bAxlIY4NpfsnVyy0bBj7hh2DI34DegWkh0fzqvIn6Oo DEQ9S5I2s2r7YItcp2pkfGsVcNs9QKF0UBEM6rGtdk+58OQQjy505FoLRN/YiarRAWmG t80Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=lGs62v///MRtIqoGt8fKJqVH59M+dNJsKUM6Ff9x4YI=; b=QVIEV1aFEl8txFtAlt9LBvUAVw2biDb4p++hhZJTseS0js6x/xaYLvJnROlHEUpc4q cueZkYV09HSwdXRBC4Obt9DzMWRtbDuh6ma9bDXBlbTY8/0xsVjzZEm7b6SeluXshV8y pGzOJxeZV0tzQSWcqPO0zXNPwKJHfK69qu59L1QErkqSfD4Ujli7tkm0OhrRYEAVWCCt 6zHb9GTozcyLYktSkB8gKrLpwziMyu33/0DoxfD4f3gqRz/9q9auEBM7kqD8krcAsJbY N0xYgRxub7VvhVNQ1noELwDfs3TjrAba9RVDNMPKy/ALcKcZR4ed/YjMdm8f2I2FkFm5 X6nQ== X-Gm-Message-State: AODbwcDCFtAHd9iJ0z9lL32m6y4CgxcXvur2QVubuGV51/rEeLixa1WI ivkVyP7zzfJYEO9grQ1wtUZEmjrMHA== X-Received: by 10.13.228.199 with SMTP id n190mr5656078ywe.279.1494866051215; Mon, 15 May 2017 09:34:11 -0700 (PDT) MIME-Version: 1.0 Sender: asomers@gmail.com Received: by 10.129.20.214 with HTTP; Mon, 15 May 2017 09:34:10 -0700 (PDT) In-Reply-To: <20170514050220.GA768@jstimpfle.de> References: <20170514050220.GA768@jstimpfle.de> From: Alan Somers Date: Mon, 15 May 2017 10:34:10 -0600 X-Google-Sender-Auth: qa3NHFxMh4YddxKqfo3BlehKgUU Message-ID: Subject: Re: Improved Red-black tree implementation To: Jens Stimpfle Cc: "freebsd-hackers@freebsd.org" Content-Type: text/plain; charset="UTF-8" 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: Mon, 15 May 2017 16:34:12 -0000 On Sat, May 13, 2017 at 11:02 PM, Jens Stimpfle 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