linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [RFC 0/6] optimize ctx switch with rb-tree
@ 2017-01-10 10:24 David Carrillo-Cisneros
  2017-01-10 10:24 ` [RFC 1/6] perf/core: create active and inactive event groups David Carrillo-Cisneros
                   ` (6 more replies)
  0 siblings, 7 replies; 33+ messages in thread
From: David Carrillo-Cisneros @ 2017-01-10 10:24 UTC (permalink / raw)
  To: linux-kernel
  Cc: x86, Ingo Molnar, Thomas Gleixner, Andi Kleen, Kan Liang,
	Peter Zijlstra, Borislav Petkov, Srinivas Pandruvada,
	Dave Hansen, Vikas Shivappa, Mark Rutland,
	Arnaldo Carvalho de Melo, Vince Weaver, Paul Turner,
	Stephane Eranian, David Carrillo-Cisneros

Following the discussion in:
https://patchwork.kernel.org/patch/9420035/

This is is an early version of a series of perf context switches
optimizations.

The main idea is to create and maintain a list of inactive events sorted
by timestamp, and a rb-tree index to index it. The rb-tree's key are
{cpu,flexible,stamp} for task contexts and {cgroup,flexible,stamp}
for CPU contexts.

The rb-tree provides functions to find intervals in the inactive event
list so that ctx_sched_in only has to visit the events that can be
potentially be scheduled (i.e. avoid iterations over events bound
to CPUs or cgroups that are not current).

Since the inactive list is sort by timestamp, rotation can be done by
simply scheduling out and in the events. This implies that each timer
interrupt, the events will rotate by q events (where q is the number
of hardware counters). This changes the current behavior of rotation.
Feedback welcome!

I haven't profiled the new approach. I am only assuming it will be
superior when the number of per-cpu or distict cgroup events is large.

The last patch shows how perf_iterate_ctx can use the new rb-tree index
to reduce the number of visited events. I haven't looked carefully if
locking and other things are correct.

If this changes are in the right direction. A next version could remove
some existing code, specifically the lists ctx->pinned_groups and
ctx->flexible_groups could be removed. Also, event_filter_match could be
simplified when called on events groups filtered using the rb-tree, since
both perform similar checks.

David Carrillo-Cisneros (6):
  perf/core: create active and inactive event groups
  perf/core: add a rb-tree index to inactive_groups
  perf/core: use rb-tree to sched in event groups
  perf/core: avoid rb-tree traversal when no inactive events
  perf/core: rotation no longer neccesary. Behavior has changed. Beware
  perf/core: use rb-tree index to optimize filtered  perf_iterate_ctx

 include/linux/perf_event.h |  13 ++
 kernel/events/core.c       | 466 +++++++++++++++++++++++++++++++++++++++------
 2 files changed, 426 insertions(+), 53 deletions(-)

-- 
2.11.0.390.gc69c2f50cf-goog

^ permalink raw reply	[flat|nested] 33+ messages in thread

end of thread, other threads:[~2017-04-26 19:40 UTC | newest]

Thread overview: 33+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-01-10 10:24 [RFC 0/6] optimize ctx switch with rb-tree David Carrillo-Cisneros
2017-01-10 10:24 ` [RFC 1/6] perf/core: create active and inactive event groups David Carrillo-Cisneros
2017-01-10 13:49   ` Mark Rutland
2017-01-10 20:45     ` David Carrillo-Cisneros
2017-01-12 11:05       ` Mark Rutland
     [not found]         ` <CALcN6mhPmpSqKhE3Ua+j-xROLzeAyrgdCk4AGGtfF9kExXRTJg@mail.gmail.com>
2017-01-13 11:01           ` Mark Rutland
2017-01-10 10:24 ` [RFC 2/6] perf/core: add a rb-tree index to inactive_groups David Carrillo-Cisneros
2017-01-10 14:14   ` Mark Rutland
2017-01-10 20:20     ` David Carrillo-Cisneros
2017-01-12 11:47       ` Mark Rutland
2017-01-13  7:34         ` David Carrillo-Cisneros
2017-01-16  2:03   ` [lkp-developer] [perf/core] 33da94bd89: BUG:unable_to_handle_kernel kernel test robot
2017-01-10 10:24 ` [RFC 3/6] perf/core: use rb-tree to sched in event groups David Carrillo-Cisneros
2017-01-10 16:38   ` Mark Rutland
2017-01-10 20:51     ` David Carrillo-Cisneros
2017-01-12 12:14       ` Mark Rutland
2017-01-13  8:01         ` David Carrillo-Cisneros
2017-01-13 10:24           ` Mark Rutland
2017-01-11 20:31     ` Liang, Kan
2017-01-12 10:11       ` Mark Rutland
2017-01-12 13:28         ` Liang, Kan
2017-01-13  8:05           ` David Carrillo-Cisneros
2017-01-10 10:25 ` [RFC 4/6] perf/core: avoid rb-tree traversal when no inactive events David Carrillo-Cisneros
2017-01-10 10:25 ` [RFC 5/6] perf/core: rotation no longer necessary. Behavior has changed. Beware David Carrillo-Cisneros
2017-01-10 10:25 ` [RFC 6/6] perf/core: use rb-tree index to optimize filtered perf_iterate_ctx David Carrillo-Cisneros
2017-01-16  2:05   ` [lkp-developer] [perf/core] 49c04ee1a7: WARNING:at_kernel/events/core.c:#perf_iterate_ctx_matching kernel test robot
2017-04-25 17:27 ` [RFC 0/6] optimize ctx switch with rb-tree Liang, Kan
2017-04-25 17:49   ` David Carrillo-Cisneros
2017-04-25 18:11     ` Budankov, Alexey
2017-04-25 18:54       ` David Carrillo-Cisneros
2017-04-26 10:34         ` Budankov, Alexey
2017-04-26 19:40           ` David Carrillo-Cisneros
2017-04-26 10:52         ` Mark Rutland

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).