Boost logo

Boost :

Subject: Re: [boost] [cpo-proposal] presentation of the idea
From: Larry Evans (cppljevans_at_[hidden])
Date: 2013-08-19 08:54:48


On 08/19/13 06:59, Thorsten Ottosen wrote:
> On 16-08-2013 15:33, Larry Evans wrote:
>> On 08/16/13 06:00, Thorsten Ottosen wrote:
>> [snip]
>>>> - The classifier uses continuous storage in memory for objects of the
>>>> same type, therefore it is expected to improve cache efficiency with
>>>> respect
>>>> to solutions that use pointers (and new to allocate objects),
>>>> especially if the
>>>> client code uses some cache-aware allocator.
>>>
>>> I wanted to call my class template polymorphic_vector, taking base class
>>> and allocator template arguments. I imagined that the storage
>>> would be completely contigious, even when many different types of
>>> objects where stored into the container. This would give maximum cache
>>> efficiency.
>>
>> Hi Thorsten,
>>
>> I'm curious how you'd be able to store different types in contiguous
>> storage. I would guess the base class would have to have a virtual
>> derived_alignof and derived_sizeof methods which would
>> return alignof(Derived) and sizeof(Derived), and then the container
>> would use placement new and these virtual functions and a
>> container_buffer type std::vector<char> to figure out where
>> to place the next element in the container_buffer?
>
> That sounds like the basic idea. Alignment may not be needed if we
> assume some kind of maximal alignment. Sizeof may not be needed either
> if the syntax for adding objects is
>
> cont.push_back<Derived>( x, y );
>

Using a templated push_back, IIUC, would require some sort of
container, such as std::vector<char> cont, which contains contigous
storage, and the push_back should find the next location, i_aligned,
in std::vector<char> which is at alignment, alignof(Derived).
and would then push_back i_aligned chars, then further push_back
sizeof(Derived) char's, the new inplace at cont.begin()+i_aligned.

Does that make sense?

>>
>> Since boost::fusion::vector<T1,T2,...,Tn> stores different
>> types, T1,T2,...,Tn in contiguous storage, I'm wondering
>> why not use boost::fusion::vector?
>
> So this vector has no requirement on the size of the container (at
> compile time)?

OOPS. IIUC, fusion::vector does require all types be known at compile
time.

>
> I guess fusion::vector uses some kind of variant storage approach?

No. fusion::vector uses the preprocessor to generate the code for a
struct something like:

  struct vectorN
  {
      T1 m1; T2 m2, ..., TN mN;
  };

You're probably wondering how that could be done with the preprocessor,
and I did have a look at how awhile back, but can't remember the
details now, other than it took a bit of work to understand.

> If
> so, a lot of space may be wasted if Derived1 is small and Derived2 is
> large.
>
> Also, We would really like not to have T1,T2,...,Tn to be complete types
> when using a polymorphic_vector, and we would really like not to
> mention all the potential types stored up front.

Ah! OK, I understand now. Thanks.

-regards,
Larry


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