[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <ZoXGr2skcDZTUb5U@google.com>
Date: Wed, 3 Jul 2024 14:46:23 -0700
From: Namhyung Kim <namhyung@...nel.org>
To: Ian Rogers <irogers@...gle.com>
Cc: Peter Zijlstra <peterz@...radead.org>, Ingo Molnar <mingo@...hat.com>,
Arnaldo Carvalho de Melo <acme@...nel.org>,
Mark Rutland <mark.rutland@....com>,
Alexander Shishkin <alexander.shishkin@...ux.intel.com>,
Jiri Olsa <jolsa@...nel.org>,
Adrian Hunter <adrian.hunter@...el.com>,
Kan Liang <kan.liang@...ux.intel.com>,
Athira Rajeev <atrajeev@...ux.vnet.ibm.com>,
linux-perf-users@...r.kernel.org, linux-kernel@...r.kernel.org,
Steinar Gunderson <sesse@...gle.com>,
Matt Fleming <matt@...dmodwrite.com>
Subject: Re: [PATCH v1 2/2] perf dsos: When adding a dso into sorted dsos
maintain the sort order
On Wed, Jul 03, 2024 at 10:21:17AM -0700, Ian Rogers wrote:
> dsos__add would add at the end of the dso array possibly requiring a
> later find to re-sort the array. Patterns of find then add were
> becoming O(n*log n) due to the sorts. Change the add routine to be
> O(n) rather than O(1) but to maintain the sorted-ness of the dsos
> array so that later finds don't need the O(n*log n) sort.
>
> Reported-by: Namhyung Kim <namhyung@...nel.org>
> Signed-off-by: Ian Rogers <irogers@...gle.com>
It works well for me too!
Tested-by: Namhyung Kim <namhyung@...nel.org>
Thanks,
Namhyung
> ---
> tools/perf/util/dsos.c | 26 +++++++++++++++++++++-----
> 1 file changed, 21 insertions(+), 5 deletions(-)
>
> diff --git a/tools/perf/util/dsos.c b/tools/perf/util/dsos.c
> index 5e5e05f86dd3..d4acdb37f046 100644
> --- a/tools/perf/util/dsos.c
> +++ b/tools/perf/util/dsos.c
> @@ -206,11 +206,27 @@ int __dsos__add(struct dsos *dsos, struct dso *dso)
> dsos->dsos = temp;
> dsos->allocated = to_allocate;
> }
> - dsos->dsos[dsos->cnt++] = dso__get(dso);
> - if (dsos->cnt >= 2 && dsos->sorted) {
> - dsos->sorted = dsos__cmp_long_name_id_short_name(&dsos->dsos[dsos->cnt - 2],
> - &dsos->dsos[dsos->cnt - 1])
> - <= 0;
> + if (!dsos->sorted) {
> + dsos->dsos[dsos->cnt++] = dso__get(dso);
> + } else {
> + int low = 0, high = dsos->cnt - 1;
> + int insert = dsos->cnt; /* Default to inserting at the end. */
> +
> + while (low <= high) {
> + int mid = low + (high - low) / 2;
> + int cmp = dsos__cmp_long_name_id_short_name(&dsos->dsos[mid], &dso);
> +
> + if (cmp < 0) {
> + low = mid + 1;
> + } else {
> + high = mid - 1;
> + insert = mid;
> + }
> + }
> + memmove(&dsos->dsos[insert + 1], &dsos->dsos[insert],
> + (dsos->cnt - insert) * sizeof(struct dso *));
> + dsos->cnt++;
> + dsos->dsos[insert] = dso__get(dso);
> }
> dso__set_dsos(dso, dsos);
> return 0;
> --
> 2.45.2.803.g4e1b14247a-goog
>
Powered by blists - more mailing lists