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 /include | |
| 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 'include')
| -rw-r--r-- | include/expression.h | 1 |
1 files changed, 1 insertions, 0 deletions
diff --git a/include/expression.h b/include/expression.h index 53194c92..cf7319b6 100644 --- a/include/expression.h +++ b/include/expression.h @@ -481,6 +481,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); |