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-15 17:53:10

El 15/11/2016 a las 18:38, Thorsten Ottosen escribió:
> Hi Joaquin,
>
> [...]
>
> A. This is very useful.

Thanks! Glad you find it interesting.

> B. I'm still wondering if requirering copyability is a good thing. 
> After all, references and pointers may be used elsewere in the program 
> where copying is really not a good idea. Could it make sense to have a 
> variation of cloneable:
>
>   void clone( void* storage ) const;
>
> // essentially a call to protected or private copy-constructor:
> //   new(storage) T( *this )
>
> which is then used internally when copying is needed? And when no 
> copying is needed, the container is not copyable. To insert elements 
> that are not copyable we would just use emplace with a type argument:
>
>   coll.emplace<derived>( x, y );

Strictly speaking, copyability is not required, but as concrete types 
are stored in rellocatable vectors they must be verify the following:

* be MoveConstructible,
* be Moveassignable or have a noexcept move constructor.

Otherwise, segments wouldn't be able to grow beyond its initial capacity.

As for your clone() proposal, I fail to see why this is preferrable to 
simply requiring (move/copy) constructibility. Please note that 
moving/copying in Boost.PolyCollection happens in a non-virtual 
environment, so we don't need the virtual-enabled clone mechanism as 
envisioned in the Clonable concept of Boost.PtrContainer. Please correct 
me if I'm missing your point.

> C. perhap some range versions of local iterators would be nice?

Care to elaborate? I've basically replicated the usual interface of 
standard containers, of course open to consider justified improvements 
on that.

> D. I don't get the use of numeric_limits<T>::max() for capacity of an 
> empty container. I would be perfectly happy with 0 unless there is 
> something we cannot do with that definition.

Not a strong opinon on that. Having capacity()==infinite for a 
segment-less collection makes sense from a mathematical point of view, 
but other than that 0 could work equally well. If this eventually make 
it into an official proposal I'd adopt whatever the community thinks 
makes the most sense.

> E. Boost.PtrContainer does not throw exception when a container cannot 
> be cloned or compared. Maybe its must be possible to get compile 
> errors here too?

I've re-read Boost.PtrContainer docs and seems like the containers 
require Base to be clonable, which is tantamount to requiring 
copyability for all derived classes in Boost.PolyCollection. Am I wrong 
here? What's the behavior if a Base is not clonable?

> F. when using type restitution for base_collection, could it no make 
> sense to provide
>
> struct visitor
> {
>     void operator()( const auto& s ) const
>     { s.render(std::cout); }
>     void operator()( const warrior& w ) const
>     { w.warrior::render(std::cout); }
>     // etc for remaining types
> } ;
>
>
> that is, would that not guarantee devirtualization?

Very good observation. Yes, that would force devirtualization. The thing 
can be packed into something more generic:

     template<typename F1,typename F2>struct overload_class:F1,F2
     {
       overload_class(const F1& f1,const F2& f2):F1{f1},F2{f2}{}
       using F1::operator();
       using F2::operator();
     };

     template<typename F1,typename F2>auto overload(const F1& f1,const 
F2& f2)
     {
       return overload_class<F1,F2>{f1,f2};
     }

     auto render=overload(
       [](const sprite& s){
         s.render(std::cout);
       },
       [](const auto& s){
         using derived=typename std::decay<decltype(s)>::type;
         s.derived::render(std::cout);
       }
     );

Where the overload for const sprite& is needed because the other 
overload would try to get a reference to the pure virtual sprite::render 
member function. This probably deserves a mention in the docs.

> G. The performance results are very impressive; do that carry over to 
> 100 elements?

Looks like it does; results for n=100-1000, Visual C++ 2015 in 32-bit 
(x86) release mode, Windows 7 64-bit, Intel Core i5-2520M @2.5GHz:

for_each:
n;ptr_vector;sorted ptr_vector;shuffled 
ptr_vector;base_collection;base_collection 
(poly::for_each);base_collection (restituted poly::for_each)
100;72.2216;37.1035;102.137;49.8478;46.7159;55.0599
200;61.3873;30.4139;82.3211;44.2409;36.4579;38.5366
310;60.4311;29.1478;84.326;41.6049;32.6577;33.1415
430;59.3126;27.9782;82.6663;39.8802;31.4011;31.8698
560;59.4073;27.3143;79.945;38.9328;30.5108;30.6352
710;59.9286;27.1021;80.2318;37.589;29.7589;29.3414
870;59.6583;28.0717;79.1177;37.927;28.6542;29.1687
1045;59.1093;26.5752;77.692;37.973;28.2845;27.938

> I have sometimes though that my best choice would be poly_vector<base> 
> where everything is stored in one big chunk of memory, but I guess the
> type restitution can make up for that.
>
> Nice work!
>
> kind regards
>
> Thorsten
>
> PS: the upcomming Boost.DoubleEnded has a new deque class that exposes 
> segmented iterations. I'm wondering if the algorithms that you have 
> made can be reused for that data structure. 

Not directly so, as the mechanisms for getting a segment iterator from a 
global iterator are Boost.PolyCollection-specific, and type restitution 
makes no sense for Boost.DoubleEnded. But the algorithmic part (some of 
which is not trivial) can be certainly taken as an inspiration for 
Boost.DoubleEnded, and it might be conceivable to factor everything out 
to a Boost.SegmentedAlgorithm proposal or something.

Best,

Joaquín M López Muñoz