Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1701835 > unrolled thread
| Started by | Alexey Budankov <alexey.budankov@linux.intel.com> |
|---|---|
| First post | 2017-08-02 10:20 +0200 |
| Last post | 2017-08-07 17:30 +0200 |
| Articles | 10 on this page of 30 — 3 participants |
Back to article view | Back to linux.kernel
[PATCH v6 0/3] perf/core: addressing 4x slowdown during per-process profiling of STREAM benchmark on Intel Xeon Phi Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-02 10:20 +0200
[PATCH v6 3/3]: perf/core: add mux switch to skip to the current CPU's events list on mux interrupt Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-02 10:20 +0200
[PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-02 10:20 +0200
Re: [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Peter Zijlstra <peterz@infradead.org> - 2017-08-03 15:10 +0200
Re: [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Peter Zijlstra <peterz@infradead.org> - 2017-08-03 16:10 +0200
Re: [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-03 18:00 +0200
Re: [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Peter Zijlstra <peterz@infradead.org> - 2017-08-04 14:40 +0200
Re: [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Peter Zijlstra <peterz@infradead.org> - 2017-08-03 17:10 +0200
Re: [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-03 20:50 +0200
Re: [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Peter Zijlstra <peterz@infradead.org> - 2017-08-04 14:40 +0200
Re: [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Peter Zijlstra <peterz@infradead.org> - 2017-08-04 15:00 +0200
Re: [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-04 16:30 +0200
Re: [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-04 16:30 +0200
Re: [PATCH v6 2/3]: perf/core: use context tstamp_data for skipped events on mux interrupt Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-10 18:00 +0200
[PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-02 10:20 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Peter Zijlstra <peterz@infradead.org> - 2017-08-03 15:10 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-03 22:40 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Peter Zijlstra <peterz@infradead.org> - 2017-08-04 16:40 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-07 09:20 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Peter Zijlstra <peterz@infradead.org> - 2017-08-07 10:40 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Peter Zijlstra <peterz@infradead.org> - 2017-08-07 11:20 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-07 17:40 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Peter Zijlstra <peterz@infradead.org> - 2017-08-07 18:00 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-07 18:30 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Peter Zijlstra <peterz@infradead.org> - 2017-08-07 19:00 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Andi Kleen <ak@linux.intel.com> - 2017-08-07 19:50 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Peter Zijlstra <peterz@infradead.org> - 2017-08-07 20:20 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-07 20:20 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Peter Zijlstra <peterz@infradead.org> - 2017-08-04 17:00 +0200
Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups Alexey Budankov <alexey.budankov@linux.intel.com> - 2017-08-07 17:30 +0200
Page 2 of 2 — ← Prev page 1 [2]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-08-07 11:20 +0200 |
| Subject | Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups |
| Message-ID | <ubMmC-6k5-13@gated-at.bofh.it> |
| In reply to | #1705241 |
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. > > 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.
[toc] | [prev] | [next] | [standalone]
| From | Alexey Budankov <alexey.budankov@linux.intel.com> |
|---|---|
| Date | 2017-08-07 17:40 +0200 |
| Subject | Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups |
| Message-ID | <ubSim-1Ys-21@gated-at.bofh.it> |
| In reply to | #1705277 |
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? >> >> 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 ... :-) >
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-08-07 18:00 +0200 |
| Subject | Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups |
| Message-ID | <ubSBI-291-3@gated-at.bofh.it> |
| In reply to | #1705648 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Alexey Budankov <alexey.budankov@linux.intel.com> |
|---|---|
| Date | 2017-08-07 18:30 +0200 |
| Subject | Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups |
| Message-ID | <ubT4K-2E7-33@gated-at.bofh.it> |
| In reply to | #1705665 |
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. >
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-08-07 19:00 +0200 |
| Subject | Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups |
| Message-ID | <ubTxM-2Qn-15@gated-at.bofh.it> |
| In reply to | #1705694 |
On Mon, Aug 07, 2017 at 07:27:30PM +0300, Alexey Budankov wrote: > On 07.08.2017 18:55, Peter Zijlstra wrote: > > 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. Like I said, in extreme. Typically its less weird. Another example is scheduling a very constrained counter/group along with a bunch of simple events such that the group will only succeed to schedule when its the first. In this case it will get only 1/nr_events time with RR, as opposed to the other/simple events that will get nr_counters/nr_events time. By making it runtime based, the constrained thing will more often be head of list and acquire equal total runtime to the other events.
[toc] | [prev] | [next] | [standalone]
| From | Andi Kleen <ak@linux.intel.com> |
|---|---|
| Date | 2017-08-07 19:50 +0200 |
| Subject | Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups |
| Message-ID | <ubUka-3qL-27@gated-at.bofh.it> |
| In reply to | #1705716 |
On Mon, Aug 07, 2017 at 06:57:11PM +0200, Peter Zijlstra wrote: > On Mon, Aug 07, 2017 at 07:27:30PM +0300, Alexey Budankov wrote: > > On 07.08.2017 18:55, Peter Zijlstra wrote: > > > > 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. > > Like I said, in extreme. Typically its less weird. > > Another example is scheduling a very constrained counter/group along > with a bunch of simple events such that the group will only succeed to > schedule when its the first. In this case it will get only 1/nr_events > time with RR, as opposed to the other/simple events that will get > nr_counters/nr_events time. > > By making it runtime based, the constrained thing will more often be > head of list and acquire equal total runtime to the other events. I'm not sure Alexey's patch kit will be able to solve every possible problem with the event scheduler. Trying to fix everything at the same time is usually difficult. It would seem better to mainly focus on the scaling problem for now (which is essentially a show stopper bug for one platform) and then tackle other problems later once that is solved. -Andi
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-08-07 20:20 +0200 |
| Subject | Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups |
| Message-ID | <ubUNc-3Tz-11@gated-at.bofh.it> |
| In reply to | #1705749 |
On Mon, Aug 07, 2017 at 10:39:55AM -0700, Andi Kleen wrote: > I'm not sure Alexey's patch kit will be able to solve every possible > problem with the event scheduler. Trying to fix everything at > the same time is usually difficult. I didn't say he should solve this. Just said that putting everything in a tree enables solving it.
[toc] | [prev] | [next] | [standalone]
| From | Alexey Budankov <alexey.budankov@linux.intel.com> |
|---|---|
| Date | 2017-08-07 20:20 +0200 |
| Subject | Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups |
| Message-ID | <ubUNb-3Tz-7@gated-at.bofh.it> |
| In reply to | #1705716 |
On 07.08.2017 19:57, Peter Zijlstra wrote: > On Mon, Aug 07, 2017 at 07:27:30PM +0300, Alexey Budankov wrote: >> On 07.08.2017 18:55, Peter Zijlstra wrote: > >>> 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. > > Like I said, in extreme. Typically its less weird.> > Another example is scheduling a very constrained counter/group along > with a bunch of simple events such that the group will only succeed to > schedule when its the first. In this case it will get only 1/nr_events > time with RR, as opposed to the other/simple events that will get > nr_counters/nr_events time. > > By making it runtime based, the constrained thing will more often be > head of list and acquire equal total runtime to the other events. I see and what could be the triggering condition for runtime based scheduling of groups as an alternative to hrtimer signal? >
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-08-04 17:00 +0200 |
| Subject | Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups |
| Message-ID | <uaMeZ-8ke-11@gated-at.bofh.it> |
| In reply to | #1703412 |
On Thu, Aug 03, 2017 at 11:30:09PM +0300, Alexey Budankov wrote:
> On 03.08.2017 16:00, Peter Zijlstra wrote:
> > On Wed, Aug 02, 2017 at 11:13:54AM +0300, Alexey Budankov wrote:
> >> @@ -2759,13 +2932,13 @@ static void ctx_sched_out(struct perf_event_context *ctx,
> >>
> >> perf_pmu_disable(ctx->pmu);
> >> if (is_active & EVENT_PINNED) {
> >> - list_for_each_entry(event, &ctx->pinned_groups, group_entry)
> >> - group_sched_out(event, cpuctx, ctx);
> >> + perf_event_groups_iterate(&ctx->pinned_groups,
> >> + group_sched_out_callback, ¶ms);
> >
> > So here I would expect to not iterate events where event->cpu !=
> > smp_processor_id() (and ideally not where event->pmu != ctx->pmu).
> >
>
> We still need to iterate thru all groups on thread context switch in
> and out as well as iterate thru cpu == -1 list (software events) additionally
> to smp_processor_id() list from multiplexing timer interrupt handler.
Well, just doing the @cpu=-1 and @cpu=this_cpu subtrees is less work
than iterating _everything_, right?
The rest will not survive event_filter_match() anyway, so iterating them
is complete waste of time, and once we have them in a tree, its actually
easy to find this subset.
[toc] | [prev] | [next] | [standalone]
| From | Alexey Budankov <alexey.budankov@linux.intel.com> |
|---|---|
| Date | 2017-08-07 17:30 +0200 |
| Subject | Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups |
| Message-ID | <ubS8G-1Uh-19@gated-at.bofh.it> |
| In reply to | #1704052 |
On 04.08.2017 17:53, Peter Zijlstra wrote:
> On Thu, Aug 03, 2017 at 11:30:09PM +0300, Alexey Budankov wrote:
>> On 03.08.2017 16:00, Peter Zijlstra wrote:
>>> On Wed, Aug 02, 2017 at 11:13:54AM +0300, Alexey Budankov wrote:
>
>>>> @@ -2759,13 +2932,13 @@ static void ctx_sched_out(struct perf_event_context *ctx,
>>>>
>>>> perf_pmu_disable(ctx->pmu);
>>>> if (is_active & EVENT_PINNED) {
>>>> - list_for_each_entry(event, &ctx->pinned_groups, group_entry)
>>>> - group_sched_out(event, cpuctx, ctx);
>>>> + perf_event_groups_iterate(&ctx->pinned_groups,
>>>> + group_sched_out_callback, ¶ms);
>>>
>>> So here I would expect to not iterate events where event->cpu !=
>>> smp_processor_id() (and ideally not where event->pmu != ctx->pmu).
>>>
>>
>> We still need to iterate thru all groups on thread context switch in
>> and out as well as iterate thru cpu == -1 list (software events) additionally
>> to smp_processor_id() list from multiplexing timer interrupt handler.
>
> Well, just doing the @cpu=-1 and @cpu=this_cpu subtrees is less work
> than iterating _everything_, right?
Right. That is actually the aim of this whole patch set - to avoid iterating "_everything_".
>
> The rest will not survive event_filter_match() anyway, so iterating them
> is complete waste of time, and once we have them in a tree, its actually
> easy to find this subset.
>
[toc] | [prev] | [standalone]
Page 2 of 2 — ← Prev page 1 [2]
Back to top | Article view | linux.kernel
csiph-web