Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk