A couple questions..

 1) have you collected traces of timeout() usage in existing systems?
(this would seem to be useful in evaluating different datastructures,
and would also be good if you wanted to publish a paper about what you
come up with).

 2) if you're going to change the API to timeout() to pass a timespec,
have you considered also changing it so the caller allocates the
space, typically in-line in one of its data structures?  

I think most or all current usage of timeout is such that this
wouldn't be a problem.

You could then use one of the binary-tree based priority queue methods
in knuth vol 3, section 5.2.3, and would not have to worry about
timeout() ever running out of table space or needing to allocate
memory, which would make timeout-driven code much more robust when
memory is short.  

This also would also speed untimeout(); rather than having to search
the entire callout structure, it would start off with a pointer to the
callout structure to be removed.

One obvious drawback of this scheme would be that up to O(log n) TLB
misses would be possible on each callout, though the same would be
likely for your multi-array heap approach assuming the deeper layers
were allocated on demand..

					- Bill