Date: Tue, 14 Nov 2006 15:46:11 +0000 From: "Poul-Henning Kamp" <phk@phk.freebsd.dk> To: Andre Oppermann <andre@freebsd.org> Cc: arch@freebsd.org Subject: Re: a proposed callout API Message-ID: <11832.1163519171@critter.freebsd.dk> In-Reply-To: Your message of "Tue, 14 Nov 2006 16:38:41 %2B0100." <4559E301.2030607@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
In message <4559E301.2030607@freebsd.org>, Andre Oppermann writes: >Luigi Rizzo wrote: >> On Tue, Nov 14, 2006 at 04:11:20PM +0100, Andre Oppermann wrote: >> ... >>> It's important to know that any random memory accesses on modern >>> CPUs are really expensive because of cache misses. That's why >>> Judy tries beat RB tries by an order of a magnitude these days. >> >> you mean this stuff ? >> >> http://docs.hp.com/en/B6841-90001/ch02s01.html >> http://judy.sourceforge.net/ > >We've used it a number of other projects and it beats everything >else hands down in speed and memory consumption. I would like to thank you all for your enthusiasm in promoting various data structures, but I kindly remind you that the only sorting requirement we have for the short/likely callouts is to know which one is next and that we may have duplicate keys. We are never going to search for a callout that expires in 1402 microseconds or anything of the sort, the basic operations are: add node to tree delete node from tree move node in tree (rescheduling) find earliest callout All of these are welldefined and efficient in binary heaps, which additionally have the advantage of being very space efficient. -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 phk@FreeBSD.ORG | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?11832.1163519171>