From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-la0-f52.google.com (mail-la0-f52.google.com [209.85.215.52]) by dpdk.org (Postfix) with ESMTP id 7E5A79A8D for ; Wed, 25 Feb 2015 14:34:57 +0100 (CET) Received: by labhs14 with SMTP id hs14so3897855lab.1 for ; Wed, 25 Feb 2015 05:34:57 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=pUM5p2bc7t7Q7EjKjJux6hE6GYEehXkkTKbx4amT/aE=; b=VdTLS6sRC2G3jNzpUTf2z7RGNxhrqLVYSsWv8IVvqKQFKn3GorsQWzdvz34f99KGdo WEbhKbz0aGOxaR4JUewT6jcdPFpBuP7llp60/nFwh+W4N+g6YCmSuMn29I63WyRSKOvE hm7yKBgfuZ543BVzGtB3j2yuG7p+rVntyMmUu7FV46PJf36HCIcSZgHcBonXT8yPpeG7 ksaPyzBtzZzJeyCPMtQRXioQk9DLbo2MCiiDkf14SB7y2AyX5DKQ6KHguyGPx76odtTI KLBJBpVx6yJZbOycj1AOZCon7AX1+eLu580B8npB2v+sx1NKmt6P/ADhJimX0ShL6VNR I9mA== MIME-Version: 1.0 X-Received: by 10.152.205.41 with SMTP id ld9mr1994284lac.98.1424871297215; Wed, 25 Feb 2015 05:34:57 -0800 (PST) Received: by 10.114.160.231 with HTTP; Wed, 25 Feb 2015 05:34:57 -0800 (PST) In-Reply-To: <20150225111643.GC4896@bricha3-MOBL3> References: <1422996127-64370-1-git-send-email-rsanford2@gmail.com> <1424837389-56276-1-git-send-email-rsanford2@gmail.com> <54ED8EC1.3030108@6wind.com> <1519667.hoeNh6GYxK@xps13> <20150225111643.GC4896@bricha3-MOBL3> Date: Wed, 25 Feb 2015 08:34:57 -0500 Message-ID: From: Robert Sanford To: Bruce Richardson Content-Type: text/plain; charset=UTF-8 X-Content-Filtered-By: Mailman/MimeDel 2.1.15 Cc: "dev@dpdk.org" Subject: Re: [dpdk-dev] [PATCH v2 0/3] timer: fix rte_timer_reset X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 25 Feb 2015 13:34:57 -0000 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