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@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