Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752002AbdHGPzm (ORCPT ); Mon, 7 Aug 2017 11:55:42 -0400 Received: from merlin.infradead.org ([205.233.59.134]:51448 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751364AbdHGPzl (ORCPT ); Mon, 7 Aug 2017 11:55:41 -0400 Date: Mon, 7 Aug 2017 17:55:27 +0200 From: Peter Zijlstra To: Alexey Budankov Cc: Ingo Molnar , Arnaldo Carvalho de Melo , Alexander Shishkin , Andi Kleen , Kan Liang , Dmitri Prokhorov , Valery Cherepennikov , Mark Rutland , Stephane Eranian , David Carrillo-Cisneros , linux-kernel Subject: Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Message-ID: <20170807155527.alarhawa64xqhp62@hirez.programming.kicks-ass.net> References: <96c7776f-1f17-a39e-23e9-658596216d6b@linux.intel.com> <20170803130002.oatczvnaalplrsep@hirez.programming.kicks-ass.net> <86cbe0b0-a1ec-4d5f-addc-87bccf2e97d7@linux.intel.com> <20170804143628.34c2xqxl2e6k2arj@hirez.programming.kicks-ass.net> <9d2e25c9-209c-f28a-d601-d3f1a71f032f@linux.intel.com> <20170807083913.vfqmwsdzxsczh4yr@hirez.programming.kicks-ass.net> <20170807091326.5e3iec54ninmeyex@hirez.programming.kicks-ass.net> <9ce8c683-791b-add1-33c4-e65233e2398c@linux.intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <9ce8c683-791b-add1-33c4-e65233e2398c@linux.intel.com> User-Agent: NeoMutt/20170609 (1.8.3) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 2119 Lines: 45 On Mon, Aug 07, 2017 at 06:32:16PM +0300, Alexey Budankov wrote: > On 07.08.2017 12:13, Peter Zijlstra wrote: > > On Mon, Aug 07, 2017 at 10:39:13AM +0200, Peter Zijlstra wrote: > >> On Mon, Aug 07, 2017 at 10:17:46AM +0300, Alexey Budankov wrote: > >>> Makes sense. The implementation becomes a bit simpler. The drawbacks > >>> may be several rotations of potentially big tree on the critical path, > >>> instead of updating four pointers in case of the tree of lists. > >> > >> Yes, but like said, it allows implementing a better scheduler than RR, > >> allowing us to fix rotation artifacts where task runtimes are near the > >> rotation window. > > Could you elaborate more on the artifacts or my be share some link to the theory? In the extreme, if you construct your program such that you'll never get hit by the tick (this used to be a popular measure to hide yourself from time accounting), you'll never rotate the counters, even though you can rack up quite a lot of runtime. By doing a runtime based scheduler, instead of a tick based RR, we'll still get rotation, and the tick will only function as a forced reprogram point. > >> A slightly more complicated, but also interested scheduling problem is > >> the per-cpu flexible vs the per-task flexible. Ideally we'd rotate them > >> at the same priority based on service, without strictly prioritizing the > >> per-cpu events. > >> > >> Again, that is something that should be possible once we have a more > >> capable event scheduler. > >> > >> > >> So yes, cons and pros.. :-) > > > > Also, I think for AVL tree you could do the erase and (re)insert > > combined and then rebalance in one go, not sure RB allows the same > > thing, but it might be fun looking into. > > Not sure if AVL is more practical here. You get better balancing what gives > you faster average search for the price of longer modifications > so yes, need to measure and compare ... :-) Oh, I wasn't suggesting using AVL (the last thing we need is another balanced tree in the kernel), I was merely wondering if you could do compound/bulk updates on RB as you can with AVL.