Re: [PATCH 3/7] perf: order iterators for visit_groups_merge into a min-heap

[Peter Zijlstra <peterz@infradead.org>]

On Mon, Jul 01, 2019 at 11:59:51PM -0700, Ian Rogers wrote:
> The groups rbtree holding perf events, either for a CPU or a task, needs
> to have multiple iterators that visit events in group_index (insertion)
> order. Rather than linearly searching the iterators, use a min-heap to go
> from a O(#iterators) search to a O(log2(#iterators)) insert cost per event
> visited.

Is this actually faster for the common (very small n) case?

ISTR 'stupid' sorting algorithms are actually faster when the data fits
into L1

> Signed-off-by: Ian Rogers <irogers@google.com>
> ---
>  kernel/events/core.c | 123 +++++++++++++++++++++++++++++++++----------
>  1 file changed, 95 insertions(+), 28 deletions(-)
> 
> diff --git a/kernel/events/core.c b/kernel/events/core.c
> index 9a2ad34184b8..396b5ac6dcd4 100644
> --- a/kernel/events/core.c
> +++ b/kernel/events/core.c
> @@ -3318,6 +3318,77 @@ static void cpu_ctx_sched_out(struct perf_cpu_context *cpuctx,
>  	ctx_sched_out(&cpuctx->ctx, cpuctx, event_type);
>  }
>  
> +/* Data structure used to hold a min-heap, ordered by group_index, of a fixed
> + * maximum size.
> + */

Broken comment style.

> +struct perf_event_heap {
> +	struct perf_event **storage;
> +	int num_elements;
> +	int max_elements;
> +};
> +
> +static void min_heap_swap(struct perf_event_heap *heap,
> +			  int pos1, int pos2)
> +{
> +	struct perf_event *tmp = heap->storage[pos1];
> +
> +	heap->storage[pos1] = heap->storage[pos2];
> +	heap->storage[pos2] = tmp;
> +}
> +
> +/* Sift the perf_event at pos down the heap. */
> +static void min_heapify(struct perf_event_heap *heap, int pos)
> +{
> +	int left_child, right_child;
> +
> +	while (pos > heap->num_elements / 2) {
> +		left_child = pos * 2;
> +		right_child = pos * 2 + 1;
> +		if (heap->storage[pos]->group_index >
> +		    heap->storage[left_child]->group_index) {
> +			min_heap_swap(heap, pos, left_child);
> +			pos = left_child;
> +		} else if (heap->storage[pos]->group_index >
> +			   heap->storage[right_child]->group_index) {
> +			min_heap_swap(heap, pos, right_child);
> +			pos = right_child;
> +		} else {
> +			break;
> +		}
> +	}
> +}
> +
> +/* Floyd's approach to heapification that is O(n). */
> +static void min_heapify_all(struct perf_event_heap *heap)
> +{
> +	int i;
> +
> +	for (i = heap->num_elements / 2; i > 0; i--)
> +		min_heapify(heap, i);
> +}
> +
> +/* Remove minimum element from the heap. */
> +static void min_heap_pop(struct perf_event_heap *heap)
> +{
> +	WARN_ONCE(heap->num_elements <= 0, "Popping an empty heap");
> +	heap->num_elements--;
> +	heap->storage[0] = heap->storage[heap->num_elements];
> +	min_heapify(heap, 0);
> +}

Is this really the first heap implementation in the kernel?

> @@ -3378,12 +3453,14 @@ static int visit_groups_merge(struct perf_event_context *ctx,
>  			struct cgroup_subsys_state *css;
>  
>  			for (css = &cpuctx->cgrp->css; css; css = css->parent) {
> -				itrs[num_itrs] = perf_event_groups_first(groups,
> +				heap.storage[heap.num_elements] =
> +						perf_event_groups_first(groups,
>  								   cpu,
>  								   css->cgroup);
> -				if (itrs[num_itrs]) {
> -					num_itrs++;
> -					if (num_itrs == max_itrs) {
> +				if (heap.storage[heap.num_elements]) {
> +					heap.num_elements++;
> +					if (heap.num_elements ==
> +					    heap.max_elements) {
>  						WARN_ONCE(
>  				     max_cgroups_with_events_depth,
>  				     "Insufficient iterators for cgroup depth");

That's turning into unreadable garbage due to indentation; surely
there's a solution for that.