lkml.org 
[lkml]   [2015]   [Jun]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [patch 2/7] timer: Remove FIFO guarantee
On Tue, 9 Jun 2015, George Spelvin wrote:
> Thomas Gleixner wrote:
>
> > After thinking more about it, I'm even more sure that any code which
> > relies on the FIFO "guarantee" is broken today.
>
> Indeed, I am completely convinced. All I might request is a reassignment
> of blame in the commit message.

Will do. Thanks for spotting it!

> Thank you for your comments on my other blue-sky ideas, too.
>
> I need to look into why we're using wheels, and what the point is.
> How much of an advantage do they have over an efficient priority queue
> like a pairing heap?

The only reason is performance. The wheel has O(1) insertion and
deletion time while heaps and trees usually have O(log(n)).

Timer wheel timers are usually timeouts and 99% of them are canceled
before expiry. Networking is probably the heaviest use case followed
by disk I/O.

Thanks,

tglx






\
 
 \ /
  Last update: 2015-06-09 10:21    [W:0.154 / U:0.148 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site