Code review, new scheduler:

[Alexander Kjeldaas]

Found it, it's still there:
http://www.cs.fsu.edu/~baker/devices/lxr/http/source/linux/kernel/timer.c?v=2.6.25.8#L255

Note that these are *timers*.  Timers are often set up and then canceled.
 As you see, the buckets are not sorted, timers are just put at the end of
a list, and the lists are even hard-coded so they are more general than
log2 buckets.

The point of this is to partially sort the timers as they get closer to
expiration.  Thus you don't pay the full sorting cost if the timer is
modified before it expires.

Alexander

On Thu, Jan 31, 2013 at 10:50 AM, Edward Z. Yang <ezyang at mit.edu> wrote:

> Excerpts from Alexander Kjeldaas's message of Thu Jan 31 01:43:51 -0800
> 2013:
> > What operations do you mostly do in the priority queue?
>
> Insert, removeEmpty, and the occasional delete.
>
> > I'd like to point you to the timer implementation that we did in the
> linux
> > kernel ages ago.  It is basically a set of log2 slots where each slot
> > contains timers for time [2^i..2^(i+1)>.  The dlinked lists make it O(1)
> to
> > remove, change, or add a timer.  The timer interrupt basically "eats"
> > linked lists, and when empty "splats" the first free slot out over the
> > upper slots (which is O(n) worst case).  The structure is simple and
> > optimized for doing a lot of mutation of the timers.  It beats a heap
> hands
> > down in the kernel at least.
>
> Interesting! That sounds simple enough to merit an implementation. However,
> I'm given to understand that the current kernel scheduler uses a red-black
> tree? (I also have an implementation of one of those, though it's based
> off of
> jemalloc's implementation.)
>
> Edward
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20130131/83de9ec8/attachment.htm>