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/optimize.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/optimize.c')
0 files changed, 0 insertions, 0 deletions