Re: [boost] [poly_collection] Request for comments: fast polymorphic collections

Subject: Re: [boost] [poly_collection] Request for comments: fast polymorphic collections
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2016-11-07 07:37:26

El 07/11/2016 a las 12:04, Dominique Devienne escribió:
> On Sun, Nov 6, 2016 at 1:25 PM, Joaquin M López Muñoz <
> joaquinlopezmunoz_at_[hidden]> wrote:
>
>> [...]
>>
>> https://github.com/joaquintides/poly_collection
>>
>> [...]
> Sounds great Joaquin. But what if I need the equivalent of Multi-Index?
>
> I have several indexes on the base interface (ByGuid unique, ByNKey unique,
> ByParent non-unique, ByType non-unique, etc...), so  am I stuck into
> heap-based
> classic OOP because I need those?

I'm afraid Boost.MultiIndex forces you to lose memory contiguity just as 
is the case
for non-OOP scenarios (boost::multi_index_container is node-based). I 
haven't though
of smart ways to combine (candidate) Boost.PolyCollection and 
Boost.MultiIndex, I guess
a boost::multi_index_container of references to boost::base_collection 
elements is
the closest you can get both worlds together without further development 
in any of the
libs.

> Also, you provide "by *concrete* type" access to a segment, but often time
> we're also interested
> in "by *abstract* base" access/traversal, the base not necessarily being
> the one from the container itself.
> Any thoughts on that? Of course, you can't do "isAssigneableFrom()" tests
> using just std::typeid(),
> so a custom RTTI mechanism is necessary, but implicit traversal of all the
> "derived" segments for
> any particular abstract type would be really useful IMHO.

This can be done relatively easily:

   #include <boost/poly_collection/base_collection.hpp>
   #include <iostream>

   struct base
   {
     virtual ~base()=default;
   };

   struct derived1:base{};

   struct base1:base
   {
     virtual void display()const=0;
   };

   struct derived2:base1
   {
     virtual void display()const{std::cout<<"derived2\n";}
   };

   struct derived3:base1
   {
     virtual void display()const{std::cout<<"derived3\n";}
   };

   template<typename SubBase,typename BaseCollection,typename Function>
   Function for_each_subbase(BaseCollection&& c,Function f)
   {
     using subbase_type=typename std::conditional<
       std::is_const<
         typename std::remove_reference<BaseCollection>::type
       >::value,
       const SubBase,SubBase
     >::type;

     for(auto s:c.segment_traversal()){
       if(s.begin()==s.end()||
!dynamic_cast<subbase_type*>(&(*s.begin())))continue;
       for(auto& x:s)f(static_cast<subbase_type&>(x));
     }
     return std::move(f);
   }

   int main()
   {
     boost::base_collection<base> c;
     c.insert(derived1{});
     c.insert(derived2{});
     c.insert(derived3{});
     for_each_subbase<base1>(c,[](auto& x){x.display();});
   }

Note this scheme is pretty efficient as dynamic_cast is invoked just *once*
per segment. A more refined version of this idea based on a general concept
of dynamic subtyping could potentially be added to the library.

> Finally, can you share any compile-time impact, between you any_... and
> poly_... benchmarks for example?

I haven't measured compile times, but the library feels very light (for 
instance, on
my i5_at_2.5Ghz machine the code above compiles in less than 3s). If you have
any specific. If you have any specific scenario in mind I'd be happy to 
benchmark
it more rigorously.

> Thanks,  --DD
>
> PS: Would VS2013 work with it too? I'm currently stuck with that one...

A cursory look at

https://msdn.microsoft.com/en-us/library/hh567368.aspx

shows that at least one necessary feature (noexcept) is missing in 
VS2013, so the
short answer is no. noexcept can be easily backported with 
BOOST_NOEXCEPT, but
of course other details might be lurking... If you want to give a try 
please contact me
back.

Joaquín M López Muñoz