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.