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> In-Reply-To: <20170514050220.GA768@jstimpfle.de> References: <20170514050220.GA768@jstimpfle.de>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20170522231105.GA24328>