Re: [patch 2/7] timer: Remove FIFO guarantee

["George Spelvin" <linux@horizon.com>]

Right, so while pairing (and fibonacci) heaps have O(log n) deletion, if
you can delay heapification you can equally delay that extra cost.

> But as you say, the heapification is a O(n) hit, which is not too
> different from our current 'problem'.

> But yes, interesting problem space this.

It definitely gets my mind going.

The issue that's occupying my thoughts right now is this...

Given a "sublist" for a range of future times, the minimum time
can be either a real timeout or a fake one.

If it's a real one, there's a chance you might delete the minimum timeout
on the list.  you have to handle re-sorting after deletion to maintain
a valid minimum time.

You can have a fake list head, which avoids ever re-sorting, but you're
bascially forcing a "tick": taking a timer interrupt at that time even
though nothing needs it.


One possibility that occurs to me would be to have fake heads on the
sublists, but recognize them when they get selected as the "next timeout".
If that happens, deletemin() them now from the remaining heap and find
next *real* timeout.

Basically, just like the current wheel, you'd have to do some scanning
past possibly-empty sublists, but perhaps by using a much more efficient
heap structure, the sublists could be made larger, so not as many heads
would be needed.


Radix sort isn't really O(n); it's O(n log N) with a small constant,
where N is the range of *possible* values (e.g. N = 2^32, so
log N = 32).  But if you want high-resolution timers, N goes
up a lot.