Re: [PATCH nf-next 0/3] netfilter: nft_set_rbtree: use cloned tree for insertions and removal

[Florian Westphal <fw@strlen.de>]

Phil Sutter <phil@nwl.cc> wrote:
> > 200K elements ~ avg. time insertion before 510ms after 744ms
> > 500K elements ~ avg. time insertion before 5460ms after 7730ms
> 
> I wonder if nft_rbtree_maybe_clone() could run a simpler copying
> algorithm than properly inserting every element from the old tree into
> the new one since the old tree is already correctly organized -
> basically leveraging the existing knowledge of every element's correct
> position.

Yes, but I doubt its going to help much.

And I don't see how this can be done without relying on implementation
details of rb_node struct.

> Or is there a need to traverse the new tree with each element instead of
> copying the whole thing as-is?

What do you mean?