Try to avoid some qsorts
Ian Rogers
reviewercover 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
Ian Rogers
reviewerPATCH 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
@@ -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
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.
Reported-by Matt Fleming <[email protected]>Signed-off-by Ian Rogers <[email protected]>--- 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.
Ian Rogers
reviewerPATCH 2/2 perf dsos: When adding a dso into sorted dsos maintain the sort order
In reply to Ian Rogersdsos__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
@@ -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
Re: [PATCH v1 2/2] perf dsos: When adding a dso into sorted dsos maintain the sort order
Quoted 8 lines · Ian Rogers
dsos__addwould add at the end of the dso array possibly requiring a later find to re-sort the array. Patterns of find then add were becomingO(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 theO(n*log n)sort.Reported-by Namhyung Kim <[email protected]>Signed-off-by Ian Rogers <[email protected]>
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@@ -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
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