Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751872AbdHGQ1g (ORCPT ); Mon, 7 Aug 2017 12:27:36 -0400 Received: from mga01.intel.com ([192.55.52.88]:10613 "EHLO mga01.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751443AbdHGQ1f (ORCPT ); Mon, 7 Aug 2017 12:27:35 -0400 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.41,339,1498546800"; d="scan'208";a="1202968428" Subject: Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups To: Peter Zijlstra 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 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> <20170807155527.alarhawa64xqhp62@hirez.programming.kicks-ass.net> From: Alexey Budankov Organization: Intel Corp. Message-ID: <6272c0e7-7254-9035-d0bc-3abf5485d309@linux.intel.com> Date: Mon, 7 Aug 2017 19:27:30 +0300 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.2.1 MIME-Version: 1.0 In-Reply-To: <20170807155527.alarhawa64xqhp62@hirez.programming.kicks-ass.net> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 2470 Lines: 56 On 07.08.2017 18:55, Peter Zijlstra wrote: > 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) Well, some weird thing for me. Never run longer than one tick? I could imaging some I/O bound code that would fast serve some short messages, all the other time waiting for incoming requests. Not sure if CPU events monitoring is helpful in this case. > , 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. Aww, I see. >