Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
        id S1754124AbdHWNqJ (ORCPT <rfc822;w@1wt.eu>);
        Wed, 23 Aug 2017 09:46:09 -0400
Received: from mga01.intel.com ([192.55.52.88]:16617 "EHLO mga01.intel.com"
        rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP
        id S1754001AbdHWNqI (ORCPT <rfc822;linux-kernel@vger.kernel.org>);
        Wed, 23 Aug 2017 09:46:08 -0400
X-ExtLoop1: 1
X-IronPort-AV: E=Sophos;i="5.41,417,1498546800"; 
   d="scan'208";a="893353090"
From: Alexander Shishkin <alexander.shishkin@linux.intel.com>
To: Alexey Budankov <alexey.budankov@linux.intel.com>,
        Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>,
        Arnaldo Carvalho de Melo <acme@kernel.org>,
        Andi Kleen <ak@linux.intel.com>, Kan Liang <kan.liang@intel.com>,
        Dmitri Prokhorov <Dmitry.Prohorov@intel.com>,
        Valery Cherepennikov <valery.cherepennikov@intel.com>,
        Mark Rutland <mark.rutland@arm.com>,
        Stephane Eranian <eranian@google.com>,
        David Carrillo-Cisneros <davidcc@google.com>,
        linux-kernel <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups
In-Reply-To: <c882a2d5-4b76-e838-f812-0b4f70b0e3f7@linux.intel.com>
References: <96c7776f-1f17-a39e-23e9-658596216d6b@linux.intel.com> <d98d9399-7292-e14d-5988-adc474f4e54a@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> <c882a2d5-4b76-e838-f812-0b4f70b0e3f7@linux.intel.com>
User-Agent: Notmuch/0.23.7 (http://notmuchmail.org) Emacs/25.1.1 (x86_64-pc-linux-gnu)
Date: Wed, 23 Aug 2017 16:39:42 +0300
Message-ID: <87o9r6z9lt.fsf@ashishki-desk.ger.corp.intel.com>
MIME-Version: 1.0
Content-Type: text/plain
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
Content-Length: 1129
Lines: 52

Alexey Budankov <alexey.budankov@linux.intel.com> writes:

>>>>> bool event_less(left, right)
>>>>> {
>>>>>   if (left->cpu < right->cpu)
>>>>>     return true;
>>>>>
>>>>>   if (left->cpu > right_cpu)
>>>>>     return false;
>>>>>
>>>>>   if (left->vtime < right->vtime)
>>>>>     return true;
>>>>>
>>>>>   return false;
>>>>> }
>>>>>
>>>>> insert_group(group, event, tail)
>>>>> {
>>>>>   if (tail)
>>>>>     event->vtime = ++group->vtime;
>>>>>
>>>>>   tree_insert(&group->root, event);
>>>>> }

[ ... ]

> 2. implementing special _less() function and rotation by re-inserting
>    group with incremented index;
>

[ ... ]

> Now I figured that not all indexed events are always located under 
> the root with the same cpu, and it depends on the order of insertion
> e.g. with insertion order 01,02,03,14,15,16 we get this:
>
>      02
>     /  \
>    01  14
>       /  \
>      03  15
>            \
>            16

How did you arrive at this? Seeing the actual code would help, because
this is not the ordering we're looking for. With Peter's earlier example
(quoted above) it shouldn't look like this.

Regards,
--
Alex