qd_timer fails to scale efficiently

[kgiusti]

The current qd_timer module does not perform well as the number of timers scale.

The primary issue is that the running timers are stored in an sorted linked list. The next timer to expire (shortest time offset) is maintained at the head of the list.

Scheduling a timer involves an O(n/2) scan and sort of the timer list. Adding long-timeout timers result in the pathological case where the entire list is scanned only to insert the timer at the end of the list.

To exacerbate the CPU load the timers use an "offset from previous timer" implementation (rather than a simple deadline timestamp) which requires an additional scan to update the offsets of all the timers that are "past" the newly scheduled timer.