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) <pet...@infradead.org>
