From: "George Spelvin" <linux@horizon.com>
To: linux@horizon.com, tglx@linutronix.de
Cc: linux-kernel@vger.kernel.org, peterz@infradead.org,
viresh.kumar@linaro.org
Subject: Re: [patch 2/7] timer: Remove FIFO guarantee
Date: 9 Jun 2015 05:43:18 -0400 [thread overview]
Message-ID: <20150609094318.12813.qmail@ns.horizon.com> (raw)
In-Reply-To: <alpine.DEB.2.11.1506091001020.4133@nanos>
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.
On reflection, it wouldn't even be necessary to have explicit code to
handle the melding. Just allocate an array of "internal use" nodes
which are easy to find, and place them in the main tree like
normal. (Each has a timeout which is guaranteed to be earliest in
its subheap, so the subjeap will never need sorting.)
When one gets to the root, the internal node gets recycled (because
we set up the callback function to do that!) and the subheap gets
sorted and merged into the main heap automatically.
Alternatively, the internal use node could be made smaller (e.g.
an hlist head rather than a normal node) at the expense of needing
special-case code to handle it.
Have to think on this. Heapifying the sublist is O(n) work, which is
the same as overflowing a bucket, but it means that additional deletions
will be more expensive.
Need to think on this.
next prev parent reply other threads:[~2015-06-09 9:43 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 [this message]
2015-06-09 10:24 ` Peter Zijlstra
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=20150609094318.12813.qmail@ns.horizon.com \
--to=linux@horizon.com \
--cc=linux-kernel@vger.kernel.org \
--cc=peterz@infradead.org \
--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.