On Wed, Jan 18, 2023 at 02:09:44PM +0100, Stefano Brivio wrote: > On Wed, 18 Jan 2023 12:14:14 +0100 > Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx> wrote: > > > ...instead of a tree descent, which became overly complicated in an > > attempt to cover cases where expired or inactive elements would affect > > comparisons with the new element being inserted. > > > > Further, it turned out that it's probably impossible to cover all those > > cases, as inactive nodes might entirely hide subtrees consisting of a > > complete interval plus a node that makes the current insertion not > > overlap. > > > > To speed up the overlap check, descent the tree to find a greater > > element that is closer to the key value to insert. Then walk down the > > node list for overlap detection. Starting the overlap check from > > rb_first() unconditionally is slow, it takes 10 times longer due to the > > full linear traversal of the list. > > > > Moreover, perform garbage collection of expired elements when walking > > down the node list to avoid bogus overlap reports. > > ...I'm quite convinced it's fine to perform the garbage collection > *after* we found the first element by descending the tree -- in the > worst case we include "too many" elements in the tree walk, but never > too little. With v4, "the worst case we include too many elements in the tree walk, but never too little" still stands. > Reviewed-by: Stefano Brivio <sbrivio@xxxxxxxxxx> So if you don't mind, I'll carry this tag on v4. Thanks.
