[PATCH v1 0/2] Try to avoid some qsorts

[PATCH v1 0/2] Try to avoid some qsorts

[Ian Rogers]

Reference count checking doesn't work well with rbtree due to the need
for counts on each child and parent edge. As such the reference count
checking changes removed rbtree and replaced them with sorted
arrays. There have been instances where sorting has been shown to be a
regression:
https://lore.kernel.org/lkml/20240521165109.708593-1-irogers@google.com/

These patches address a further 2 cases in comm and dsos, avoiding a
sort when the array is already sorted at the cost of an O(n) memmove.

Ian Rogers (2):
  perf comm str: Avoid sort during insert
  perf dsos: When adding a dso into sorted dsos maintain the sort order

 tools/perf/util/comm.c | 29 ++++++++++++++++++-----------
 tools/perf/util/dsos.c | 26 +++++++++++++++++++++-----
 2 files changed, 39 insertions(+), 16 deletions(-)

-- 
2.45.2.803.g4e1b14247a-goog

[PATCH v1 1/2] perf comm str: Avoid sort during insert

[Ian Rogers]

The array is sorted, so just move the elements and insert in order.

Reported-by: Matt Fleming <matt@readmodwrite.com>
Signed-off-by: Ian Rogers <irogers@google.com>
---
 tools/perf/util/comm.c | 29 ++++++++++++++++++-----------
 1 file changed, 18 insertions(+), 11 deletions(-)

diff --git a/tools/perf/util/comm.c b/tools/perf/util/comm.c
index 233f2b6edf52..49b79cf0c5cc 100644
--- a/tools/perf/util/comm.c
+++ b/tools/perf/util/comm.c
@@ -86,14 +86,6 @@ static struct comm_str *comm_str__new(const char *str)
 	return result;
 }
 
-static int comm_str__cmp(const void *_lhs, const void *_rhs)
-{
-	const struct comm_str *lhs = *(const struct comm_str * const *)_lhs;
-	const struct comm_str *rhs = *(const struct comm_str * const *)_rhs;
-
-	return strcmp(comm_str__str(lhs), comm_str__str(rhs));
-}
-
 static int comm_str__search(const void *_key, const void *_member)
 {
 	const char *key = _key;
@@ -169,9 +161,24 @@ static struct comm_str *comm_strs__findnew(const char *str)
 		}
 		result = comm_str__new(str);
 		if (result) {
-			comm_strs->strs[comm_strs->num_strs++] = result;
-			qsort(comm_strs->strs, comm_strs->num_strs, sizeof(struct comm_str *),
-			      comm_str__cmp);
+			int low = 0, high = comm_strs->num_strs - 1;
+			int insert = comm_strs->num_strs; /* Default to inserting at the end. */
+
+			while (low <= high) {
+				int mid = low + (high - low) / 2;
+				int cmp = strcmp(comm_str__str(comm_strs->strs[mid]), str);
+
+				if (cmp < 0) {
+					low = mid + 1;
+				} else {
+					high = mid - 1;
+					insert = mid;
+				}
+			}
+			memmove(&comm_strs->strs[insert + 1], &comm_strs->strs[insert],
+				(comm_strs->num_strs - insert) * sizeof(struct comm_str *));
+			comm_strs->num_strs++;
+			comm_strs->strs[insert] = result;
 		}
 	}
 	up_write(&comm_strs->lock);
-- 
2.45.2.803.g4e1b14247a-goog

[PATCH v1 2/2] perf dsos: When adding a dso into sorted dsos maintain the sort order

[Ian Rogers]

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@kernel.org>
Signed-off-by: Ian Rogers <irogers@google.com>
---
 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

Re: [PATCH v1 1/2] perf comm str: Avoid sort during insert

[Matt Fleming]

On Wed, Jul 3, 2024 at 6:21 PM Ian Rogers <irogers@google.com> wrote:
>
> The array is sorted, so just move the elements and insert in order.
>
> Reported-by: Matt Fleming <matt@readmodwrite.com>
> Signed-off-by: Ian Rogers <irogers@google.com>
> ---
>  tools/perf/util/comm.c | 29 ++++++++++++++++++-----------
>  1 file changed, 18 insertions(+), 11 deletions(-)

Thanks, this fixes the issue I had where perf-top would spend >40% of
its time sorting comm_strs.

Tested-by: Matt Fleming <matt@readmodwrite.com>

Re: [PATCH v1 2/2] perf dsos: When adding a dso into sorted dsos maintain the sort order

[Namhyung Kim]

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@kernel.org>
> Signed-off-by: Ian Rogers <irogers@google.com>

It works well for me too!

Tested-by: Namhyung Kim <namhyung@kernel.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
> 

Re: [PATCH v1 0/2] Try to avoid some qsorts

[Namhyung Kim]

On Wed, 03 Jul 2024 10:21:15 -0700, Ian Rogers wrote:

> Reference count checking doesn't work well with rbtree due to the need
> for counts on each child and parent edge. As such the reference count
> checking changes removed rbtree and replaced them with sorted
> arrays. There have been instances where sorting has been shown to be a
> regression:
> https://lore.kernel.org/lkml/20240521165109.708593-1-irogers@google.com/
> 
> [...]

Applied to perf-tools-next, thanks!

Best regards,
Namhyung