On Wed, Feb 25, 2015 at 6:16 AM, Bruce Richardson < bruce.richardson at intel.com> wrote:
> On Wed, Feb 25, 2015 at 06:02:24AM -0500, Robert Sanford wrote: > > > > > One question about lib rte_timer that's been troubling me for a while: > How > > are skip lists better than BSD-style timer wheels? > > > > -- > > The skip list may not be any better than a timer wheel - it's just what is > used > now, and it does give pretty good performance (insert O(log n) [up to a few > million timers per core], expiry O(1)). > Originally in DPDK, the timers were maintained in a regular sorted linked > list, > but that suffered from scalability issues when starting timers, or stopped > before > expiry. The skip-list was therefore a big improvement on that, and gave us > much greater scalability in timers, without any regressions in > performance. I > don't know if anyone has tried to implement and benchmark a timer-wheel > based > rte_timer library replacement. I'd be interested to see a performance > comparison > between the two implementations! :-) > > Regards, > /Bruce > > I've wanted to try out the timer-wheels since before the skip-list version, but it just hasn't made it to the top of my priority list. The other thing that concerns me about the skip-list implementation is the extra cache line that all those pointers consume. -- Thanks, Robert
