a proposed callout API

[Poul-Henning Kamp]

In message <4559E301.2030607 at 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 at 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.