Re: [dpdk-dev] [PATCH v2 0/3] timer: fix rte_timer_reset

[Robert Sanford <rsanford2@gmail.com>]

On Wed, Feb 25, 2015 at 6:16 AM, Bruce Richardson <
bruce.richardson@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