[poly_collection] Request for comments: fast polymorphic collections
A couple of years ago I wrote two blog entries about high-performance data structures for polymorphic objects: http://bannalia.blogspot.com/2014/05/fast-polymorphic-collections.html http://bannalia.blogspot.com/2014/05/fast-polymorphic-collections-with.html that spurred some interest in the community. Now I've had the time to turn these ideas into something resembling a full-fledged library: https://github.com/joaquintides/poly_collection http://rawgit.com/joaquintides/poly_collection/website/doc/html/index.html and I'd be very grateful if people could give their opinion on usefulness, design, etc. so as to determine potential interest in an eventual official submission to Boost. Thank you, Joaquín M López Muñoz
On Sun, Nov 6, 2016 at 7:25 AM, Joaquin M López Muñoz <joaquinlopezmunoz@gmail.com> wrote:
and I'd be very grateful if people could give their opinion on usefulness, design, etc. so as to determine potential interest in an eventual official submission to
I spent about 20 minutes reading the documentation and looking through the class declarations in the repository. This library solves a real problem and looks like it does so efficiently. The code looks pretty solid. I can already think of one place that could benefit from such a container. Specifically the implementation of this specification, where "Condition" is a polymorphic object and where threshold condition types may have an array of children which are themselves Condition objects: https://tools.ietf.org/html/draft-thomas-crypto-conditions-00 One question, how do you iterate over all the objects of a particular type in a container using a range-for? I see begin() and end() overloads which take a std::type index but if I want to visit all the "warrior" objects (from your example) in a given container `c`, what expression do I put in place of R below: for(auto& sprite : R) { ... } Thanks
El 06/11/2016 a las 15:46, Vinnie Falco escribió:
One question, how do you iterate over all the objects of a particular type in a container using a range-for? I see begin() and end() overloads which take a std::type index but if I want to visit all the "warrior" objects (from your example) in a given container `c`, what expression do I put in place of R below:
for(auto& sprite : R) { ... }
In its current state the lib does not provide syntax sugar for this. The alternatives are for(auto first=c.begin<warrior>(),last=c.end<warrior>();first!=last;++first){ ... // work with *first } std::for_each(c.begin<warrior>(),c.end<warrior>(),[](auto& sprite){ ... } for(auto& sprite:boost::make_iterator_range(c.begin<warrior>(),c.end<warrior>())){ ... } This is not to say that this particular feature couldn't be in principle added to the lib. Joaquín M López Muñoz
On 11/06/2016 06:25 AM, Joaquin M López Muñoz wrote:
A couple of years ago I wrote two blog entries about high-performance data structures for polymorphic objects:
http://bannalia.blogspot.com/2014/05/fast-polymorphic-collections.html
http://bannalia.blogspot.com/2014/05/fast-polymorphic-collections-with.html
that spurred some interest in the community. Now I've had the time to turn these ideas into something resembling a full-fledged library:
http://rawgit.com/joaquintides/poly_collection/website/doc/html/index.html
and I'd be very grateful if people could give their opinion on usefulness, design, etc. so as to determine potential interest in an eventual official submission to Boost.
Thank you,
Joaquín M López Muñoz
Thanks for the update Joaquin. I noticed you also mentioned this library in reponse to another thread here: http://lists.boost.org/Archives/boost/2016/10/231186.php which made me wonder how it would perform in the benchmark mentioned in that thread: https://github.com/cppljevans/soa/blob/master/soa_compare.benchmark.cpp But then, I looked at the documentation here: http://rawgit.com/joaquintides/poly_collection/website/doc/html/poly_collect... and it looked like there was a separate pointer for each type. Hence, the storage looks like it would be simllar to: template<typename... Ts> soa_tuple=std::tuple<std::vector<Ts>...>; where the separate pointers would be the data() pointer for each element in soa_tuple. IOW, the storage would be like that of particles here: https://github.com/cppljevans/soa/blob/master/soa_compare.benchmark.cpp#L278 Hence, I'm wondering what's the advantage of your library's base_collection compared to the soa_tuple. Now, if you say soa_tuple contains duplicate entries of size(), then I could ask what's the advantage of base_collection vs that of the particles at: https://github.com/cppljevans/soa/blob/master/soa_compare.benchmark.cpp#L456 where there's just a single pointer to a contiguous block of storage: https://github.com/cppljevans/soa/blob/master/soa_block.hpp#L30 and the pointers to the specific types are given by the soa_block::begin_all function: https://github.com/cppljevans/soa/blob/master/soa_block.hpp#L294 in the soa_block<Ts...> type of the particles? Maybe you could provide another implentation of the emitter_t using your base_collection to see how they compare. -regards, Larry
El 06/11/2016 a las 17:11, Larry Evans escribió:
Thanks for the update Joaquin.
I noticed you also mentioned this library in reponse to another thread here:
Mmm... on that particular thread I mentioned a different set of blog entries related to DOD, SOA/AOS etc. This is rather a different beast having to do with dynamic polymorphism, which I think the SOA/AOS discussion is not particularly concerned about.
[...]
But then, I looked at the documentation here:
http://rawgit.com/joaquintides/poly_collection/website/doc/html/poly_collect...
and it looked like there was a separate pointer for each type. Hence, the storage looks like it would be simllar to:
template<typename... Ts> soa_tuple=std::tuple<std::vector<Ts>...>;
The data structure in (candidate) Boost.PolyCollection is not meant to be used as a SOA structure where the different attributes of an entity are laid out contiguously, but as a decomposition of a linear sequence of polymorphic objects into several segments dedicate to each of the concrete types being dealt with. In particular, traversing the entire sequence is done by traversing each segment in succession, which looks to me hardly similar to SOA access patterns. Maybe I'm missing something? Joaquín M López Muñoz
On 11/06/2016 02:22 PM, Joaquin M López Muñoz wrote:
El 06/11/2016 a las 17:11, Larry Evans escribió:
Thanks for the update Joaquin.
I noticed you also mentioned this library in reponse to another thread here:
Mmm... on that particular thread I mentioned a different set of blog entries related to DOD, SOA/AOS etc. This is rather a different beast having to do with dynamic polymorphism, which I think the SOA/AOS discussion is not particularly concerned about.
Ah. Thanks for clarifying.
[...]
But then, I looked at the documentation here:
http://rawgit.com/joaquintides/poly_collection/website/doc/html/poly_collect...
and it looked like there was a separate pointer for each type. Hence, the storage looks like it would be simllar to:
template<typename... Ts> soa_tuple=std::tuple<std::vector<Ts>...>;
The data structure in (candidate) Boost.PolyCollection is not meant to be used as a SOA structure where the different attributes of an entity are laid out contiguously, but as a decomposition of a linear sequence of polymorphic objects into several segments dedicate to each of the concrete types being dealt with. In particular, traversing the entire sequence is done by traversing each segment in succession, which looks to me hardly similar to SOA access patterns. Maybe I'm missing something?
No, you probably got it right. I was jumping to conclusions. Sorry :(
On Sun, Nov 6, 2016 at 1:25 PM, Joaquin M López Muñoz < joaquinlopezmunoz@gmail.com> wrote:
A couple of years ago I wrote two blog entries about high-performance data structures for polymorphic objects:
http://bannalia.blogspot.com/2014/05/fast-polymorphic-collections.html http://bannalia.blogspot.com/2014/05/fast-polymorphic-collec tions-with.html
that spurred some interest in the community. Now I've had the time to turn these ideas into something resembling a full-fledged library:
https://github.com/joaquintides/poly_collection http://rawgit.com/joaquintides/poly_collection/website/doc/html/index.html
and I'd be very grateful if people could give their opinion on usefulness, design, etc. so as to determine potential interest in an eventual official submission to Boost.
Sounds great Joaquin. But what if I need the equivalent of Multi-Index? I have several indexes on the base interface (ByGuid unique, ByNKey unique, ByParent non-unique, ByType non-unique, etc...), so am I stuck into heap-based classic OOP because I need those? Also, you provide "by *concrete* type" access to a segment, but often time we're also interested in "by *abstract* base" access/traversal, the base not necessarily being the one from the container itself. Any thoughts on that? Of course, you can't do "isAssigneableFrom()" tests using just std::typeid(), so a custom RTTI mechanism is necessary, but implicit traversal of all the "derived" segments for any particular abstract type would be really useful IMHO. Finally, can you share any compile-time impact, between you any_... and poly_... benchmarks for example? Thanks, --DD PS: Would VS2013 work with it too? I'm currently stuck with that one...
El 07/11/2016 a las 12:04, Dominique Devienne escribió:
On Sun, Nov 6, 2016 at 1:25 PM, Joaquin M López Muñoz < joaquinlopezmunoz@gmail.com> wrote:
[...]
https://github.com/joaquintides/poly_collection
[...] Sounds great Joaquin. But what if I need the equivalent of Multi-Index?
I have several indexes on the base interface (ByGuid unique, ByNKey unique, ByParent non-unique, ByType non-unique, etc...), so am I stuck into heap-based classic OOP because I need those?
I'm afraid Boost.MultiIndex forces you to lose memory contiguity just as is the case for non-OOP scenarios (boost::multi_index_container is node-based). I haven't though of smart ways to combine (candidate) Boost.PolyCollection and Boost.MultiIndex, I guess a boost::multi_index_container of references to boost::base_collection elements is the closest you can get both worlds together without further development in any of the libs.
Also, you provide "by *concrete* type" access to a segment, but often time we're also interested in "by *abstract* base" access/traversal, the base not necessarily being the one from the container itself. Any thoughts on that? Of course, you can't do "isAssigneableFrom()" tests using just std::typeid(), so a custom RTTI mechanism is necessary, but implicit traversal of all the "derived" segments for any particular abstract type would be really useful IMHO.
This can be done relatively easily: #include <boost/poly_collection/base_collection.hpp> #include <iostream> struct base { virtual ~base()=default; }; struct derived1:base{}; struct base1:base { virtual void display()const=0; }; struct derived2:base1 { virtual void display()const{std::cout<<"derived2\n";} }; struct derived3:base1 { virtual void display()const{std::cout<<"derived3\n";} }; template<typename SubBase,typename BaseCollection,typename Function> Function for_each_subbase(BaseCollection&& c,Function f) { using subbase_type=typename std::conditional< std::is_const< typename std::remove_reference<BaseCollection>::type >::value, const SubBase,SubBase >::type; for(auto s:c.segment_traversal()){ if(s.begin()==s.end()|| !dynamic_cast<subbase_type*>(&(*s.begin())))continue; for(auto& x:s)f(static_cast<subbase_type&>(x)); } return std::move(f); } int main() { boost::base_collection<base> c; c.insert(derived1{}); c.insert(derived2{}); c.insert(derived3{}); for_each_subbase<base1>(c,[](auto& x){x.display();}); } Note this scheme is pretty efficient as dynamic_cast is invoked just *once* per segment. A more refined version of this idea based on a general concept of dynamic subtyping could potentially be added to the library.
Finally, can you share any compile-time impact, between you any_... and poly_... benchmarks for example?
I haven't measured compile times, but the library feels very light (for instance, on my i5@2.5Ghz machine the code above compiles in less than 3s). If you have any specific. If you have any specific scenario in mind I'd be happy to benchmark it more rigorously.
Thanks, --DD
PS: Would VS2013 work with it too? I'm currently stuck with that one...
A cursory look at https://msdn.microsoft.com/en-us/library/hh567368.aspx shows that at least one necessary feature (noexcept) is missing in VS2013, so the short answer is no. noexcept can be easily backported with BOOST_NOEXCEPT, but of course other details might be lurking... If you want to give a try please contact me back. Joaquín M López Muñoz
Hi Joaquin,
A couple of years ago I wrote two blog entries about high-performance data structures for polymorphic objects:
[snip]
and I'd be very grateful if people could give their opinion on usefulness, design, etc. so as to determine potential interest in an eventual official submission to Boost.
A. This is very useful. B. I'm still wondering if requirering copyability is a good thing. After all, references and pointers may be used elsewere in the program where copying is really not a good idea. Could it make sense to have a variation of cloneable: void clone( void* storage ) const; // essentially a call to protected or private copy-constructor: // new(storage) T( *this ) which is then used internally when copying is needed? And when no copying is needed, the container is not copyable. To insert elements that are not copyable we would just use emplace with a type argument: coll.emplace<derived>( x, y ); C. perhap some range versions of local iterators would be nice? D. I don't get the use of numeric_limits<T>::max() for capacity of an empty container. I would be perfectly happy with 0 unless there is something we cannot do with that definition. E. Boost.PtrContainer does not throw exception when a container cannot be cloned or compared. Maybe its must be possible to get compile errors here too? F. when using type restitution for base_collection, could it no make sense to provide struct visitor { void operator()( const auto& s ) const { s.render(std::cout); } void operator()( const warrior& w ) const { w.warrior::render(std::cout); } // etc for remaining types } ; that is, would that not guarantee devirtualization? G. The performance results are very impressive; do that carry over to 100 elements? I have sometimes though that my best choice would be poly_vector<base> where everything is stored in one big chunk of memory, but I guess the type restitution can make up for that. Nice work! kind regards Thorsten PS: the upcomming Boost.DoubleEnded has a new deque class that exposes segmented iterations. I'm wondering if the algorithms that you have made can be reused for that data structure.
El 15/11/2016 a las 18:38, Thorsten Ottosen escribió:
Hi Joaquin,
[...]
A. This is very useful.
Thanks! Glad you find it interesting.
B. I'm still wondering if requirering copyability is a good thing. After all, references and pointers may be used elsewere in the program where copying is really not a good idea. Could it make sense to have a variation of cloneable:
void clone( void* storage ) const;
// essentially a call to protected or private copy-constructor: // new(storage) T( *this )
which is then used internally when copying is needed? And when no copying is needed, the container is not copyable. To insert elements that are not copyable we would just use emplace with a type argument:
coll.emplace<derived>( x, y );
Strictly speaking, copyability is not required, but as concrete types are stored in rellocatable vectors they must be verify the following: * be MoveConstructible, * be Moveassignable or have a noexcept move constructor. Otherwise, segments wouldn't be able to grow beyond its initial capacity. As for your clone() proposal, I fail to see why this is preferrable to simply requiring (move/copy) constructibility. Please note that moving/copying in Boost.PolyCollection happens in a non-virtual environment, so we don't need the virtual-enabled clone mechanism as envisioned in the Clonable concept of Boost.PtrContainer. Please correct me if I'm missing your point.
C. perhap some range versions of local iterators would be nice?
Care to elaborate? I've basically replicated the usual interface of standard containers, of course open to consider justified improvements on that.
D. I don't get the use of numeric_limits<T>::max() for capacity of an empty container. I would be perfectly happy with 0 unless there is something we cannot do with that definition.
Not a strong opinon on that. Having capacity()==infinite for a segment-less collection makes sense from a mathematical point of view, but other than that 0 could work equally well. If this eventually make it into an official proposal I'd adopt whatever the community thinks makes the most sense.
E. Boost.PtrContainer does not throw exception when a container cannot be cloned or compared. Maybe its must be possible to get compile errors here too?
I've re-read Boost.PtrContainer docs and seems like the containers require Base to be clonable, which is tantamount to requiring copyability for all derived classes in Boost.PolyCollection. Am I wrong here? What's the behavior if a Base is not clonable?
F. when using type restitution for base_collection, could it no make sense to provide
struct visitor { void operator()( const auto& s ) const { s.render(std::cout); } void operator()( const warrior& w ) const { w.warrior::render(std::cout); } // etc for remaining types } ;
that is, would that not guarantee devirtualization?
Very good observation. Yes, that would force devirtualization. The thing can be packed into something more generic: template<typename F1,typename F2>struct overload_class:F1,F2 { overload_class(const F1& f1,const F2& f2):F1{f1},F2{f2}{} using F1::operator(); using F2::operator(); }; template<typename F1,typename F2>auto overload(const F1& f1,const F2& f2) { return overload_class<F1,F2>{f1,f2}; } auto render=overload( [](const sprite& s){ s.render(std::cout); }, [](const auto& s){ using derived=typename std::decay<decltype(s)>::type; s.derived::render(std::cout); } ); Where the overload for const sprite& is needed because the other overload would try to get a reference to the pure virtual sprite::render member function. This probably deserves a mention in the docs.
G. The performance results are very impressive; do that carry over to 100 elements?
Looks like it does; results for n=100-1000, Visual C++ 2015 in 32-bit (x86) release mode, Windows 7 64-bit, Intel Core i5-2520M @2.5GHz: for_each: n;ptr_vector;sorted ptr_vector;shuffled ptr_vector;base_collection;base_collection (poly::for_each);base_collection (restituted poly::for_each) 100;72.2216;37.1035;102.137;49.8478;46.7159;55.0599 200;61.3873;30.4139;82.3211;44.2409;36.4579;38.5366 310;60.4311;29.1478;84.326;41.6049;32.6577;33.1415 430;59.3126;27.9782;82.6663;39.8802;31.4011;31.8698 560;59.4073;27.3143;79.945;38.9328;30.5108;30.6352 710;59.9286;27.1021;80.2318;37.589;29.7589;29.3414 870;59.6583;28.0717;79.1177;37.927;28.6542;29.1687 1045;59.1093;26.5752;77.692;37.973;28.2845;27.938
I have sometimes though that my best choice would be poly_vector<base> where everything is stored in one big chunk of memory, but I guess the type restitution can make up for that.
Nice work!
kind regards
Thorsten
PS: the upcomming Boost.DoubleEnded has a new deque class that exposes segmented iterations. I'm wondering if the algorithms that you have made can be reused for that data structure.
Not directly so, as the mechanisms for getting a segment iterator from a global iterator are Boost.PolyCollection-specific, and type restitution makes no sense for Boost.DoubleEnded. But the algorithmic part (some of which is not trivial) can be certainly taken as an inspiration for Boost.DoubleEnded, and it might be conceivable to factor everything out to a Boost.SegmentedAlgorithm proposal or something. Best, Joaquín M López Muñoz
On 15-11-2016 23:53, Joaquin M López Muñoz wrote:
El 15/11/2016 a las 18:38, Thorsten Ottosen escribió:
Hi Joaquin,
[...]
A. This is very useful.
Thanks! Glad you find it interesting.
B. I'm still wondering if requirering copyability is a good thing. After all, references and pointers may be used elsewere in the program where copying is really not a good idea. Could it make sense to have a variation of cloneable:
void clone( void* storage ) const;
// essentially a call to protected or private copy-constructor: // new(storage) T( *this )
which is then used internally when copying is needed? And when no copying is needed, the container is not copyable. To insert elements that are not copyable we would just use emplace with a type argument:
coll.emplace<derived>( x, y );
Strictly speaking, copyability is not required, but as concrete types are stored in rellocatable vectors they must be verify the following:
* be MoveConstructible, * be Moveassignable or have a noexcept move constructor.
Otherwise, segments wouldn't be able to grow beyond its initial capacity.
Right. But maybe that access to be hidden to the outside world like in Boost.Serialiation: friend class boost::poly_collection::access; Then perhaps your library could work with private and protected copy/move operations? My point is that we are still doing OO-programming, and copying/moving is not natural operations for objects in that domain.
As for your clone() proposal, I fail to see why this is preferrable to simply requiring (move/copy) constructibility. Please note that moving/copying in Boost.PolyCollection happens in a non-virtual environment, so we don't need the virtual-enabled clone mechanism as envisioned in the Clonable concept of Boost.PtrContainer. Please correct me if I'm missing your point.
You could always devirtualize it. Anyway, the point is, to hide the copy/move semantics to clients of my class hierarchy. Take the following use-case: I know what types to register and how many of each I'm going to insert. For that case I should be able to construct, reserve and insert without having a copyable or movable type. Anyway, I would be ok with just being able to make copy/move operations protected.
C. perhap some range versions of local iterators would be nice?
Care to elaborate? I've basically replicated the usual interface of standard containers, of course open to consider justified improvements on that.
For example, for(auto first=c.begin<warrior>(),last=c.end<warrior>(); first!=last;++first) could be nice to write for( auto x : c.range<warrior>() ) or for( auto x : restituted_range<warrior>(c) )
D. I don't get the use of numeric_limits<T>::max() for capacity of an empty container. I would be perfectly happy with 0 unless there is something we cannot do with that definition.
Not a strong opinon on that. Having capacity()==infinite for a segment-less collection makes sense from a mathematical point of view, but other than that 0 could work equally well. If this eventually make it into an official proposal I'd adopt whatever the community thinks makes the most sense.
ok, it confused me, so chances are that it will confuse the average programmer and take up brain cycles for no reason.
E. Boost.PtrContainer does not throw exception when a container cannot be cloned or compared. Maybe its must be possible to get compile errors here too?
I've re-read Boost.PtrContainer docs and seems like the containers require Base to be clonable, which is tantamount to requiring copyability for all derived classes in Boost.PolyCollection. Am I wrong here? What's the behavior if a Base is not clonable?
It's a compile error. But I think I don't give the compile error until the cloning is needed.
that is, would that not guarantee devirtualization?
Very good observation. Yes, that would force devirtualization. The thing can be packed into something more generic:
sweet. kind regards -Thorsten
El 16/11/2016 a las 11:54, Thorsten Ottosen escribió:
B. I'm still wondering if requirering copyability is a good thing [...]
Right. But maybe that access to be hidden to the outside world like in Boost.Serialiation:
friend class boost::poly_collection::access;
Then perhaps your library could work with private and protected copy/move operations? My point is that we are still doing OO-programming, and copying/moving is not natural operations for objects in that domain.
[...]
You could always devirtualize it. Anyway, the point is, to hide the copy/move semantics to clients of my class hierarchy. Take the following use-case:
I know what types to register and how many of each I'm going to insert. For that case I should be able to construct, reserve and insert without having a copyable or movable type.
Anyway, I would be ok with just being able to make copy/move operations protected.
I'm in principle somewhat reluctant to add lib-specific mechanisms for generic operations such as copying (although the friend class boost::poly_collection::access thing is an opt-in feature not really needed for publicly copyable classes); that said, my wish is to flexible with whatever reviewers mostly agree on.
C. perhap some range versions of local iterators would be nice?
[...]
For example,
for(auto first=c.begin<warrior>(),last=c.end<warrior>(); first!=last;++first)
could be nice to write
for( auto x : c.range<warrior>() )
or
for( auto x : restituted_range<warrior>(c) )
range<warrior>() (and range(typeid(warrior))) definitely save some keystrokes, so why not. What do you mean by restituted_range<warrior>(c)?
E. Boost.PtrContainer does not throw exception when a container cannot be cloned or compared. Maybe its must be possible to get compile errors here too?
I've re-read Boost.PtrContainer docs and seems like the containers require Base to be clonable, which is tantamount to requiring copyability for all derived classes in Boost.PolyCollection. Am I wrong here? What's the behavior if a Base is not clonable?
It's a compile error. But I think I don't give the compile error until the cloning is needed.
The problem is that, unlike the case of Boost.PtrContainer, a polymorphic collection can hold simultaneously classes that are copyable and non-copyable, so whole-copyability cannot be determined till invocation time. Best Joaquín M López Muñoz
On 16-11-2016 18:39, Joaquin M López Muñoz wrote:
El 16/11/2016 a las 11:54, Thorsten Ottosen escribió:
B. I'm still wondering if requirering copyability is a good thing [...]
Right. But maybe that access to be hidden to the outside world like in Boost.Serialiation:
friend class boost::poly_collection::access;
Anyway, I would be ok with just being able to make copy/move operations protected.
I'm in principle somewhat reluctant to add lib-specific mechanisms for generic operations such as copying (although the friend class boost::poly_collection::access thing is an opt-in feature not really needed for publicly copyable classes); that said, my wish is to flexible with whatever reviewers mostly agree on.
Yes, please consider it. Most OO-hierarchies start off with prohibiting copying by inheriting from boost::noncopyable or something similar. It would be a shame if such hierarchies would now be /forced/ to have public copy/move operations.
C. perhap some range versions of local iterators would be nice?
[...]
For example,
for(auto first=c.begin<warrior>(),last=c.end<warrior>(); first!=last;++first)
could be nice to write
for( auto x : c.range<warrior>() )
or
for( auto x : restituted_range<warrior>(c) )
range<warrior>() (and range(typeid(warrior))) definitely save some keystrokes, so why not. What do you mean by restituted_range<warrior>(c)?
The name was referring to type restitution from your docs. This latter one is a free-standing function, so c is the collection. Anway, I prefer members. kind regards -Thorsten
El 18/11/2016 a las 12:02, Thorsten Ottosen escribió:
On 16-11-2016 18:39, Joaquin M López Muñoz wrote:
I'm in principle somewhat reluctant to add lib-specific mechanisms for generic operations such as copying (although the friend class boost::poly_collection::access thing is an opt-in feature not really needed for publicly copyable classes); that said, my wish is to flexible with whatever reviewers mostly agree on.
Yes, please consider it. Most OO-hierarchies start off with prohibiting copying by inheriting from boost::noncopyable or something similar. It would be a shame if such hierarchies would now be /forced/ to have public copy/move operations.
Point taken. Joaquín M Lopez Muñoz
El 18/11/2016 a las 12:02, Thorsten Ottosen escribió:
On 16-11-2016 18:39, Joaquin M López Muñoz wrote:
I'm in principle somewhat reluctant to add lib-specific mechanisms for generic operations such as copying (although the friend class boost::poly_collection::access thing is an opt-in feature not really needed for publicly copyable classes); that said, my wish is to flexible with whatever reviewers mostly agree on.
Yes, please consider it. Most OO-hierarchies start off with prohibiting copying by inheriting from boost::noncopyable or something similar. It would be a shame if such hierarchies would now be /forced/ to have public copy/move operations.
Point taken. Joaquín M López Muñoz
On 16-11-2016 11:54, Thorsten Ottosen wrote:
On 15-11-2016 23:53, Joaquin M López Muñoz wrote:
El 15/11/2016 a las 18:38, Thorsten Ottosen escribió:
D. I don't get the use of numeric_limits<T>::max() for capacity of an empty container. I would be perfectly happy with 0 unless there is something we cannot do with that definition.
Not a strong opinon on that. Having capacity()==infinite for a segment-less collection makes sense from a mathematical point of view, but other than that 0 could work equally well. If this eventually make it into an official proposal I'd adopt whatever the community thinks makes the most sense.
ok, it confused me, so chances are that it will confuse the average programmer and take up brain cycles for no reason.
It also seems natural to expect that capacity() - size() for a container to tell us the number of elements I can insert without reallocation will happen, and hence is important if one want to reason about exception-safety. With the exotic definition of capacity() that is no longer the case. kind regards -Thorsten
El 18/11/2016 a las 11:56, Thorsten Ottosen escribió:
It also seems natural to expect that capacity() - size() for a container to tell us the number of elements I can insert without reallocation will happen, and hence is important if one want to reason about exception-safety. With the exotic definition of capacity() that is no longer the case.
Here I don't see an alternative: please note that c.insert(x) can *never* guarantee no memory allocation because x can be of an as-of-yet unregistered type, which will force the creation of a new segment etc. So, we can only provide capacity information for *registered* types, which is precisely what the exotic definition of capacity() does. Do you see any other viable definition? Joaquín M López Muñoz
On 19-11-2016 10:09, Joaquin M López Muñoz wrote:
El 18/11/2016 a las 11:56, Thorsten Ottosen escribió:
It also seems natural to expect that capacity() - size() for a container to tell us the number of elements I can insert without reallocation will happen, and hence is important if one want to reason about exception-safety. With the exotic definition of capacity() that is no longer the case.
Here I don't see an alternative: please note that c.insert(x) can *never* guarantee no memory allocation because x can be of an as-of-yet unregistered type, which will force the creation of a new segment etc.
OTOH, if we know the type is registered ... and there is also the reverse statement: if capacity is 0, I know the thing can throw.
So, we can only provide capacity information for *registered* types, which is precisely what the exotic definition of capacity() does. Do you see any other viable definition?
Hm. Maybe not. We have cc.capacity() cc.capacity(index) cc.capacity<U>() and the first is specified as "the minimum return value of capacity for each of the segments of the collection, or std::numeric_limits<size_type>::max if there are no segments." I can't see how that is useful for much. The segment specific ones are useful, of course. I would still say it should return 0 if there are no segments, or that it should not be provided at all. If provided, it should follow size() which I assume sums over all segment sizes. That is, it should sum over all capacities. Here are some design questions: A. Do we want these two states to be independently observable: - empty, but with empty segments - empty, but with no segments B. If I call shrink_to_fit on an container with empty segements, does it end up with no segments? C. Could the segment type be a template argument, or is there good reasons for not dong that?
El 23/11/2016 a las 18:23, Thorsten Ottosen escribió:
On 19-11-2016 10:09, Joaquin M López Muñoz wrote:
So, we can only provide capacity information for *registered* types, which is precisely what the exotic definition of capacity() does. Do you see any other viable definition?
Hm. Maybe not. We have
cc.capacity() cc.capacity(index) cc.capacity<U>()
and the first is specified as
"the minimum return value of capacity for each of the segments of the collection, or std::numeric_limits<size_type>::max if there are no segments."
I can't see how that is useful for much. The segment specific ones are useful, of course. I would still say it should return 0 if there are no segments, or that it should not be provided at all. If provided, it should follow size() which I assume sums over all segment sizes. That is, it should sum over all capacities.
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).
Here are some design questions:
A. Do we want these two states to be independently observable:
- empty, but with empty segments - empty, but with no segments
These two states are indeed observably different: A collection with a segment for D returns true for is_registered<D>(). The distinction is important; for instance, the following Base x; D& d=x; // D is derived from Base p.insert(d); throws if D is not previously registered into the collection p.
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.
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. Joaquín M López Muñoz
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
El 30/11/2016 a las 17:10, Thorsten Ottosen escribió:
On 23-11-2016 21:19, Joaquin M López Muñoz wrote:
El 23/11/2016 a las 18:23, Thorsten Ottosen escribió:
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?
I think all-segment reserve is convenient as there are use cases that can't be done easily with segment-specific reserve, such as "make sure *registered* types can't hold N elements without reallocation" Doing this without reserve is possible but awkward and sub-optimal wrt efficiency: for(auto s:c.segment_traversal()){ c.reserve(s.type_index(),N); // incurs an internal lookup on std::type_index } Joaquín M López Muñoz
On 11/15/2016 11:38 AM, Thorsten Ottosen wrote:
PS: the upcomming Boost.DoubleEnded has a new deque class that exposes segmented iterations. I'm wondering if the algorithms that you have made can be reused for that data structure.
Guntram Berti also has some nice work in the area of hierarchical algorithms. https://github.com/gberti/hierarchical-algorithms
participants (6)
-
Dominique Devienne -
Joaquin M López Muñoz -
Larry Evans -
Michael Marcin -
Thorsten Ottosen -
Vinnie Falco