a proposed callout API

[Luigi Rizzo]

On Mon, Nov 13, 2006 at 09:38:21PM +0000, Poul-Henning Kamp wrote:
> In message <20061113133236.A28926 at xorpc.icir.org>, Luigi Rizzo writes:
> >On Mon, Nov 13, 2006 at 08:53:41PM +0000, Poul-Henning Kamp wrote:
> >> 
> 
> >i am a bit curious on why  you want to split the callouts among
> >multiple data structures.
> 
> A binary heap is optimal for the timeouts that will happen, but
> filling it up with timeouts that are unlikely to, and in most
> cases won't happen for a very long time will soak up CPU
> time used for pointlessly ordering the heap.

that's only one side - you are still paying, on each entry,
the cost of the periodic scanning of the list, and the cpu burstiness
of these scanning operations is harmful for system with
pseudo-real-time requirements (and the workarounds complicate
operations).

To make a proper evaluation i would need some idea of the number
and distribution of scheduled events on a busy box, and of the
frequency of insertion/removals, which i don't know.
But just to make an example, say you have a total of 1000
insertions/deletions per second, 64k total events.

Using a single heap, that's 16k operations per second (log64k=16
is the cost of each insert/remove).
Using a small 1k heap (log1k=10 is the cost of each operation),
scanning the list once per second gives you 64k operations per second.
plus add the heap manipulation (but maybe that's in the noise, if,
say, only 10% of the insert-remove go there).

Sure if you make sure the short-term list has very few entries
the scanning costs go down, but how much really depends on your stats.

Note, i am not opposed to separating the heaps, i fully buy your
arguments on reducing the rescheduling costs and the representation
of the intervals on a smaller number of bits.  However, i would try
to use a more efficient data structure for the long-term entries,
eg. another heap with coarser (say 1s) granularity.
You can insert fake events for the first 100..1000 seconds
and have a small array of pointers for access pointers to
those entries, so inserting/rescheduling an event within the
next 100..1000 seconds window is O(1), and when the next event
fires (basically in the next second) you just have to move
a sublist to the main heap, without having to touch all the
other entries.

cheers
luigi