intervals: Do not sort cached set elements over and over again
Phil Sutter
reviewerPATCH 1/1 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.
A test case adding ~25k elements in individual commands completes in about 1/4th of the time with this patch applied.
--- include/expression.h | 1 + src/intervals.c | 10 ++++++---- src/mergesort.c | 2 +- 3 files changed, 8 insertions(+), 5 deletions(-)
include/expression.h +1 -0
@@ -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);
src/intervals.c +6 -4
@@ -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) {
src/mergesort.c +1 -1
@@ -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;
Signature · 1 line
2.34.1
Pablo Neira Ayuso
maintainerQuoted 8 lines · Phil Sutter
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->initis sorted already, sort only the list of new elements and uselist_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.
Good.
Do you still like the idea of coalescing set element commands whenever possible?
https://patchwork.ozlabs.org/project/netfilter-devel/patch/[email protected]/
Thanks.
Quoted 66 lines
Fixes 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")Signed-off-by Phil Sutter <[email protected]>--- include/expression.h | 1 + src/intervals.c | 10 ++++++---- src/mergesort.c | 2 +- 3 files changed, 8 insertions(+), 5 deletions(-)include/expression.h +1
-0@@ -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);src/intervals.c +6
-4@@ -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) {src/mergesort.c +1
-1@@ -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;Signature · 1 line
2.34.1
Phil Sutter
reviewerQuoted 7 lines · Pablo Neira Ayuso
Quoted 6 lines · Phil Sutter
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->initis sorted already, sort only the list of new elements and uselist_splice_sorted()to merge the two sorted lists.
Quoted 7 lines
Quoted 2 lines
A test case adding ~25k elements in individual commands completes in about 1/4th of the time with this patch applied.
Good.
Do you still like the idea of coalescing set element commands whenever possible?
Does it mess with error reporting? If not, I don't see a downside of doing it.
With regards to the problem at hand, it seems like a feature to escape the actual problem. Please keep in mind that my patch's improvement from ~4min down to ~1min is pretty lousy given that v1.0.1 completed the same task in 0.3s.
IMHO the whole overlap detection/auto merging should happen as commit preparation and not per command.
Cheers, Phil
Pablo Neira Ayuso
maintainerQuoted 16 lines · Phil Sutter
Quoted 7 lines · Pablo Neira Ayuso
Quoted 6 lines · Phil Sutter
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->initis sorted already, sort only the list of new elements and uselist_splice_sorted()to merge the two sorted lists.Quoted 7 lines
Quoted 2 lines
A test case adding ~25k elements in individual commands completes in about 1/4th of the time with this patch applied.
Good.
Do you still like the idea of coalescing set element commands whenever possible?
Quoted 7 lines
Does it mess with error reporting? If not, I don't see a downside of doing it.
With regards to the problem at hand, it seems like a feature to escape the actual problem. Please keep in mind that my patch's improvement from ~4min down to ~1min is pretty lousy given that v1.0.1 completed the same task in 0.3s.
I running this comparison between 1.0.1:
# nft -v nftables v1.0.1 (Fearless Fosdick #3) # nft -f dump_sep.nft
real 0m3,867s user 0m3,651s sys 0m0,219s
and current 1.0.4 plus pending patches in patchwork:
# nft -v nftables v1.0.4 (Lester Gooch #3) # nft -f dump_sep.nft
real 0m3,867s user 0m3,677s sys 0m0,190s
For the record, this dump_sep.nft (that you sent me) looks like this:
# cat dump_sep.nft
add table t
add set t s { type ipv4_addr; flags interval; }
add element t s { 1.0.1.0/24 }
add element t s { 1.0.2.0/23 }
[...] more single command to add element [...]Quoted 2 lines
IMHO the whole overlap detection/auto merging should happen as commit preparation and not per command.
Then, this needs to coalesce the commands that update a single set at a later stage, in such commit preparation phase.
This code also has to deal with deletions coming in the same batch, which might be happening per command, by a robot generated batch.
Userspace overlap detection is only required by kernels <= 5.7, so this check could be removed.
For automerging, I don't think I can escape tracking each command to update the userspace set cache and adjust the existing ranges accordingly.