Re: [ICL] Proposal to support other set/map implementations

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2021-09-14 16:52:05

Martin Duvanel wrote:
> We are using boost::icl::interval_set with very large amounts of 
> intervals, and we are having some performance issues.

That's not surprising. ICL uses the wrong data structures.

I refer to my review of the library from Feb 2010:

https://lists.boost.org/Archives/boost//2010/02/162198.php

(Note that at the time of its review it was called "ITL", not "ICL" -
knowing that makes searching the archive quicker!)

> Profiling showed that, in our use-case, a lot of time was spent 
> on memory allocation/deallocation,

Did you also find that the total required RAM was greater than
expected?

> and swapping std::set for boost::flat_set made a huge, positive 
> difference.

I would expect to get a constant-order improvement from using a
flat_set. To get a big-O improvement it needs a better data structure.

> We may have a very specific use-case, but would you consider a 
> small modification to the library inside "boost/icl/impl_config.hpp", 
> in order to open the door for other set/map implementations?

I don't think ICL gets much attention. You could try sending a patch to
its github page if you wanted.

Regards, Phil.