On Thu, Jun 16, 2022 at 11:04:46AM +0200, Pablo Neira Ayuso wrote:
> From: Phil Sutter <phil@xxxxxx>
>
> 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@xxxxxx>
> Signed-off-by: Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx>
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.
Cheers, Phil
