From: Peter Zijlstra <peterz@infradead.org>
To: George Spelvin <linux@horizon.com>
Cc: tglx@linutronix.de, linux-kernel@vger.kernel.org,
viresh.kumar@linaro.org
Subject: Re: [patch 2/7] timer: Remove FIFO guarantee
Date: Tue, 9 Jun 2015 12:24:53 +0200 [thread overview]
Message-ID: <20150609102453.GT3644@twins.programming.kicks-ass.net> (raw)
In-Reply-To: <20150609094318.12813.qmail@ns.horizon.com>
On Tue, Jun 09, 2015 at 05:43:18AM -0400, George Spelvin wrote:
> Thomas Gleixner wrote:
> > The only reason is performance. The wheel has O(1) insertion and
> > deletion time while heaps and trees usually have O(log(n)).
>
> Pairing heaps also have O(1) insertion, and rescheduling can
> be quite lightweight.
>
> The issue I was worried about is the need for an additional pointer
> per timer (left, right, parent) and the associated cache line touch
> when modifying the heap.
>
> > 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.
>
> And that rewards very lazy structures, that postpone work in the
> hope it will become unnecessary. But a wheel has real problems with
> non-tick-based timers, which as you note covers both hrtimers and NOHZ.
>
> Now, two things to note about pairing heaps (and many related heap
> structures like Fibonacci heaps, but pairing heaps have a particularly
> good constant factor in practice) are:
>
> 1) It is O(1) to "meld" two heaps into one.
> 2) The above is O(1) because it's literally "stick it on a linked list";
> the left child pointers are NULL until the minimum (which is kept
> at the head/root) is deleted and a new minimum has to be found.
>
> Combining these two facts, we could do something wheel-like: divide
> the future into a number of heaps, link future events into the correct
> subheap, and meld the subheaps into the main heap when necessary.
>
> Hopefully, by the time it's necessary, the subheap would have been
> thinned out by timers being ccanceled.
Right, so while pairing (and fibonacci) heaps have O(log n) deletion, if
you can delay heapification you can equally delay that extra cost.
But as you say, the heapification is a O(n) hit, which is not too
different from our current 'problem'.
But yes, interesting problem space this.
next prev parent reply other threads:[~2015-06-09 10:25 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-06-05 22:27 [patch 2/7] timer: Remove FIFO guarantee George Spelvin
2015-06-08 17:48 ` Thomas Gleixner
2015-06-09 5:39 ` George Spelvin
2015-06-09 8:05 ` Thomas Gleixner
2015-06-09 9:43 ` George Spelvin
2015-06-09 10:24 ` Peter Zijlstra [this message]
2015-06-09 11:15 ` George Spelvin
-- strict thread matches above, loose matches on Subject: below --
2015-05-26 22:50 [patch 0/7] timers: Footprint diet and NOHZ overhead mitigation Thomas Gleixner
2015-05-26 22:50 ` [patch 2/7] timer: Remove FIFO guarantee Thomas Gleixner
2015-05-27 9:11 ` Viresh Kumar
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20150609102453.GT3644@twins.programming.kicks-ass.net \
--to=peterz@infradead.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@horizon.com \
--cc=tglx@linutronix.de \
--cc=viresh.kumar@linaro.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.