From: Peter Zijlstra <peterz@infradead.org>
To: Davidlohr Bueso <dave@stgolabs.net>
Cc: mingo@kernel.org, akpm@linux-foundation.org,
torvalds@linux-foundation.org, jack@suse.cz,
kirill.shutemov@linux.intel.com, ldufour@linux.vnet.ibm.com,
mhocko@suse.com, mgorman@techsingularity.net,
linux-kernel@vger.kernel.org
Subject: Re: [PATCH -next v3 0/9] rbtree: Cache leftmost node internally
Date: Wed, 5 Jul 2017 19:47:33 +0200 [thread overview]
Message-ID: <20170705174733.v2clo62p45oftu4z@hirez.programming.kicks-ass.net> (raw)
In-Reply-To: <20170629171553.2146-1-dave@stgolabs.net>
On Thu, Jun 29, 2017 at 10:15:44AM -0700, Davidlohr Bueso wrote:
> Here's a proposal for extending rbtrees to internally cache the leftmost
> node such that we can have fast overlap check optimization for all interval
> tree users[1]. The benefits of this series are that:
>
> (i) Unify users that do internal leftmost node caching.
> (ii) Optimize all interval tree users.
> (iii) Convert at least two new users (epoll and procfs) to the new interface.
>
> Patch 1: Layout the rb machinery.
>
> Patches 2-5: Make use of the internal leftmost node in scheduler and
> rt mutexes and cfq.
>
> Patch 6: Implements fast overlap checks for interval trees.
>
> Patch 7: rocket science.
>
> Patches 8,9: New patches that convert to O(1) rb_first_cached().
>
> The series has survived booting, kernel builds and pistress workloads.
>
> Ingo, I know it's late in the game, but could it be considered for
> v4.13? Given that v2 has been there a while and there are no issues
> currently. Applies on top of today's -next.
IIRC akpm typically collects rb-tree patches.
In any case:
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
next prev parent reply other threads:[~2017-07-05 17:49 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-06-29 17:15 Davidlohr Bueso
2017-06-29 17:15 ` [PATCH 1/9] " Davidlohr Bueso
2017-07-15 10:54 ` Christoph Hellwig
2017-07-15 15:28 ` Davidlohr Bueso
2017-06-29 17:15 ` [PATCH 2/9] sched/fair: Replace cfs_rq->rb_leftmost Davidlohr Bueso
2017-06-29 17:15 ` [PATCH 3/9] sched/deadline: Replace earliest dl and rq leftmost caching Davidlohr Bueso
2017-06-29 17:15 ` [PATCH 4/9] locking/rtmutex: Replace top-waiter and pi_waiters " Davidlohr Bueso
2017-06-29 17:15 ` [PATCH 5/9] block/cfq: Replace cfq_rb_root " Davidlohr Bueso
2017-06-29 17:15 ` [PATCH 6/9] lib/interval_tree: Fast overlap detection Davidlohr Bueso
2017-06-29 17:15 ` [PATCH 7/9] lib/interval-tree: Correct comment wrt generic flavor Davidlohr Bueso
2017-06-29 17:15 ` [PATCH 8/9] procfs: Use faster rb_first_cached() Davidlohr Bueso
2017-06-29 17:15 ` [PATCH 9/9] fs/epoll: " Davidlohr Bueso
2017-07-05 17:47 ` Peter Zijlstra [this message]
2017-07-19 22:54 ` [PATCH -next v3 0/9] rbtree: Cache leftmost node internally Andrew Morton
2017-07-19 23:00 ` Davidlohr Bueso
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=20170705174733.v2clo62p45oftu4z@hirez.programming.kicks-ass.net \
--to=peterz@infradead.org \
--cc=akpm@linux-foundation.org \
--cc=dave@stgolabs.net \
--cc=jack@suse.cz \
--cc=kirill.shutemov@linux.intel.com \
--cc=ldufour@linux.vnet.ibm.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mgorman@techsingularity.net \
--cc=mhocko@suse.com \
--cc=mingo@kernel.org \
--cc=torvalds@linux-foundation.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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®