Sounds interesting.

>From what source do you expect the huge number of callouts at once that
justify this kind of structure, i.e what application or application mix?

later,
Adam

>----------
>From: 	Charles M. Hannum[SMTP:mycroft@mit.edu]
>Sent: 	Wednesday, July 17, 1996 2:36 PM
>To: 	tech-kern@NetBSD.ORG
>Subject: 	Efficient callout handling
>
>
>It's been brought to my attention that more efficient callout handling
>would be beneficial, not only for the current uses of callouts, but
>even more so in cases where it might be preferrable to have a *huge*
>number of callouts at once.
>
>One idea (from Greg) for implementing a more efficient callout
>mechanism would be to store the entries in a heap.  This is an
>interesting suggestion, and I explored it a bit today.  As it turns
>out, though, it is actually difficult to implement a heap efficiently
>in the kernel without some perverse hacks to the data structure.  By
>the time you're done, it really doesn't look much better than a
>balanced binary tree.  Also, insertions and deletions are still O(log
>N), and it's arguable that one can do better.
>
>I have, therefore, devised a different (and possibly more perverse
>B-)) mechanism for keeping track of callouts.  It results in something
>approximating O(1) insertion, deletion, and lookup time.
>
>The idea is to use a sort of radix tree, but with a twist.  You have
>HZ lists of callouts to execute within the current second, (say) 60
>lists of callouts to execute within the next 60 seconds, 60 lists
>divided by minute, 24 lists divided by hour, N lists divided by day.
>When a particular point rolls over, you promote and resort the current
>list at the appropriate levels up 1 slot.
>
>In addition, rather than the current method of allocating callout
>structures, you either allocate them separately, or allocate them
>dynamically within the timeout() routine.  Like the original BCI
>interface, untimeout() then takes a cookie that was returned by
>timeout() to delete the callout, and does so in O(1) time.  This is
>trivial to do, for example, by implementing the above-mentioned lists
>as TAILQs or something similar.
>
>The overall time used for any given callout (whether deleted or
>executed) is thus O(log T), where T is the distance into the future.
>Since T is (especially when you include things like TCP timers) almost
>always <= 60 seconds, this means that the constant factor is actually
>fairly small.
>
>
>Does anyone have suggestions on further refinements to this, or
>perhaps better ways of doing it?
>
>