When adding element(s) to a non-empty set, code merged the two lists and
sorted the result. With many individual 'add element' commands this
causes substantial overhead. Make use of the fact that
existing_set->init is sorted already, sort only the list of new elements
and use list_splice_sorted() to merge the two sorted lists.
A test case adding ~25k elements in individual commands completes in
about 1/4th of the time with this patch applied.
Fixes: 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")
Signed-off-by: Phil Sutter <phil@xxxxxx>
---
include/expression.h | 1 +
src/intervals.c | 10 ++++++----
src/mergesort.c | 2 +-
3 files changed, 8 insertions(+), 5 deletions(-)
diff --git a/include/expression.h b/include/expression.h
index 2c3818e89b791..0f7ffb3a0a623 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -480,6 +480,7 @@ extern struct expr *compound_expr_alloc(const struct location *loc,
extern void compound_expr_add(struct expr *compound, struct expr *expr);
extern void compound_expr_remove(struct expr *compound, struct expr *expr);
extern void list_expr_sort(struct list_head *head);
+extern void list_splice_sorted(struct list_head *list, struct list_head *head);
extern struct expr *concat_expr_alloc(const struct location *loc);
diff --git a/src/intervals.c b/src/intervals.c
index bc414d6c87976..a18967ee21061 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -589,19 +589,21 @@ int set_overlap(struct list_head *msgs, struct set *set, struct expr *init)
struct expr *i, *n, *clone;
int err;
+ set_to_range(init);
+ list_expr_sort(&init->expressions);
+
if (existing_set) {
if (existing_set->init) {
- list_splice_init(&existing_set->init->expressions,
+ set_to_range(existing_set->init);
+ list_splice_sorted(&existing_set->init->expressions,
&init->expressions);
+ init_list_head(&existing_set->init->expressions);
} else {
existing_set->init = set_expr_alloc(&internal_location,
set);
}
}
- set_to_range(init);
- list_expr_sort(&init->expressions);
-
err = setelem_overlap(msgs, set, init);
list_for_each_entry_safe(i, n, &init->expressions, list) {
diff --git a/src/mergesort.c b/src/mergesort.c
index 8e6aac5fb24ed..dca71422dd947 100644
--- a/src/mergesort.c
+++ b/src/mergesort.c
@@ -70,7 +70,7 @@ static int expr_msort_cmp(const struct expr *e1, const struct expr *e2)
return ret;
}
-static void list_splice_sorted(struct list_head *list, struct list_head *head)
+void list_splice_sorted(struct list_head *list, struct list_head *head)
{
struct list_head *h = head->next;
struct list_head *l = list->next;
--
2.34.1
