Review Request: poly_collection

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Review Request: poly_collection

Boost - Dev mailing list
Hello,

I'd like to ask for formal review of (candidate) Boost.PolyCollection, a
library providing
fast containers of polymorphic objects:

https://github.com/joaquintides/poly_collection
http://blincubator.com/bi_library/polycollection/?gform_post_id=1643
http://rawgit.com/joaquintides/poly_collection/website/doc/html/index.html

Typically, polymorphic objects cannot be stored directly in regular
containers and need
be accessed through an indirection pointer, which introduces performance
problems
related to CPU caching and branch prediction. Boost.PolyCollection
implements a novel
data structure that is able to contiguously store polymorphic objects
without such
indirection, thus providing a value-semantics user interface and better
performance.
Three polymorphic collections are provided:

* boost::base_collection
* boost::function_collection
* boost::any_collection

dealing respectively with classic base/derived or OOP polymorphism, function
wrapping in the spirit of std::function and so-called duck typing as
implemented by
Boost.TypeErasure.

The library compiles and runs succesfully in Visual Studio 2015, GCC
5.2.1 and
Clang 3.7. Ion Gaztañaga has kindly volunteered to act as the review
manager for
(candidate) Boost.PolyCollection.

Best regards,

Joaquín M López Muñoz


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Review Request: poly_collection

Boost - Dev mailing list
Le 01/03/2017 à 09:32, Joaquin M López Muñoz via Boost a écrit :

> Hello,
>
> I'd like to ask for formal review of (candidate) Boost.PolyCollection,
> a library providing
> fast containers of polymorphic objects:
>
> https://github.com/joaquintides/poly_collection
> http://blincubator.com/bi_library/polycollection/?gform_post_id=1643
> http://rawgit.com/joaquintides/poly_collection/website/doc/html/index.html 
>
>
> Typically, polymorphic objects cannot be stored directly in regular
> containers and need
> be accessed through an indirection pointer, which introduces
> performance problems
> related to CPU caching and branch prediction. Boost.PolyCollection
> implements a novel
> data structure that is able to contiguously store polymorphic objects
> without such
> indirection, thus providing a value-semantics user interface and
> better performance.
> Three polymorphic collections are provided:
>
> * boost::base_collection
> * boost::function_collection
> * boost::any_collection
>
> dealing respectively with classic base/derived or OOP polymorphism,
> function
> wrapping in the spirit of std::function and so-called duck typing as
> implemented by
> Boost.TypeErasure.
>
> The library compiles and runs succesfully in Visual Studio 2015, GCC
> 5.2.1 and
> Clang 3.7. Ion Gaztañaga has kindly volunteered to act as the review
> manager for
> (candidate) Boost.PolyCollection.
Hi,

thanks for proposing this library Joaquîn.


I've surely missed why base_collection is named this way. Is it because
the parameter is a base class. Could you confirm?

On the documentation you compare

     base_collection<T> and ptr_vector<T>

     function_collection<T()> and vector<function<T(U)>>

     any_collection<Concept> and vector< |type_erasure::|any<Concept>>

wondering if a single class with specializations wouldn't help

     collection<polymorphic<T>>
     collection<function<T(U)>>
     collection<any<Concept>>


In this way we could have

     collection<Model, Allocator>

BTW, I see that you have in the implementation a
detail::poly_collection<Model, Allocator> that is the base of the 3
collections.

In your blog there were some comments about a collection of variants.
Have you considered adding a variant_collection<Ts...>

This collection could support ordering and hash. In addition, it could
be preregistered.

As the collections are closer to multisets (unordered/not-hash), maybe
it is worth using this name.

Have you think about using the same design for maps/unordered maps of
polymorphic objet (where the key is not polymorphic)?

