From owner-freebsd-hackers@freebsd.org  Mon May 22 23:11:10 2017
Return-Path: <owner-freebsd-hackers@freebsd.org>
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 5079CD79B12
 for <freebsd-hackers@mailman.ysv.freebsd.org>;
 Mon, 22 May 2017 23:11:10 +0000 (UTC) (envelope-from joerg@bec.de)
Received: from relay4-d.mail.gandi.net (relay4-d.mail.gandi.net
 [IPv6:2001:4b98:c:538::196])
 (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
 (Client did not present a certificate)
 by mx1.freebsd.org (Postfix) with ESMTPS id 1FB191964
 for <freebsd-hackers@freebsd.org>; Mon, 22 May 2017 23:11:09 +0000 (UTC)
 (envelope-from joerg@bec.de)
Received: from britannica.bec.de
 (p200300D2ABDFC310EEF4BBFFFE2CB4D9.dip0.t-ipconnect.de
 [IPv6:2003:d2:abdf:c310:eef4:bbff:fe2c:b4d9])
 (Authenticated sender: joerg@bec.de)
 by relay4-d.mail.gandi.net (Postfix) with ESMTPSA id 8244D172093
 for <freebsd-hackers@freebsd.org>; Tue, 23 May 2017 01:11:07 +0200 (CEST)
Date: Tue, 23 May 2017 01:11:05 +0200
From: Joerg Sonnenberger <joerg@bec.de>
To: freebsd-hackers@freebsd.org
Subject: Re: Improved Red-black tree implementation
Message-ID: <20170522231105.GA24328@britannica.bec.de>
Mail-Followup-To: freebsd-hackers@freebsd.org
References: <20170514050220.GA768@jstimpfle.de>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20170514050220.GA768@jstimpfle.de>
User-Agent: Mutt/1.7.1 (2016-10-04)
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.23
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
 <freebsd-hackers.freebsd.org>
List-Unsubscribe: <https://lists.freebsd.org/mailman/options/freebsd-hackers>, 
 <mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers/>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <https://lists.freebsd.org/mailman/listinfo/freebsd-hackers>, 
 <mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Mon, 22 May 2017 23:11:10 -0000

On Sun, May 14, 2017 at 07:02:20AM +0200, Jens Stimpfle wrote:
> 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).

NetBSD at least has created sys/rbtree.h and matching code in
src/common/lib/libc/gen/rb.c ages ago.

Joerg