Re: [boost] [cpo-proposal] presentation of the idea

Subject: Re: [boost] [cpo-proposal] presentation of the idea
From: Santiago Tapia (santiago.tapia_at_[hidden])
Date: 2013-08-18 19:49:07

> Date: Fri, 16 Aug 2013 13:00:57 +0200
> From: Thorsten Ottosen <thorsten.ottosen_at_[hidden]>
>> int main(int argc, char** argv)
>> {
>>    classifier<base, std::allocator> collection;
>>
>>    collection.insert( derived_A(21) );
>>    collection.insert( derived_B(40) );
>>
>>    classifier<base, std::allocator>::iterator i, e = collection.end();
>>
>>    for ( i = collection.begin(); i != e; ++i )
>>    {
>>      const base& x = *i;
>>      std::cout << x.do_something(6) << std::endl;
>>    }
>>
>>    return 0;
>> }
>
> I would like to see the use of forwrding in-place construction:
>
>    collection.push_back<derived_A>( 21 );
>
> using variadic templates.

OK, I will try.

>
>> - The container's name is classifier because it classifies objects
>> internally using the RTTI.
>
> I had similar ideas that I wanted to implement. I didn't expect to use
> RTTI. Basically I wanted the class hierarchy's base class to derive from
> a class with pure virtual functions that allowed the container to
> perform the inplace-contruction, copying and alignment stuff.

I am trying to make the interface of the container as easy as possible.
I think using RTTI is an easy solution.

>
>> - The container classifier is _not_ a sequence.
>
> I would expect the container to allow forward iteration. I assume you
> mean that erase/insert into the middle is prohibited? I imagined that
> only push_back/pop_back was supported.
>
>> - 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. Then if the user wanted to sort or otherwise manipulate the
> sequence, he could just create an std::vector<T*> of the elements
> (Thus, push_back should probably return a pointer to the constructed
> element).

I am thinking about including that std:vector<T*> internally in
another container,
thus, I could provide a random access iterator. That could be
"sequence_classifier".

But I see a problem: if we only sort the vector<T*> then the objects in memory
of consecutive iterations will not be contigous in memory
and we will lose some of the cache efficiency.

I will try to provide another kind of iteration, actually a two-levels
iteration, like in
a matrix, in order to gain access to the vectors of objects. That way we might
sort objects of the same type without drawbacks.

>
> All in all, I hope you will persue this idea. I certainly have many
> use-cases for it in code where efficiency matters, and in code where
> using Boost.Intrusive is just must more work.
>
> kind regards
>
> Thorsten

> Date: Fri, 16 Aug 2013 19:20:36 -0500
> From: Larry Evans <cppljevans_at_[hidden]>

>> Yes, that is the idea. Actually, whether the implementation uses a collection
>> of vectors or other mechanism is an implementation detail. I use a map
>> of vectors in the classifier container, but I will try other implementations.
> Is the map key something like the type_info:
>
>   http://www.cplusplus.com/reference/typeinfo/

Yes, actually a wrapper of typeinfo because of a problem with typeinfo
I could not workaround. But that is an implementation detail, I mean,
that will be an inner detail of the library and I might find a better solution
without changing the interface of the classifier container.

>
> If there is a separate vector for each type, then the storage for a
> container containing more than one type can't be contiguous,
> since the vectors for the containers for the types cannot be
> contiguous, or am I missing something?  I think what Thorsten
> was aiming at in this post:
>
> http://article.gmane.org/gmane.comp.lib.boost.devel/243504

I could not follow the link... ?

>
> was each element in the container was truly contiguous.  IOW,
> given a container, c, then.
>
>   c.insert(T1());
>   c.insert(T2());
>
> The T1 inserted into c would be contigous with the T2.

No, in the prototype of the classifier T1 will not be contigous with T2,
but:

 c.insert(T2());
 c.insert(T2());

first object of T2 will be contigous with second object of T2.

>
> [snip]
>>> Date: Tue, 13 Aug 2013 23:33:25 +0400
>>> From: Andrey Semashev <andrey.semashev_at_[hidden]>
>>>>
>>>> - The container classifier is _not_ a sequence.
>>>
>>> Why? Is this intentional?
>>
>> Both intentional and accidental, because I want to allocate objects
>> contiguously in memory I have to store them in a collection of
>> vectors, the container is not a sequence but a collection of sequences,
>> one sequence for every class in the classifier.
>> I will implement a sequence, but later.
>>
>
> The above reinforces my above conclusion that T1 and T2 elements
> cannot be contiguous in the container.

A container might store T1 and T2 contigously, but up to now,
that is not my idea, because it is more difficult and I am not sure
about the efficiency of that alternative.
Actually, I have read somewhere that there is a cache memory
for functions, in that case, classifying the objects by type could be
a good implementation because the virtual methods could be stored
in the cache until the objects of that type were finished.

> Date: Sat, 17 Aug 2013 08:12:48 -0400
> From: Rob Stewart <robertstewart_at_[hidden]>
> To: "boost_at_[hidden]" <boost_at_[hidden]>
> Subject: Re: [boost] [cpo-proposal] presentation of the idea
>
> On Aug 16, 2013, at 9:21 AM, Santiago Tapia <santiago.tapia_at_[hidden]> wrote:
>
>>> Date: Tue, 13 Aug 2013 23:33:25 +0400
>>> From: Andrey Semashev <andrey.semashev_at_[hidden]>
>>>
>>>> - The allocator argument in the classifier will be applied to every object added to the classifier. Thus, the allocator is provided without its argument. The std::allocator is the default argument.
>>>
>>> You can use the standard interface for allocator rebinding:
>>>
>>> typedef allocator<T> allocator_T;
>>> typedef typename allocator_T::template rebind<U>::other allocator_U;
>>>
>>> You can use std::allocator<void> by default then.
>>
>> I am not sure how to do this. I need a allocator with a parameter in order to get: allocator<triangle>, allocator<square>, ... this allocator must be instantiated when an object of a new class is inserted in the classifier.
>
> That's the point of rebind. Starting with allocator<A>, you can get allocator<B>. The spelling of allocator<B> just looks odd:
>
> typename allocator<A> template ::rebind<B>::other
>
> ___
> Rob
>

Understood, thank you both for the comment.

> Date: Sat, 17 Aug 2013 09:20:14 -0500
> From: Larry Evans <cppljevans_at_[hidden]>
>
> The attached demonstrates, I believe, what Thorsten was aiming at
> an shows the storage of *different* types in contiguous storage.
>
> HTH.
>
>
> -regards,
> Larry
>
> -------------- next part --------------
> A non-text attachment was scrubbed...
> Name: align_in_buffer.cpp
> Type: text/x-c++src
> Size: 4402 bytes
> Desc: not available
> URL: <http://lists.boost.org/boost/attachments/20130817/7b23e93f/attachment.bin>
>

I can not find the attachment.

Anyway, I am not sure about the memory model. As I said in the first
version I will
choose contigous allocation for each type, that is, objects of same type will be
contigous and objects of different objects will not.
There are some reasons for that decision:
1) It is easier to implement.
2) I think it will more effective. Of course, that has to be proved.
3) Contigous storage for same type enables random access by index directly.

But if contigous storage of different types is better, I will switch
to it or provide
different containers using each memory model.

Finally, thank you all for your comments, I am going to pursue the idea, and
therefore I am going to concentrate on writing the documentation and finishing
the implementation of the containers.

Best regards,

   Santiago