There is a C++ proposal for a polymorphic_value
(https://github.com/jbcoe/polymorphic_value/blob/master/draft.md). Your
base_collection<T> corresponds quite well to this polymorphic_value<T>,
isn't it?
Maybe polymorphic_collection<T> or collection<polymorphic<T>>
The main difference is the memory management, polymorphic_value can be
adapted to use an Allocator.

What are the function types passed to for_each whee we have a
function_collection or a any_collection? Is a reference to the
|value_type? |Do we need generic lambdas?



Best,
Vicente


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Review Request: poly_collection

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Hi,

I have added PolyCollection to the review schedule.

Best,
Ron

> On Mar 1, 2017, at 12:32 AM, Joaquin M López Muñoz via Boost <[hidden email]> wrote:
>
> Hello,
>
> I'd like to ask for formal review of (candidate) Boost.PolyCollection, a library providing
> fast containers of polymorphic objects:
>
> https://github.com/joaquintides/poly_collection
> http://blincubator.com/bi_library/polycollection/?gform_post_id=1643
> http://rawgit.com/joaquintides/poly_collection/website/doc/html/index.html
>
> Typically, polymorphic objects cannot be stored directly in regular containers and need
> be accessed through an indirection pointer, which introduces performance problems
> related to CPU caching and branch prediction. Boost.PolyCollection implements a novel
> data structure that is able to contiguously store polymorphic objects without such
> indirection, thus providing a value-semantics user interface and better performance.
> Three polymorphic collections are provided:
>
> * boost::base_collection
> * boost::function_collection
> * boost::any_collection
>
> dealing respectively with classic base/derived or OOP polymorphism, function
> wrapping in the spirit of std::function and so-called duck typing as implemented by
> Boost.TypeErasure.
>
> The library compiles and runs succesfully in Visual Studio 2015, GCC 5.2.1 and
> Clang 3.7. Ion Gaztañaga has kindly volunteered to act as the review manager for
> (candidate) Boost.PolyCollection.
>
> Best regards,
>
> Joaquín M López Muñoz
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Review Request: poly_collection

Boost - Dev mailing list
El 02/03/2017 a las 7:41, Ronald Garcia via Boost escribió:
> Hi,
>
> I have added PolyCollection to the review schedule.

Hi Ron,

Please note we already have a Review Manager volunteer for this (Ion
Gaztañaga).

Thank you,

Joaquín M López Muñoz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Review Request: poly_collection

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
El 01/03/2017 a las 23:15, Vicente J. Botet Escriba escribió:
> Le 01/03/2017 à 09:32, Joaquin M López Muñoz via Boost a écrit :
>> Hello,
>>
>> I'd like to ask for formal review of (candidate) Boost.PolyCollection
>> [...]
>
> Hi,
>
> thanks for proposing this library Joaquîn.

Hi Vicente, thanks for your interest.

> I've surely missed why base_collection is named this way. Is it
> because the parameter is a base class. Could you confirm?

Exactly. base_collection<Base> pretty much behaves as a container of
Base objects.

> wondering if a single class with specializations wouldn't help
>
>     collection<polymorphic<T>>
>     collection<function<T(U)>>
>     collection<any<Concept>>
>
> In this way we could have
>
>     collection<Model, Allocator>
>
> BTW, I see that you have in the implementation a
> detail::poly_collection<Model, Allocator> that is the base of the 3
> collections.

This is mostly a naming issue. Indeed the three collections derive from
the same
implementation and could be publicly provided as specializations of the
same class,
if this is what reviewers lean towards. Personally I like it better to
keep names
separated as in the current proposal.

> In your blog there were some comments about a collection of variants.
> Have you considered adding a variant_collection<Ts...>

I've thought about it. Such a collection would deviate from the others
both in terms
of its interface (no type registration, for instance) and implementation
--the data
structure detail::poly_collection relies on could be used to support
variants, but
more efficient implementations exist for this particular case.

> As the collections are closer to multisets (unordered/not-hash), maybe
> it is worth using this name.

I'd say similarities with unordered_multiset are superficial (segments
resemble
buckets) and the interfaces ultimately are too different. I chose
"collection" because
the term is not overloaded in the STL or Boost.

> Have you think about using the same design for maps/unordered maps of
> polymorphic objet (where the key is not polymorphic)?

Same-type contiguity is an essential feature of PolyCollection: I fail
to see how this
could be preserved for an associative container. Care to elaborate?

