Re: [PATCH nft 2/2,v2] intervals: Do not sort cached set elements over and over again

[Pablo Neira Ayuso <pablo@netfilter.org>]

On Thu, Jun 23, 2022 at 06:25:35PM +0200, Phil Sutter wrote:
> On Thu, Jun 23, 2022 at 06:17:16PM +0200, Pablo Neira Ayuso wrote:
> > On Thu, Jun 23, 2022 at 06:05:20PM +0200, Phil Sutter wrote:
> > > On Thu, Jun 16, 2022 at 11:04:46AM +0200, Pablo Neira Ayuso wrote:
> > > > From: Phil Sutter <phil@nwl.cc>
> > > > 
> > > > 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>
> > > 
> > > Thanks for picking it up, I missed the automerge code being very
> > > similar.
> > > 
> > > I worked on a patch to move the whole set adjustment to a separate step
> > > after evaluating commands, but it's a bit larger effort as it requires
> > > to combine overlap detection, auto merge and element deletion. With
> > > simple appending new elements in eval phase and reacting upon
> > > EXPR_F_KERNEL and EXPR_F_REMOVE flags, I guess it's possible to update
> > > the whole set in one go.
> > 
> > You mean, appending if they come in order as in your test ruleset? Not
> > sure what you are suggesting.
> 
> It was merely loud thinking - combining repeated 'add element' commands
> is fine with me for avoiding the problem. I have an alternative in mind
> where added elements are appended to the set without EXPR_F_KERNEL and
> removed ones also with EXPR_F_REMOVE. So after nft_evaluate() one could
> do all the overlap detection / auto merging / element removing once for
> each changed set.

I have pushed out this coalesce approach to tackle this regression.
Feel free to revisit this approach.