[ICL] Proposal to support other set/map implementations
Hello,
We are using boost::icl::interval_set with very large amounts of intervals, and we are having some performance issues.
Profiling showed that, in our use-case, a lot of time was spent on memory allocation/deallocation, and swapping std::set for boost::flat_set made a huge, positive difference.
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?
Here is the simple change we made to "boost/icl/impl_config.hpp" for this experiment:
<code>
#if defined(ICL_USE_BOOST_MOVE_IMPLEMENTATION)
# define ICL_IMPL_SPACE boost::container
#elif defined(ICL_USE_STD_IMPLEMENTATION)
# define ICL_IMPL_SPACE std
+ #elif defined(ICL_USE_CUSTOM_IMPLEMENTATION)
+ # define ICL_IMPL_SPACE ICL_CUSTOM_IMPL_SPACE
#else
# define ICL_IMPL_SPACE std
#endif
</code>
And then declaring the following before including:
<code>
namespace custom_icl
{
template
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.
On Wed, Sep 8, 2021 at 1:50 PM Martin Duvanel via Boost < boost@lists.boost.org> wrote:
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 am unrelated to ICL, but I do not thing this is such a small change, if they would allow flat_* containers with O(n) insert time then they would probably need to update all the docs to specify complexity in terms of underlying container complexity, or just add an ugly hack to docs that notes that if you use your own container that then all complexity guarantees in docs are off. https://www.boost.org/doc/libs/1_64_0/libs/icl/doc/html/boost_icl/function_r... Also out of curiosity: did you try out the google abseil b-tree https://abseil.io/blog/20190812-btree?
Ivan Matek wrote:
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 am unrelated to ICL, but I do not thing this is such a small change, if they would allow flat_* containers with O(n) insert time then they would probably need to update all the docs to specify complexity in terms of underlying container complexity, or just add an ugly hack to docs that notes that if you use your own container that then all complexity guarantees in docs are off. https://www.boost.org/doc/libs/1_64_0/libs/icl/doc/html/boost_icl/function_r...
That's a very good point, so much for the small patch then.
Also out of curiosity: did you try out the[google abseil b-tree](https://abseil.io/blog/20190812-btree)?
No we did not, but it may be worth trying it out too, thanks for the advice. Since our use-case revolves mostly around creating big interval sets, then adding, subtracting or traversing them (think selecting millions of items among billions of them, and adjusting that selection), the lesser memory footprint and increased cache-friendliness are good arguments. In the end we will probably end up rewriting something more suited to our needs. ICL provided a quick and easy way to implement it, but not optimised given the scale we use it at. Thank you for the feedback! Best regards, Martin
On Sat, Sep 18, 2021 at 3:02 PM Martin Duvanel
No we did not, but it may be worth trying it out too, thanks for the advice.
If you have blog/twitter feel free to share experiences if you try it out, I am curious how it behaves IRL.
In the end we will probably end up rewriting something more suited to our needs. ICL provided a quick and easy way to implement it, but not optimised given the scale we use it at.
That is a bit of a shame, but at least ICL gave you nice way to quickly verify design works.
participants (3)
-
Ivan Matek
-
Martin Duvanel
-
Phil Endecott