From 73e40c9bd44ce91fd0fcee6f0a3480dcd97963b6 Mon Sep 17 00:00:00 2001 From: Riccardo Mancini Date: Sat, 21 Aug 2021 11:19:07 +0200 Subject: libperf cpumap: Use binary search in perf_cpu_map__idx() as array are sorted Since 7074674e7338863e ("perf cpumap: Maintain cpumaps ordered and without dups") perf_cpu_map elements are sorted in ascending order. This patch improves perf_cpu_map__idx() by using a binary search. Signed-off-by: Riccardo Mancini Cc: Andi Kleen Cc: Ian Rogers Cc: Jiri Olsa Cc: Mark Rutland Cc: Namhyung Kim Cc: Peter Zijlstra Link: http://lore.kernel.org/lkml/f1543c15797169c21e8b205a4a6751159180580d.1629490974.git.rickyman7@gmail.com [ Removed 'else' after if + return, declared variables where needed ] Signed-off-by: Arnaldo Carvalho de Melo --- tools/lib/perf/cpumap.c | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) (limited to 'tools/lib') diff --git a/tools/lib/perf/cpumap.c b/tools/lib/perf/cpumap.c index 6d8e521c59e1..adaad3dddf6e 100644 --- a/tools/lib/perf/cpumap.c +++ b/tools/lib/perf/cpumap.c @@ -270,11 +270,19 @@ bool perf_cpu_map__empty(const struct perf_cpu_map *map) int perf_cpu_map__idx(struct perf_cpu_map *cpus, int cpu) { - int i; + int low = 0, high = cpus->nr; - for (i = 0; i < cpus->nr; ++i) { - if (cpus->map[i] == cpu) - return i; + while (low < high) { + int idx = (low + high) / 2, + cpu_at_idx = cpus->map[idx]; + + if (cpu_at_idx == cpu) + return idx; + + if (cpu_at_idx > cpu) + high = idx; + else + low = idx + 1; } return -1; -- cgit