From: Alexey Budankov <alexey.budankov@linux.intel.com>
To: Alexander Shishkin <alexander.shishkin@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
Date: Wed, 23 Aug 2017 17:18:54 +0300 [thread overview]
Message-ID: <6e70f551-a9a3-deb9-67b1-a82251d69c36@linux.intel.com> (raw)
In-Reply-To: <87o9r6z9lt.fsf@ashishki-desk.ger.corp.intel.com>
On 23.08.2017 16:39, Alexander Shishkin wrote:
> 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.
I implemented the solution Peter suggested. Then I was testing and noticed
considerable difference in amount of collected samples when multiplexing
event, in comparison to the version with tree of lists.
I then looked for a fast way to emulate the idea with virtual index as
a secondary key and found this RB tree emulator:
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
and it showed me the picture I mentioned above:
02
/ \
01 14
/ \
03 15
\
16
I understand it is not 100% proof that index idea doesn't work
however it means that in order to apply the idea to this patch
some more changes are required additionally to what Peter
shared earlier.
>
> Regards,
> --
> Alex
>
>
>
next prev parent reply other threads:[~2017-08-23 14:19 UTC|newest]
Thread overview: 76+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-08-02 8:11 [PATCH v6 0/3] perf/core: addressing 4x slowdown during per-process profiling of STREAM benchmark on Intel Xeon Phi Alexey Budankov
2017-08-02 8:13 ` [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Alexey Budankov
2017-08-03 13:00 ` Peter Zijlstra
2017-08-03 20:30 ` Alexey Budankov
2017-08-04 14:36 ` Peter Zijlstra
2017-08-07 7:17 ` Alexey Budankov
2017-08-07 8:39 ` Peter Zijlstra
2017-08-07 9:13 ` Peter Zijlstra
2017-08-07 15:32 ` Alexey Budankov
2017-08-07 15:55 ` Peter Zijlstra
2017-08-07 16:27 ` Alexey Budankov
2017-08-07 16:57 ` Peter Zijlstra
2017-08-07 17:39 ` Andi Kleen
2017-08-07 18:12 ` Peter Zijlstra
2017-08-07 18:13 ` Alexey Budankov
2017-08-15 17:28 ` Alexey Budankov
2017-08-23 13:39 ` Alexander Shishkin
2017-08-23 14:18 ` Alexey Budankov [this message]
2017-08-29 13:51 ` Alexander Shishkin
2017-08-30 8:30 ` Alexey Budankov
2017-08-30 10:18 ` Alexander Shishkin
2017-08-30 10:30 ` Alexey Budankov
2017-08-30 11:13 ` Alexander Shishkin
2017-08-30 11:16 ` Alexey Budankov
2017-08-31 10:12 ` Alexey Budankov
2017-08-31 10:12 ` Alexey Budankov
2017-08-04 14:53 ` Peter Zijlstra
2017-08-07 15:22 ` Alexey Budankov
2017-08-02 8:15 ` [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Alexey Budankov
2017-08-03 13:04 ` Peter Zijlstra
2017-08-03 14:00 ` Peter Zijlstra
2017-08-03 15:58 ` Alexey Budankov
2017-08-04 12:36 ` Peter Zijlstra
2017-08-03 15:00 ` Peter Zijlstra
2017-08-03 18:47 ` Alexey Budankov
2017-08-04 12:35 ` Peter Zijlstra
2017-08-04 12:51 ` Peter Zijlstra
2017-08-04 14:25 ` Alexey Budankov
2017-08-04 14:23 ` Alexey Budankov
2017-08-10 15:57 ` Alexey Budankov
2017-08-22 20:47 ` Peter Zijlstra
2017-08-23 8:54 ` Alexey Budankov
2017-08-31 17:18 ` [RFC][PATCH] perf: Rewrite enabled/running timekeeping Peter Zijlstra
2017-08-31 19:51 ` Stephane Eranian
2017-09-05 7:51 ` Stephane Eranian
2017-09-05 9:44 ` Peter Zijlstra
2017-09-01 10:45 ` Alexey Budankov
2017-09-01 12:31 ` Peter Zijlstra
2017-09-01 11:17 ` Alexey Budankov
2017-09-01 12:42 ` Peter Zijlstra
2017-09-01 21:03 ` Vince Weaver
2017-09-04 10:46 ` Alexey Budankov
2017-09-04 12:08 ` Peter Zijlstra
2017-09-04 14:56 ` Alexey Budankov
2017-09-04 15:41 ` Peter Zijlstra
2017-09-04 15:58 ` Peter Zijlstra
2017-09-05 10:17 ` Alexey Budankov
2017-09-05 11:19 ` Peter Zijlstra
2017-09-11 6:55 ` Alexey Budankov
2017-09-05 12:06 ` Alexey Budankov
2017-09-05 12:59 ` Peter Zijlstra
2017-09-05 16:03 ` Peter Zijlstra
2017-09-06 13:48 ` Alexey Budankov
2017-09-08 8:47 ` Alexey Budankov
2018-03-12 17:43 ` [tip:perf/core] perf/cor: Use RB trees for pinned/flexible groups tip-bot for Alexey Budankov
2017-08-02 8:16 ` [PATCH v6 3/3]: perf/core: add mux switch to skip to the current CPU's events list on mux interrupt Alexey Budankov
2017-08-18 5:17 ` [PATCH v7 0/2] perf/core: addressing 4x slowdown during per-process profiling of STREAM benchmark on Intel Xeon Phi Alexey Budankov
2017-08-18 5:21 ` [PATCH v7 1/2] perf/core: use rb trees for pinned/flexible groups Alexey Budankov
2017-08-23 11:17 ` Alexander Shishkin
2017-08-23 17:23 ` Alexey Budankov
2017-08-18 5:22 ` [PATCH v7 2/2] perf/core: add mux switch to skip to the current CPU's events list on mux interrupt Alexey Budankov
2017-08-23 11:54 ` Alexander Shishkin
2017-08-23 18:12 ` Alexey Budankov
2017-08-22 20:21 ` [PATCH v7 0/2] perf/core: addressing 4x slowdown during per-process profiling of STREAM benchmark on Intel Xeon Phi Peter Zijlstra
2017-08-23 8:54 ` Alexey Budankov
2017-08-31 10:12 ` Alexey Budankov
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=6e70f551-a9a3-deb9-67b1-a82251d69c36@linux.intel.com \
--to=alexey.budankov@linux.intel.com \
--cc=Dmitry.Prohorov@intel.com \
--cc=acme@kernel.org \
--cc=ak@linux.intel.com \
--cc=alexander.shishkin@linux.intel.com \
--cc=davidcc@google.com \
--cc=eranian@google.com \
--cc=kan.liang@intel.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mark.rutland@arm.com \
--cc=mingo@redhat.com \
--cc=peterz@infradead.org \
--cc=valery.cherepennikov@intel.com \
/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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.