Skip to contentSkip to conversation

Try to avoid some qsorts

PATCH Applied Ian Rogers 3 participants 6 messages Jul 3, 2024 – Jul 4, 2024 perf events

lore
Share & tools
lore

Ian Rogers

author reviewer
#0 lore raw

cover Try to avoid some qsorts

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/[email protected]/

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(-)
Signature · 1 line
2.45.2.803.g4e1b14247a-goog
author reviewer
#1 lore raw

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

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

---
 tools/perf/util/comm.c | 29 ++++++++++++++++++-----------
 1 file changed, 18 insertions(+), 11 deletions(-)
tools/perf/util/comm.c +18 -11
index 233f2b6edf52..49b79cf0c5cc 100644
@@ -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);
Signature · 1 line
2.45.2.803.g4e1b14247a-goog
Tested-by on v1 1/2
#2 lore raw

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

Quoted 8 lines · Ian Rogers

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

---
 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.

author reviewer
#3 lore raw

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

In reply to 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.

---
 tools/perf/util/dsos.c | 26 +++++++++++++++++++++-----
 1 file changed, 21 insertions(+), 5 deletions(-)
tools/perf/util/dsos.c +21 -5
index 5e5e05f86dd3..d4acdb37f046 100644
@@ -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;
Signature · 1 line
2.45.2.803.g4e1b14247a-goog
maintainer Tested-by on v1 2/2
#4 lore raw

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

Quoted 8 lines · 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.

It works well for me too!

Thanks,
Namhyung

Quoted 44 lines
---
 tools/perf/util/dsos.c | 26 +++++++++++++++++++++-----
 1 file changed, 21 insertions(+), 5 deletions(-)
tools/perf/util/dsos.c +21 -5
index 5e5e05f86dd3..d4acdb37f046 100644
@@ -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;
Signature · 1 line
2.45.2.803.g4e1b14247a-goog
maintainer Applied
#5 lore raw
In reply to Ian Rogers
Quoted 8 lines · 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/[email protected]/

[...]

Applied to perf-tools-next, thanks!

Best regards,
Namhyung