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

Subject: Re: [boost] [poly_collection] Request for comments: fast polymorphic collections
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2016-11-15 12:38:36

Hi Joaquin,

> A couple of years ago I wrote two blog entries about high-performance
> data structures
> for polymorphic objects:

[snip]

> and I'd be very grateful if people could give their opinion on
> usefulness, design, etc.
> so as to determine potential interest in an eventual official submission
> to Boost.

A. This is very useful.

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 );

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

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.

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?

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?

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

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.