2021-08-21 09:21:49

by Riccardo Mancini

Subject: [RFC PATCH v1 01/37] libperf cpumap: improve idx function

From commit 7074674e7338863e ("perf cpumap: Maintain cpumaps ordered
and without dups"), perf_cpu_map elements are sorted in ascending order.

This patch improves the perf_cpu_map__idx function by using a binary
search.

Signed-off-by: Riccardo Mancini <[email protected]>
---
tools/lib/perf/cpumap.c | 15 +++++++++++----
1 file changed, 11 insertions(+), 4 deletions(-)

diff --git a/tools/lib/perf/cpumap.c b/tools/lib/perf/cpumap.c
index ca0215047c326af4..fb633272be3aaed9 100644
--- a/tools/lib/perf/cpumap.c
+++ b/tools/lib/perf/cpumap.c
@@ -265,11 +265,18 @@ 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, idx, cpu_at_idx;

- for (i = 0; i < cpus->nr; ++i) {
- if (cpus->map[i] == cpu)
- return i;
+ while (low < high) {
+ idx = (low + high) / 2;
+ cpu_at_idx = cpus->map[idx];
+
+ if (cpu_at_idx == cpu)
+ return idx;
+ else if (cpu_at_idx > cpu)
+ high = idx;
+ else
+ low = idx+1;
}

return -1;
--
2.31.1

2021-08-31 18:49:51

by Arnaldo Carvalho de Melo

Subject: Re: [RFC PATCH v1 01/37] libperf cpumap: improve idx function

Em Sat, Aug 21, 2021 at 11:19:07AM +0200, Riccardo Mancini escreveu:
> >From commit 7074674e7338863e ("perf cpumap: Maintain cpumaps ordered
> and without dups"), perf_cpu_map elements are sorted in ascending order.
>
> This patch improves the perf_cpu_map__idx function by using a binary
> search.

Why not use bsearch()? See 'man bsearch' and look at the example.

- Arnaldo

> Signed-off-by: Riccardo Mancini <[email protected]>
> ---
> tools/lib/perf/cpumap.c | 15 +++++++++++----
> 1 file changed, 11 insertions(+), 4 deletions(-)
>
> diff --git a/tools/lib/perf/cpumap.c b/tools/lib/perf/cpumap.c
> index ca0215047c326af4..fb633272be3aaed9 100644
> --- a/tools/lib/perf/cpumap.c
> +++ b/tools/lib/perf/cpumap.c
> @@ -265,11 +265,18 @@ 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, idx, cpu_at_idx;
>
> - for (i = 0; i < cpus->nr; ++i) {
> - if (cpus->map[i] == cpu)
> - return i;
> + while (low < high) {
> + idx = (low + high) / 2;
> + cpu_at_idx = cpus->map[idx];
> +
> + if (cpu_at_idx == cpu)
> + return idx;
> + else if (cpu_at_idx > cpu)
> + high = idx;
> + else
> + low = idx+1;
> }
>
> return -1;
> --
> 2.31.1

--

- Arnaldo

2021-10-08 14:31:22

by Arnaldo Carvalho de Melo

Subject: Re: [RFC PATCH v1 01/37] libperf cpumap: improve idx function

Em Sat, Aug 21, 2021 at 11:19:07AM +0200, Riccardo Mancini escreveu:
> >From commit 7074674e7338863e ("perf cpumap: Maintain cpumaps ordered
> and without dups"), perf_cpu_map elements are sorted in ascending order.
>
> This patch improves the perf_cpu_map__idx function by using a binary
> search.

Thanks, applied.

- Arnaldo


> Signed-off-by: Riccardo Mancini <[email protected]>
> ---
> tools/lib/perf/cpumap.c | 15 +++++++++++----
> 1 file changed, 11 insertions(+), 4 deletions(-)
>
> diff --git a/tools/lib/perf/cpumap.c b/tools/lib/perf/cpumap.c
> index ca0215047c326af4..fb633272be3aaed9 100644
> --- a/tools/lib/perf/cpumap.c
> +++ b/tools/lib/perf/cpumap.c
> @@ -265,11 +265,18 @@ 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, idx, cpu_at_idx;
>
> - for (i = 0; i < cpus->nr; ++i) {
> - if (cpus->map[i] == cpu)
> - return i;
> + while (low < high) {
> + idx = (low + high) / 2;
> + cpu_at_idx = cpus->map[idx];
> +
> + if (cpu_at_idx == cpu)
> + return idx;
> + else if (cpu_at_idx > cpu)
> + high = idx;
> + else
> + low = idx+1;
> }
>
> return -1;
> --
> 2.31.1

--

- Arnaldo