> There is a C++ proposal for a polymorphic_value
> (https://github.com/jbcoe/polymorphic_value/blob/master/draft.md).
> Your base_collection<T> corresponds quite well to this
> polymorphic_value<T>, isn't it?
> Maybe polymorphic_collection<T> or collection<polymorphic<T>>
> The main difference is the memory management, polymorphic_value can be
> adapted to use an Allocator.

base_collection<T> behaves approximately as a
std::vector<polymorphic_value<T>>,
the crucial difference being that the former groups elements by concrete
type in
contiguous chunks of memory, while the latter holds indirection pointers
behind the
scenes, so there is no real memory contiguity.

> What are the function types passed to for_each whee we have a
> function_collection or a any_collection? Is a reference to the
> |value_type? |Do we need generic lambdas?

These functions are passed a (const) value_type&, where

value_type=function_collection_value_type<Sig>  for
function_collection<Sig>,
value_type=any_collection_value_type<Concept>  for any_collection<Concept>

(see http://tinyurl.com/hmywnea , http://tinyurl.com/zh9ugl8 ). Now,
when type
restitution is used (http://tinyurl.com/gopdpuz ), and only then, the
functions are
passed a (const) Ti& for each of the restituted types Ti: in this case,
a generic lambda
is a very convenient way of taking advantage of this, but you can also
resort to a
polymorphic functor if you wish.

Best,

Joaquín M López Muñoz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Review Request: poly_collection

Boost - Dev mailing list
Le 02/03/2017 à 10:41, Joaquin M López Muñoz via Boost a écrit :

> El 01/03/2017 a las 23:15, Vicente J. Botet Escriba escribió:
>> Le 01/03/2017 à 09:32, Joaquin M López Muñoz via Boost a écrit :
>>> Hello,
>>>
>>> I'd like to ask for formal review of (candidate)
>>> Boost.PolyCollection [...]
>>
>> Hi,
>>
>> thanks for proposing this library Joaquîn.
>
> Hi Vicente, thanks for your interest.
>
>> I've surely missed why base_collection is named this way. Is it
>> because the parameter is a base class. Could you confirm?
>
> Exactly. base_collection<Base> pretty much behaves as a container of
> Base objects.
>
>> wondering if a single class with specializations wouldn't help
>>
>>     collection<polymorphic<T>>
>>     collection<function<T(U)>>
>>     collection<any<Concept>>
>>
>> In this way we could have
>>
>>     collection<Model, Allocator>
>>
>> BTW, I see that you have in the implementation a
>> detail::poly_collection<Model, Allocator> that is the base of the 3
>> collections.
>
> This is mostly a naming issue. Indeed the three collections derive
> from the same
> implementation and could be publicly provided as specializations of
> the same class,
> if this is what reviewers lean towards. Personally I like it better to
> keep names
> separated as in the current proposal.
Ok, no problem.

>
>> In your blog there were some comments about a collection of variants.
>> Have you considered adding a variant_collection<Ts...>
>
> I've thought about it. Such a collection would deviate from the others
> both in terms
> of its interface (no type registration, for instance) and
> implementation --the data
> structure detail::poly_collection relies on could be used to support
> variants, but
> more efficient implementations exist for this particular case.
Ok, I see. Even if it needs a specific implementation I believe it is
worth having it. I say that because more and more people are using
variant as an alternative way of polymorphism (See Andrzej blog -
Another polymorphism)
https://akrzemi1.wordpress.com/2016/02/27/another-polymorphism/
>
>> As the collections are closer to multisets (unordered/not-hash),
>> maybe it is worth using this name.
>
> I'd say similarities with unordered_multiset are superficial (segments
> resemble
> buckets) and the interfaces ultimately are too different. I chose
> "collection" because
> the term is not overloaded in the STL or Boost.
My intention was to confirm we have something close to a multiset.
Anyway, it would be great to see a comparison table. Aside construction,
what is provided by std::unordered_multiset that is not provided by the
poly_collections (or it is provided in a different way) ?

>
>> Have you think about using the same design for maps/unordered maps of
>> polymorphic objet (where the key is not polymorphic)?
>
> Same-type contiguity is an essential feature of PolyCollection: I fail
> to see how this
> could be preserved for an associative container. Care to elaborate?
I was thinking in having the a map of (keys,poly_collection.::iterator)
and store the values using your poly_collection. After thinking a little
bit more on that maybe there is a problem with the iterators stability.

>
>> There is a C++ proposal for a polymorphic_value
>> (https://github.com/jbcoe/polymorphic_value/blob/master/draft.md).
>> Your base_collection<T> corresponds quite well to this
>> polymorphic_value<T>, isn't it?
>> Maybe polymorphic_collection<T> or collection<polymorphic<T>>
>> The main difference is the memory management, polymorphic_value can
>> be adapted to use an Allocator.
>
> base_collection<T> behaves approximately as a
> std::vector<polymorphic_value<T>>,
> the crucial difference being that the former groups elements by
> concrete type in
> contiguous chunks of memory, while the latter holds indirection
> pointers behind the
> scenes, so there is no real memory contiguity.
I talked of polymorphic_value as it close to std::function and
boost::type_erasure::any. At the end all of them are type erasures for
some concept.
IMO, you base_collection<T> is closer to vector<polymorphic_value<T>>
than to ptr_vector<T>. Of course the layout is not the same, and this
makes the difference of your poly_collections.

>
>> What are the function types passed to for_each whee we have a
>> function_collection or a any_collection? Is a reference to the
>> |value_type? |Do we need generic lambdas?
>
> These functions are passed a (const) value_type&, where
>
> value_type=function_collection_value_type<Sig>  for
> function_collection<Sig>,
> value_type=any_collection_value_type<Concept>  for
> any_collection<Concept>
>
> (see http://tinyurl.com/hmywnea , http://tinyurl.com/zh9ugl8 ). Now,
> when type
> restitution is used (http://tinyurl.com/gopdpuz ), and only then, the
> functions are
> passed a (const) Ti& for each of the restituted types Ti: in this
> case, a generic lambda
> is a very convenient way of taking advantage of this, but you can also
> resort to a
> polymorphic functor if you wish.


Let me see if I understood.
For the normal algorithms, the function has as parameter the const
value_type and needs to use dynamic polymorphism.
When we use the “restituted" algorithm overload, the algorithm
"restitutes" the specific types and call to an heterogeneous function,
an overload set  for the reconstituted types, as if it were a visitor,
isn't it?

hana::overload function should be useful here.


Vicente


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Review Request: poly_collection

Boost - Dev mailing list
El 02/03/2017 a las 18:46, Vicente J. Botet Escriba via Boost escribió:

> Le 02/03/2017 à 10:41, Joaquin M López Muñoz via Boost a écrit :
>> El 01/03/2017 a las 23:15, Vicente J. Botet Escriba escribió:
>>> In your blog there were some comments about a collection of
>>> variants. Have
>>> you considered adding a variant_collection<Ts...>
>>
>> I've thought about it. Such a collection would deviate from the
>> others both in terms
>> of its interface (no type registration, for instance) and
>> implementation --the data
>> structure detail::poly_collection relies on could be used to support
>> variants, but
>> more efficient implementations exist for this particular case.
>
> Ok, I see. Even if it needs a specific implementation I believe it is
> worth having it. I say
> that because more and more people are using variant as an alternative
> way of
> polymorphism (See Andrzej blog - Another polymorphism)
> https://akrzemi1.wordpress.com/2016/02/27/another-polymorphism/

This can be defintely included in the lib roadmap. A variant_collection
won't fit 100% within
the current concepts in Boost.PolyCollection (e.g. type registration
makes no sense, type
restitution shoul be provided through a different interface as there's
no need for the user
to specify the restituted types), but I guess we could work it out. A
variant-specific
implementation could be very fast as no virtual calls are needed and
segment visitation
can be resolved statically (detail::poly_collection uses a
virtual-powered backend).

>> I'd say similarities with unordered_multiset are superficial
>> (segments resemble
>> buckets) and the interfaces ultimately are too different. I chose
>> "collection" because
>> the term is not overloaded in the STL or Boost.
>
> My intention was to confirm we have something close to a multiset.
> Anyway, it would
> be great to see a comparison table. Aside construction, what is
> provided by
> std::unordered_multiset that is not provided by the poly_collections
> (or it is provided
> in a different way) ?

poly collections do not behave like multisets in many respects:

* There is no predicate-induced ordering of elements: order in a poly
collection is free for
the user to change *within a segment* (much like in a regular
std::vector<T>).
* No binary-search lookup interface.
* segments might resemble buckets, but they're completely different
beasts: segments
are dedicated vector-like structures for same-type elements, whereas
elements in
an unordered multiset migrate from bucket to bucket as the container
grows (rehashes).

All in all, I really don't see much connection between both data structures.

> I talked of polymorphic_value as it close to std::function and
> boost::type_erasure::any.
> At the end all of them are type erasures for some concept. IMO, you
> base_collection<T>
> is closer to vector<polymorphic_value<T>> than to ptr_vector<T>. Of
> course the layout
> is not the same, and this makes the difference of your poly_collections.
>

Exactly. Both structures hide pointer indirections away.

> For the normal algorithms, the function has as parameter the const
> value_type and
> needs to use dynamic polymorphism.

Right. (Parameter is (const) value_type&, note the '&'.)

> When we use the “restituted" algorithm overload, the algorithm
> "restitutes" the specific
> types and call to an heterogeneous function, an overload set  for the
> reconstituted
> types, as if it were a visitor, isn't it?

Exactly. The nice thing about generic lambdas is that code such as this

   [](auto& x){
     //use common interface of all types
   }

automatically generates the necessary overloads. For instance:

   struct base
   {
     virtual void f();
   };

   struct derived1:base{...};
   struct derived2:base{...};
   struct derived3:base{...};

   poly_collection::for_each<derived1,derived2,derived3>(
     c.begin(),c.end(),
     [](auto& x){x.f();}};

generates overloads in the lambda function for derived1, derived2 and
derived3, which sufficiently smart compilers (GCC , Clang) can use to
completely eliminate virtual machinery in calling x.f().

> hana::overload function should be useful here.

Can be useful when you want to use a different interface for each type:

   struct base
   {
     virtual void f();
   };

   struct derived1:base{void d1();...};
   struct derived2:base{void d2();...};
   struct derived3:base{void d3();...};

   poly_collection::for_each<derived1,derived2,derived3>(
     c.begin(),c.end(),
     hana::overload(
       [](derived1& x){x.f();x.d1();},
       [](derived2& x){x.f();x.d2();},
       [](derived3& x){x.f();x.d3();})};

Joaquín M López Muñoz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost