Date: Mon, 15 May 2017 22:10:35 +0200 From: Jens Stimpfle <jfs@jstimpfle.de> To: freebsd-hackers@freebsd.org Subject: Re: Improved Red-black tree implementation Message-ID: <20170515201035.GA6853@jstimpfle.de> In-Reply-To: <CAOtMX2iU7kYsrROhwn2j78VKj2iTW08DhE8H0j1aSEKtRE29cQ@mail.gmail.com> References: <20170514050220.GA768@jstimpfle.de> <CAOtMX2iU7kYsrROhwn2j78VKj2iTW08DhE8H0j1aSEKtRE29cQ@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Mon, May 15, 2017 at 10:34:10AM -0600, Alan Somers wrote: > 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. So far there is only the benchmark code, one directory level up. If there's use for it that would be motivation for me to work on packaging, also including automated tests and documentation. > 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? More like autoreconf. The output of gen-macros.py is something like tree.h. > 3) Do you know of any examples of programs that use multiple instances > of RB trees? Tmux has 14 instances. I have no idea if the saved code matters in any practical application. It could be rare that more than two instances or so are active at the same time *and* the size of the client code is not dominating. But if anything, code sharing is "the right thing". Digression: I figure most algorithmic implementations could be generic. Even if many data structures need a "stride" parameter. Are there case where it's clearly better to duplicate code for some data structure whose instances are only differing by integer parameters? For functions parameters, there is the famous example of std::sort being faster than qsort, but that must be about the most extreme one: On flat arrays function call overhead dominates cache miss overhead to the point where it sometimes makes sense to inline the function call. Jens
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20170515201035.GA6853>