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-30 11:10:04

On 23-11-2016 21:19, Joaquin M López Muñoz wrote:
> El 23/11/2016 a las 18:23, Thorsten Ottosen escribió:
>> On 19-11-2016 10:09, Joaquin M López Muñoz wrote:
>>

>> I can't see how that is useful for much.
>>
>
> Re-thinking this, seems to me that the main use case of capacity() for a
> regular container like std::vector is in the expression
>
> X = v.capacity()-v.size()
>
> to calculate how many more insertions can one make without reallocation.
> Maybe we can define capacity() in Boost.PolyCollection to allow for the
> same use case: if we denote by si, ci the sizes and capacities of the
> different elements i=0,1,... then the equivalent expression for X taking
> into consideration only registered types and assuming the worst case
> (all insertions happen in the segment with the least unused capacity) is
>
> X = min{ci-si} = min{c1-si} + (s0+s1+...) - (s0+s1+...) = min{c1-si} +
> (s0+s1+...) - v.size()
>
> which leads to v.capacity() being defined as
>
> min{c1-si} + (s0+s1+...)
>
> i.e. the size of the entire collection plus the minimum *unused*
> capacity. Maybe this is too weird. Maybe we should drop capacity()
> altogether (not the sector-specific versions, of course).

That's not entirely wierd (if stated in the short words), but I'm 
leaning towards dropping it would be best.

>> Here are some design questions:

>> B. If I call shrink_to_fit on an container with empty segements, does
>> it end up with no segments?
>
> No. The only way to remove a segment from a collection p is to assign it
> a different collection q (without that segment), swap it or move it (in
> whch case all segments are gone).
> Again, my thinking is that having empty segments is a good thing in as
> much as this is tied to the fact that the associated types are
> registered into the collection. For that reason, the lib does nothing in
> particular to remove empty segments.

fair enough.

>> C. Could the segment type be a template argument, or is there good
>> reasons for not dong that?
>
> Like replacing std::vector with some other contiguous-memory container?
> This can certainly be done but I fail to see any reasonable use case for
> that. Also, the library is extremely sensitve to the requirements
> imposed on stored concrete types (moevability etc.) which are precisely
> coded for std::vector but may dffer wildly for other vector-like
> containers.

The downside of using std::vector is then that you are stuck with that 
behavior, and that the behavior is different on different platforms. 
E.g., a resize may double the capacity or grow by 50% etc. This may be 
fine for vector, but could hurt a little more here.

I certainly have class hierarchies where the size of some classes is 
very small and for others it is an order of magnitude larger.

Doing

   coll.reserve( x );

then potentially ends up eating much more memory then the normal vector 
case. Maybe we should only have reserve for specific types?

kind regards

Thorsten