diff options
author | Phil Sutter <phil@nwl.cc> | 2022-06-16 10:56:12 +0200 |
---|---|---|
committer | Pablo Neira Ayuso <pablo@netfilter.org> | 2022-06-19 00:55:20 +0200 |
commit | 59e3a59221fb81c289a0868a85140dd452fb1c30 (patch) | |
tree | 6b58eb03b8ed11a1448405b0369d835b2b28071d /src/mergesort.c | |
parent | d434de8b50dcf3f5f4ca027e122a7df9d4e5d8e1 (diff) |
intervals: Do not sort cached set elements over and over again
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.
Add set_sort_splice() and use it for set element overlap detection and
automerge.
A test case adding ~25k elements in individual commands completes in
about 1/4th of the time with this patch applied.
Joint work with Pablo.
Fixes: 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")
Signed-off-by: Phil Sutter <phil@nwl.cc>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Diffstat (limited to 'src/mergesort.c')
-rw-r--r-- | src/mergesort.c | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/src/mergesort.c b/src/mergesort.c index 8e6aac5f..dca71422 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; |