> Anders Magnusson writes:
> > > > The callout code under BSD has always been, uh, 
> > > > less than optimal.  Since it is O(n) on operations
> > > > it really sucks on slow processors (VAX, i386, etc.)
> > > 
> > > I'm pretty sure FreeBSD has solved this quite some time ago, don't know if
> > > they used the stuff referenced here. Maybe we should take a look there
> > > first...
> 
> > Yes, FreeBSD uses Varghese's callout stuff since loong time ago. 
> > Probably simplest to get it from there.
> 
> The question is who is going to get it. I'm personally not qualified
> to do the work, or I would volunteer.

Be aware that the freebsd version of this changed the API to timeout()
to return a handle, and untimeout() to take the handle as an argument,
kind of like the SVR4 timeout().  This has some advantages, as it makes
untimeout() a bit faster and eliminates the memory and operations that
would otherwise be needed to maintain an untimeout() hash table, but
changes this from a small hack in kern_clock.c to a big hack that requires
modifications to every caller of untimeout().

There are also other ways at this that have slightly different tradeoffs.
The callwheel code makes timeout() and untimeout() constant time, but
does so at the cost of perhaps calling setsoftclock() more often than it 
strictly needs to and by maybe adding O(n) operations to setsoftclock() to
find guys who have timed out (though the O(n) should have a very small constant
of proportionality, i.e. it is O(n) quite simple operations spread out over
time).  Another way at this is to use a conventional heap, which makes
all operations O(log(n)) while avoiding unnecessary calls to setsoftclock()
and which requires less memory so the callout structure doesn't bloat quite
as badly when the hash pointers are added.  I could contribute code for the
latter if there were interest in keeping the API to (un)timeout() the
same as it is now (not that I necessarily have a strong opinion about
keeping the current API; there is merit in using the handle for untimeout()).

In any case, the code that is there now truly sucks if you have more
than a few active callouts.

Dennis Ferguson