Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1705648

Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups

From Alexey Budankov <alexey.budankov@linux.intel.com>
Newsgroups linux.kernel
Subject Re: [PATCH v6 1/3] perf/core: use rb trees for pinned/flexible groups
Date 2017-08-07 17:40 +0200
Message-ID <ubSim-1Ys-21@gated-at.bofh.it> (permalink)
References (3 earlier) <uav4t-5ap-5@gated-at.bofh.it> <uaLVF-8da-57@gated-at.bofh.it> <ubKuu-59V-19@gated-at.bofh.it> <ubLJV-5RE-25@gated-at.bofh.it> <ubMmC-6k5-13@gated-at.bofh.it>
Organization Intel Corp.

Show all headers | View raw

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 ... :-)

>

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[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

csiph-web