On Thu, Jan 31, 2013 at 11:06 AM, Edward Z. Yang
Excerpts from Alexander Kjeldaas's message of Thu Jan 31 01:57:17 -0800 2013:
Found it, it's still there:
http://www.cs.fsu.edu/~baker/devices/lxr/http/source/linux/kernel/timer.c?v=...
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.
Ah, I see. GHC threads are very rarely canceled, so I don't think we would see much benefit here.
You are probably right. I can think of priority inversion with rapidly changing priorities as a possible use-case then. Anyways, keep up the good work! Alexander
Edward