12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208 |
- [library Boost.PolyCollection
- [quickbook 1.6]
- [authors [López Muñoz, Joaquín M]]
- [copyright 2016-2019 Joaquín M López Muñoz]
- [category containers]
- [id poly_collection]
- [dirname poly_collection]
- [purpose
- High-performance containers for polymorphic objects.
- ]
- [license
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- [@http://www.boost.org/LICENSE_1_0.txt])
- ]
- ]
- [def _Boost.TypeErasure_ [@boost:/libs/type_erasure Boost.TypeErasure]]
- [def _Boost.TypeIndex_ [@boost:/libs/type_index Boost.TypeIndex]]
- [def _CopyConstructible_ [@http://en.cppreference.com/w/cpp/named_req/CopyConstructible [* `CopyConstructible`]]]
- [def _duck_typing_ [@https://en.wikipedia.org/wiki/Duck_typing ['duck typing]]]
- [def _EqualityComparable_ [@http://en.cppreference.com/w/cpp/named_req/EqualityComparable [* `EqualityComparable`]]]
- [def _ForwardIterator_ [@http://en.cppreference.com/w/cpp/named_req/ForwardIterator [* `ForwardIterator`]]]
- [def _MoveConstructible_ [@http://en.cppreference.com/w/cpp/named_req/MoveConstructible [* `MoveConstructible`]]]
- [def _MoveAssignable_ [@http://en.cppreference.com/w/cpp/named_req/MoveAssignable [* `MoveAssignable`]]]
- [def _std::for_each_ [@http://en.cppreference.com/w/cpp/algorithm/for_each `std::for_each`]]
- [def _std::function_ [@http://en.cppreference.com/w/cpp/utility/functional/function `std::function`]]
- [def _std::unordered_multiset_ [@http://en.cppreference.com/w/cpp/container/unordered_multiset `std::unordered_multiset`]]
- [def _RandomAccessIterator_ [@http://en.cppreference.com/w/cpp/named_req/RandomAccessIterator [* `RandomAccessIterator`]]]
- [template ticket[number]'''<ulink url="https://svn.boost.org/trac/boost/ticket/'''[number]'''">'''#[number]'''</ulink>''']
- [template github[module number]'''<ulink url="https://github.com/boostorg/'''[module]'''/issues/'''[number]'''">'''#[number]'''</ulink>''']
- [template github_pr[module number]'''<ulink url="https://github.com/boostorg/'''[module]'''/pull/'''[number]'''">'''PR#[number]'''</ulink>''']
- [section Introduction]
- Dynamic polymorphism in C++ requires that objects (such as instances
- of classes derived from an abstract base) be accessed through an indirection pointer
- because their actual /type/ and /size/ are not known at the point of usage. As a
- consequence, regular containers cannot store polymorphic objects directly: the usual
- workaround is to have containers of pointers to heap-allocated elements. In modern
- computer architectures this pattern incurs two types of inefficiency:
- * The lack of memory contiguity produced by heap allocation degrades CPU cache
- performance.
- * Executing virtual operations on a sequence of polymorphic objects whose
- actual types differ from one to the next results in failures in
- [@https://en.wikipedia.org/wiki/Branch_predictor branch prediction] and a
- lower execution speed.
- When the particular traversal order is not relevant to the user application,
- Boost.PolyCollection proposes an alternative data structure that restores memory
- contiguity and packs elements according to their concrete type. Three container
- class templates are provided:
- * `boost::base_collection`
- * `boost::function_collection`
- * `boost::any_collection`
- respectively dealing with three different types of dynamic polymorphism
- available in C++:
- * Classic base/derived or OOP polymorphism.
- * Function wrapping in the spirit of _std::function_.
- * So-called _duck_typing_ as implemented by _Boost.TypeErasure_.
- The interface of these containers closely follows that of standard containers.
- Additionally, the library provides versions of many of the standard library
- algorithms (including
- [@http://en.cppreference.com/w/cpp/algorithm/for_each `std::for_each`])
- with improved performance and a special feature called /type restitution/
- that allows user code to provide clues on the concrete types of the elements
- stored for further opportunities of increased efficiency related to inlining and
- [@http://hubicka.blogspot.com.es/2014/01/devirtualization-in-c-part-1.html ['devirtualization]].
- [note Boost.PolyCollection is a header-only library. C++11 support is required.
- The library has been verified to work with Visual Studio 2015, GCC 4.8 and
- Clang 3.3.]
- [endsect]
- [section An efficient polymorphic data structure]
- Suppose we have a `base` abstract class with implementations `derived1`, `derived2`
- and `derived3`. The memory layout of a `std::vector<base*>` (or similar constructs
- such as `std::vector<std::unique_ptr<base>>` or
- [@boost:/libs/ptr_container/ `boost::ptr_vector<base>`]) looks like
- the following:
- [$poly_collection/img/ptr_vector.png]
- Elements that are adjacent in the vector are not necessarily allocated contiguously,
- much less so if the vector has undergone mid insertions and deletions. A typical
- processing operation
- std::vector<base*> v;
- ...
- for(base* b: v){
- ... // access base's virtual interface
- }
- is impacted negatively by two factors:
- * Scattering of elements throughout memory reduces CPU caching efficiency,
- which in general favor regular access loops to contiguous memory areas.
- * [@https://en.wikipedia.org/wiki/Branch_predictor Branch prediction] tries
- to minimize the effect of running conditional code (such as an
- `if`-`else` statement or the invocation of a `base` virtual function) by
- speculatively executing a given branch based on past history. This
- mechanism is rendered mostly useless when `derived1`, `derived2` and
- `derived3` elements are interspersed along the sequence without a definite pattern.
- These limitations are imposed by the very nature of dynamic polymorphism:
- as the exact types of the elements accessed through `base`'s interface are not
- known, an indirection through `base*` (a particular form of /type erasure/)
- is required. There is however a critical observation: even though derived types
- are not known when traversing a `std::vector<base*>`, the information is typically
- available /at compile time/ at the point of insertion in the vector:
- std::vector<base*> v;
- ...
- v.insert(new derived2{...}); // the type derived2 is "forgotten" by v
- A suitably designed container can take advantage of this information to
- arrange elements contiguously according to their exact type, which results
- in an internal data structure (a map of pointers to
- [@http://en.cppreference.com/w/cpp/types/type_info `std::type_info`] objects,
- actually) pointing to as many vectors or /segments/ as there are derived classes:
- [$poly_collection/img/segment_map.png]
- Traversing such a structure reduces to looping over all the segments one after
- another: this is extremely efficient both in terms of caching and branch
- prediction. In the process we have however lost the free-order capability of a
- `std::vector<base*>` (free order can only be retained at the segment level), but
- if this is not relevant to the user application the potential performance gains
- of switching to this structure are large.
- The discussion has focused on base/derived programming, also known as OOP, but it
- also applies to other forms of dynamic polymorphism:
- * _std::function_ abstracts callable entities with the same given signature
- under a common interface. Internally, pointer indirections and virtual-like
- function calls are used. Memory fragmentation is expected to be lower than
- with OOP, though, as implementations usually feature the so-called
- [@http://talesofcpp.fusionfenix.com/post-16/episode-nine-erasing-the-concrete#a-note-on-small-buffer-optimization [' small buffer optimization]]
- to avoid heap allocation in some situations.
- * The case of `std::function` can be seen as a particular example of a
- more general form of polymorphism called _duck_typing_, where unrelated types
- are treated uniformly if they conform to the same given /interface/ (a specified
- set of member functions and/or operations). Duck typing provides the power of
- OOP while allowing for greater flexibility as polymorphic types need not derive
- from a preexisting base class or in general be designed with any particular
- interface in mind --in fact, the same object can be duck-typed to different
- interfaces. Among other libraries, _Boost.TypeErasure_ provides duck typing
- for C++. Under the hood, duck typing requires pointer indirection and virtual
- call implementation techniques analogous to those of OOP, and so there are
- the same opportunities for efficient container data structures as we have
- described.
- Boost.PolyCollection provides three different container class templates
- dealing with OOP, `std::function`-like polymorphism and duck typing as
- implemented by Boost.TypeErasure:
- * `boost::base_collection`
- * `boost::function_collection`
- * `boost::any_collection`
- The interfaces of these containers are mostly the same and follow the usual
- conventions of standard library containers.
- [endsect]
- [section Tutorial]
- [section Basics]
- [import ../example/rolegame.hpp]
- [section `boost::base_collection`]
- [import ../example/basic_base.cpp]
- (Code samples from [@boost:/libs/poly_collection/example/basic_base.cpp `basic_base.cpp`].)
- Imagine we are developing a role playing game in C++ where sprites are rendered on
- screen; for the purposes of illustration we can model rendering simply as
- outputting some information to a `std::ostream`:
- [rolegame_1]
- The game features warriors, juggernauts (a special type of warrior) and goblins,
- each represented by its own class derived (directly or indirectly) from `sprite`:
- [rolegame_2]
- Let us populate a polymorphic collection with an assortment of sprites:
- [basic_base_1]
- There are two aspects to notice here:
- * `boost::base_collection` does not have a `push_back` member function like, say,
- `std::vector`, as the order in which elements are stored cannot be freely
- chosen by the user code \u2014we will see more about this later. The insertion mechanisms
- are rather those of containers like _std::unordered_multiset_, namely `insert` and
- `emplace` with or without a position /hint/.
- * Elements are not created with `new` but constructed on the stack and passed
- directly much like one would do with a standard non-polymorphic container.
- [important Elements inserted into a `boost::base_collection` (or the other
- containers of Boost.PolyCollection) must be copyable and assignable; strictly
- speaking, they must at least model _MoveConstructible_ and either be
- _MoveAssignable_ or not throw on move construction. This might
- force you to revisit your code as it is customary to explicitly forbid
- copying at the base level of a virtual hierarchy to avoid
- [@https://en.wikipedia.org/wiki/Object_slicing ['slicing]].]
- Rendering can now be implemented with a simple `for` loop over `c`:
- [basic_base_2]
- The output being:
- [pre
- juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,warrior 2,warrior 6
- ]
- As we have forewarned, the traversal order does not correspond to that of insertion.
- Instead, the elements are grouped in /segments/ according to their concrete type.
- Here we see that juggernauts come first, followed by goblins and warriors. In
- general, no assumptions should be made about segment ordering, which may be
- different for this very example in your environment. On the other hand, elements
- inserted into an already existing segment always come at the end (except if a hint
- is provided). For instance, after inserting a latecomer goblin with `id==8`:
- [basic_base_3]
- the rendering loop outputs (new element in red):
- [pre
- juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,[role red goblin 8],warrior 2,warrior 6
- ]
- Deletion can be done in the usual way:
- [basic_base_4]
- Now rendering emits:
- [pre
- juggernaut 0,juggernaut 4,goblin 1,goblin 3,goblin 5,goblin 8,warrior 2,warrior 6
- ]
- [endsect]
- [section `boost::function_collection`]
- [import ../example/basic_function.cpp]
- (Code samples from [@boost:/libs/poly_collection/example/basic_function.cpp `basic_function.cpp`].
- C++14 `std::make_unique` is used.)
- Well into the development of the game, the product manager requests that two new
- types of entities be added to the rendering loop:
- * Overlaid messages, such as scores, modelled as `std::string`s.
- * Pop-up windows coming from a third party library that, unfortunately, do not
- derive from `sprite` and use their own `display` member functon for rendering:
- [rolegame_3]
- We then decide to refactor the code so that sprites, messsages and windows are
- stored in dedicated containers:
- [basic_function_1]
- and define our rendering container as a `boost::function_collection` of
- /callable entities/ \u2014function pointers or objects with a function
- call `operator()`\u2014 accepting a `std::ostream&` as a parameter
- [basic_function_2]
-
- which we fill with suitable adaptors for `sprite`s, `std::string`s and
- `window`s, respectively. Lambda functions allow for a particularly terse code.
- [basic_function_3]
- The rendering loop now looks like this:
- [basic_function_4]
- and produces the following for a particular scenario of sprites, messages and
- windows:
- [pre
- juggernaut 0,goblin 1,warrior 2,goblin 3,"stamina: 10,000","game over",'''[pop-up 1]''','''[pop-up 2]'''
- ]
- The container we have just created works in many respects like a
- `std::vector<std::function<render_callback>>`, the main difference being
- that with `boost::function_collection` callable entities of the same type
- are packed together in memory
- [footnote Note that all `sprite`s come into one segment: this is why
- goblins #1 and #3 are not adjacent. Exercise for the reader: change
- the code of the example so that sprites are further segmented according
- to their concrete type.], thus increasing performance (which is the whole
- point of using Boost.PolyCollection), while a vector of `std::function`s
- results in an individual allocation for each entity stored
- [footnote Except when small buffer optimization applies.].
- In fact, the `value_type` elements held by a
- `boost::function_collection` are actually /not/ `std::function`s,
- although they behave analogously and can be converted to `std::function` if needed:
- [basic_function_5]
- There is a reason for this: elements of a polymorphic collection cannot be freely
- assigned to by the user as this could end up trying to insert an object into a
- segment of a different type. So, unlike with `std::function`, this will not work:
- [basic_function_6]
- [endsect]
- [section `boost::any_collection`]
- [import ../example/basic_any.cpp]
- (Code samples from [@boost:/libs/poly_collection/example/basic_any.cpp `basic_any.cpp`].)
- [note Here we just touch on the bare essentials of _Boost.TypeErasure_ needed
- to present `boost::any_collection`. The reader is advised to read
- Boost.TypeErasure documentation for further information.]
- After measuring the performance of the latest changes, we find that rendering
- is too slow and decide to refactor once again: if we could store all the
- entities --sprites, messages and windows-- into one single container, that would
- eliminate a level of indirection. The problem is that these types are totally
- unrelated to each other.
- _Boost.TypeErasure_ provides a class template `boost::type_erasure::any<Concept>`
- able to hold an object of whatever type as long as it conforms to the interface
- specified by `Concept`. In our case, we find it particularly easy to implement
- a common interface for rendering by providing overloads of `operator<<`
- [basic_any_1]
- so that we can use it to specify the interface all entities have to adhere to:
- [basic_any_2]
- The collection just created happily accepts insertion of heterogeneous entities
- (since interface conformity is silently checked at compile time)
- [basic_any_3]
- and rendering becomes
- [basic_any_4]
- with output
- [pre
- '''[pop-up 1]''','''[pop-up 2]''',juggernaut 0,goblin 1,goblin 3,warrior 2,"stamina: 10,000","game over"
- ]
- As was the case with `boost::function_collection`, this container is similar
- to a `std::vector<boost::type_erasure::any<Concept>>` but has better performance
- due to packing of same-type elements. Also, the `value_type` of a
- `boost::any_collection<Concept>` is /not/ `boost::type_erasure::any<Concept>`,
- but a similarly behaving entity
- [footnote Actually, it is
- `boost::type_erasure::any<Concept2,boost::type_erasure::_self&>` for some
- internally defined `Concept2` that extends `Concept`.].
- In any case, we are not accessing sprites through an abstract `sprite&`
- anymore, so we could as well dismantle the virtual hierarchy and implement
- each type autonomously: this is left as an exercise to the reader.
- [endsect]
- [endsect]
- [section Deeper into the segmented nature of Boost.PolyCollection]
- [import ../example/segmented_structure.cpp]
- (Code samples from [@boost:/libs/poly_collection/example/segmented_structure.cpp `segmented_structure.cpp`].
- C++14 `std::make_unique` is used.)
- [section Type registration]
- Getting back to our [link poly_collection.tutorial.basics.boost_base_collection `boost::base_collection`]
- example, suppose we want to refactor the populating code as follows:
- [segmented_structure_1]
- Unexpectedly, this piece of code throws an exception of type
- [link poly_collection.reference.header_boost_poly_collection_exc.class_unregistered_type `boost::poly_collection::unregistered_type`].
- What has changed from our original code?
- Suppose a `warrior` has been created by `make_sprite`. The statement
- `c.insert(*make_sprite())` is passing the object as a `sprite&`: even though
- `boost::base_collection` is smart enough to know that the object is actually
- derived from `sprite` (by using
- [@http://en.cppreference.com/w/cpp/language/typeid `typeid()`]) and
- [@https://en.wikipedia.org/wiki/Object_slicing slicing] is to be avoided,
- there is no way that a segment for it can be created without accessing
- the type `warrior` /at compile time/ for the proper internal class templates
- to be instantiated
- [footnote If this is conceptually difficult to grasp, consider the potentially
- more obvious case where `warrior` is defined in a dynamic module linked to
- the main program: the code of `boost::base_collection`, which has been compiled
- before linking, cannot even know the size of this as-of-yet unseen class, so
- hardly can it allocate a segment for the received object.].
- This did not happen in the pre-refactoring code because objects were passed
- as references to their true types.
- A type is said to be /registered/ into a polymorphic collection if
- there is a (potentially empty) segment created for it. This can be checked
- with:
- [segmented_structure_2]
- Registration happens automatically when the object is passed as a reference
- to its true type or
- [link poly_collection.tutorial.insertion_and_emplacement.emplacement `emplace`]'d,
- and explicitly with
- `register_types`:
- [segmented_structure_3]
- Once `T` has been registered into a polymorphic collection, it remains
- so regardless of whether objects of type `T` are stored or not, except if
- the collection is moved from, assigned to, or swapped.
- As slicing is mainly an issue with OOP, `unregistered_type` exceptions are
- expected to be much less frequent with `boost::function_collection` and
- `boost::any_collection`. Contrived examples can be found, though:
- [segmented_structure_4]
- [endsect]
- [section Segment-specific interface]
- For most of the interface of a polymorphic collection, it is possible to only
- refer to the elements of a given segment by providing either their type or
- `typeid()`. For instance:
- [segmented_structure_5]
- Note that any of these (except
- [link poly_collection.tutorial.deeper_into_the_segmented_nature.reserve `reserve`])
- will throw `boost::poly_collection::unregistered_type` if the type is not
- registered. Segment-specific addressability also includes traversal:
- [endsect]
- [section Local iterators]
- The following runs only over the `warrior`s of the collection:
- [segmented_structure_6]
- Output:
- [pre
- warrior 2,warrior 6
- ]
- `begin|end(typeid(T))` return objects of type `local_base_iterator`
- associated to the segment for `T`. These iterators dereference to the same
- value as regular iterators (in the case of `boost::base_collection<base>`,
- `base&`) but can only be used to traverse a given segment (for instance,
- `local_base_iterator`'s from different segments cannot be compared between them).
- In exchange, `local_base_iterator` is a _RandomAccessIterator_, whereas
- whole-collection iterators only model _ForwardIterator_.
- A terser range-based `for` loop can be used with the convenience `segment`
- member function:
- [segmented_structure_7]
- Even more powerful than `local_base_iterator` is `local_iterator<T>`:
- [segmented_structure_8]
- This appends a `"super"` prefix to the `rank` data member of existing warriors:
- [pre
- superwarrior 2,superwarrior 6
- ]
- The observant reader will have noticed that in order to access `rank`, which
- is a member of `warrior` rather than its base class `sprite`, `first` (or
- `x` in the range `for` loop version) has to refer to a `warrior&`, and this
- is precisely the difference between `local_iterator<warrior>` (the type
- returned by `begin<warrior>()`) and `local_base_iterator`.
- `local_iterator<warrior>` is also a _RandomAccessIterator_: for most respects,
- \[`begin<T>()`, `end<T>()`) can be regarded as a range over an array of `T`
- objects. `local_iterator<T>`s can be explicitly converted to
- `local_base_iterator`s. Conversely, if a `local_base_iterator` is associated
- to a segment for `T`, it can then be explictly converted to a
- `local_iterator<T>` (otherwise the conversion is undefined behavior).
- The figure shows the action scopes of all the iterators associated to
- a polymorphic collection (`const_` versions not included):
- [$ poly_collection/img/poly_collection_iterators.png]
- We have yet to describe the bottom part of the diagram.
- Whereas `segment(typeid(T))` is used to range over the /elements/
- of a particular segment, `segment_traversal()` returns an object for ranging over
- /segments/, so that the whole collection can be processed with a nested
- segment-element `for` loop like the following:
- [segmented_structure_9]
- Segment decomposition of traversal loops forms the basis of
- [link poly_collection.tutorial.algorithms improved-performance algorithms].
- [endsect]
- [section Reserve]
- Much like `std::vector`, segments can be made to reserve memory in
- advance to minimize reallocations:
- [segmented_structure_10]
- If there is no segment for the indicated type (here, `goblin`), one is
- automatically created. This is in contrast with the rest of segment-specific
- member functions, which throw
- [link poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration
- `boost::poly_collection::unregistered_type`].
- `reserve` can deal with all segments at once. The following
- [segmented_structure_11]
- instructs every /existing/ segment to reserve 1,000 elements. If a
- segment is created later (through element insertion or with
- [link poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration
- type registration]), its capacity will be different.
- [note Unlike standard containers, collection-level `capacity()` and
- `max_size()` are not provided because their usual semantics cannot be
- applied to Boost.PolyCollection: for instance, `capacity()` is typically
- used to check how many elements can be inserted without reallocation,
- but in a segmented structure that depends on the exact types of the
- elements and whether they are registered or not.
- ]
- [endsect]
- [endsect]
- [section Insertion and emplacement]
- [import ../example/insertion_emplacement.cpp]
- (Code samples from [@boost:/libs/poly_collection/example/insertion_emplacement.cpp `insertion_emplacement.cpp`].)
- We already know that `insert(x)`, without further positional information,
- stores `x` at the end of its associated segment. When a regular iterator `it`
- is provided, insertion happens at the position indicated if both `it` and
- `x` belong in the same segment; otherwise, `it` is ignored. For instance,
- if our sprite collection has the following entities:
- [pre
- juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,warrior 2,warrior 6
- ]
- then this code:
- [insertion_emplacement_1]
- puts the new `juggernaut` at the beginning:
- [pre
- [role red juggernaut 8],juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,...
- ]
- whereas the position hint at
- [insertion_emplacement_2]
- is ignored and the new `goblin` gets inserted at the end of its segment:
- [pre
- juggernaut 8,...,juggernaut 7,goblin 1,goblin 3,goblin 5,[role red goblin 9],warrior 2,...
- ]
- [link poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators Local iterators]
- can also be used to indicate the insertion position:
- [insertion_emplacement_3]
- [pre
- juggernaut 8,juggernaut 0,[role red juggernaut 10],juggernaut 4,juggernaut 7,goblin 1,...
- ]
- There is a caveat, though: when using a local iterator, the element inserted
- /must belong to the indicated segment/:
- [insertion_emplacement_4]
- Member functions are provided for range insertion, with and without a position
- hint:
- [insertion_emplacement_5]
- As [link poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration already explained],
- care must be taken that types be pre-registered into the collection if
- they are not passed as references to their actual type. So, why did not
- this line
- [insertion_emplacement_6]
- throw `boost::poly_collection::unregistered_type`? As it happens, in the
- special case where the inserted range belongs to a polymorphic collection
- of the same type, registration is done automatically
- [footnote That is, Boost.PolyCollection has enough static information to
- do type registration without further assistance from the user.].
- [#poly_collection.tutorial.insertion_and_emplacement.emplacement]
- Emplacement is slightly different for Boost.PolyCollection than with
- standard containers. Consider this attempt at emplacing a `goblin`:
- [insertion_emplacement_7]
- If examined carefully, it is only natural that the code above not compile:
- Boost.PolyCollection cannot possibly know that it is precisely a `goblin`
- that we want to emplace and not some other type constructible from an `int`
- (like `warrior`, `juggernaut` or an unrelated class). So, the type of
- the emplaced element has to be specified explicitly:
- [insertion_emplacement_8]
- As with `insert`, a position can be indicated for emplacing:
- [insertion_emplacement_9]
- Note the naming here: `emplace_hint` is used when the position is indicated with
- a regular iterator, and for local iterators it is `emplace_pos`.
- [endsect]
- [section Exceptions]
- [import ../example/exceptions.cpp]
- (Code samples from [@boost:/libs/poly_collection/example/exceptions.cpp `exceptions.cpp`].)
- Besides the usual exceptions like
- [@http://en.cppreference.com/w/cpp/memory/new/bad_alloc `std::bad_alloc`] and
- those generated by user-provided types, polymorphic collections can throw the following:
- * `boost::poly_collection::unregistered_type`
- * `boost::poly_collection::not_copy_constructible`
- * `boost::poly_collection::not_equality_comparable`
- The situations in which the first is raised have been
- [link poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration already discussed];
- let us focus on the other two.
- We have a new type of sprite in our game defined by the non-copyable
- class `elf`:
- [rolegame_4]
- and we use it without problems until we write this:
- [exceptions_1]
- The first insertion works because the `elf` object passed is /temporary/
- and can be /moved/ into the container, but the second statement actually
- needs to /copy/ the `elf` elements in `c` to `c2`, hence the exception.
- The potentially surprising aspect of this behavior is that standard
- containers signal this kind of problems by /failing at compile time/.
- Here we cannot afford this luxury because the exact types contained in a
- polymorphic collection are not known until run time (for instance,
- if `elf` elements had been erased before copying `c` to `c2` everything
- would have worked): basically, the deferral of errors from compile time
- to run time is an intrinsic feature of dynamic polymorphism.
- In the same vein, equality comparison requires that elements themselves
- be equality comparable:
- [exceptions_2]
- The above is unremarkable once we notice we have not defined `operator==`
- for any `sprite`. The problem may go unnoticed for quite some time, however,
- because determining that two polymorphic collections are equal (i.e.
- all their non-empty segments are equal) can return `false` without
- comparing anything at all (for instance, if segment sizes differ), in which
- case no exception is thrown.
- [note Operators for `<`, `<=`, `>` and `>=` comparison are not provided
- because /segment/ order is not fixed and may vary across otherwise
- identical collections. The situation is similar to that of standard
- [@http://en.cppreference.com/w/cpp/named_req/UnorderedAssociativeContainer unordered
- associative containers.]
- ]
- These three are all the intrinsic exceptions thrown by Boost.PolyCollection.
- The implication is that if a type is _CopyConstructible_,
- _MoveAssignable_ (or move construction does not throw) and _EqualityComparable_, then
- the entire interface of Boost.PolyCollection is unrestrictedly available for it
- [footnote Provided, of course, that the type has the /right/ to be in the collection,
- that is, it is derived from the specified base, or callable with the specified
- signature, etc.].
- [endsect]
- [section Algorithms]
- [import ../example/algorithms.cpp]
- (Code samples from [@boost:/libs/poly_collection/example/algorithms.cpp `algorithms.cpp`].
- C++14 generic lambda expressions are used.)
- The ultimate purpose of Boost.PolyCollection is to speed up the processing of
- large quantities of polymorphic entities, in particular for those operations
- that involve linear traversal as implemented with a `for`-loop or using the
- quintessential _std::for_each_ algorithm.
- [algorithms_1]
- Replacing the container used in the program from classic alternatives to
- Boost.PolyCollection:
- * `std::vector<base*>` (or similar) → `boost::base_collection<base>`
- * `std::vector<std::function<signature>>` → `boost::function_collection<signature>`
- * `std::vector<boost::type_erasure::any<concept_>>` → `boost::any_collection<concept_>`
- is expected to increase performance due to better caching and branch prediction
- behavior. But there is still room for improvement.
- Consider this transformation of the code above using a double
- segment-element loop (based on the
- [link poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators local iterator]
- capabilities of Boost.PolyCollection):
- [algorithms_2]
- Although not obvious at first sight, this version of the same basic operation
- is actually /faster/ than the first one: for a segmented structure such as used
- by Boost.PolyCollection, each iteration with the non-local iterator passed to
- `std::for_each` involves:
- # hopping to next position in the segment,
- # checking for /end of segment/ (always),
- # if at end (infrequent), selecting the next segment,
- # checking for /end of range/ (always),
- whereas in the second version, iteration on the inner loop, where most
- processing happens, is a simple increment-and-check operation, that is,
- there is one less check (which happens at the much shorter outer loop). When
- the workload of the algorithm (the actually useful stuff done with the elements
- themselves) is relatively light, the overhead of looping can be very
- significant.
- To make it easier for the user to take advantage of faster segment-element
- looping, Boost.PolyCollection provides its own version of `for_each` based
- on that technique:
- [algorithms_3]
- `boost::poly_collection::for_each` has the same interface and behavior as
- `std::for_each` except for the fact that it only works for (non-local)
- iterators of a polymorphic container
- [footnote For any other type of iterator, it is guaranteed not to compile.].
- Versions of other standard algorithms are provided as well:
- [algorithms_4]
- In fact, variants are given of most (though not all) of the algorithms in
- [@http://en.cppreference.com/w/cpp/algorithm `<algorithm>`]
- among those that are compatible with polymorphic collections
- [footnote For example, algorithms requiring bidirectional iterators or a higher
- category are not provided because polymorphic collections have forward-only
- iterators.].
- Check the [link poly_collection.reference.header_boost_poly_collection_alg reference]
- for details.
- [section Type restitution]
- By /type restitution/ we mean the generic process of getting a concrete entity
- from an abstract one by providing missing type information:
- [algorithms_5]
- Type restitution has the potential to increase performance. Consider for
- instance the following:
- [algorithms_6]
- Behaviorwise this code is equivalent to simply executing `std::cout<<r<<"\n"`,
- but when type restitution succeeds the statement `std::cout<<str<<"\n"` is
- skipping a virtual-like call that would have happened if `r` were used instead.
- From a general point of view, supplying the compiler with extra type
- information allows it to perform more optimizations than in the abstract case,
- inlining being the prime example.
- All Boost.PolyCollection algorithms accept an optional list of types for
- restitution. Let us use the
- [link poly_collection.tutorial.basics.boost_any_collection `boost::any_collection`]
- scenario to illustrate this point:
- [algorithms_7]
- Output:
- [pre
- warrior 2,warrior 6,[pop-up 1],[pop-up 2],juggernaut 0,juggernaut 4,
- juggernaut 7,goblin 1,goblin 3,goblin 5,"stamina: 10,000","game over"
- ]
- This rendering loop differs from the non-restituting one in two aspects:
- * A list of types is provided as template arguments to the algorithm. This is
- an indication that the types /may/ be actually present in the collection, not
- a promise. Also, the list of types need not be exhaustive, that is, some
- unlisted types could be present in the collection \u2014in the example above,
- the loop traverses *all* elements (including `std::string`s and `window`s),
- not only those corresponding to restituted types. In general, the more types
- are restituted, the greater the potential improvement in performance.
- * The lambda function passed is a generic one accepting its argument as
- `const auto&`
- [footnote This requires C++14, but the same effect can be achieved in C++11
- providing an equivalent, if more cumbersome, functor with a templatized
- call operator.].
- Internally, `boost::poly_collection::for_each` checks for each segment if its
- type, say `T`, belongs in the type restitution list: if this is the case, the lambda
- function is passed a `const T&` rather than the generic
- `const boost::any_collection::value_type&`. For each restituted type we are
- saving indirection calls and possibly getting inlining optimizations, etc.
- As we see in the
- [link poly_collection.performance performance section], the speedup can be
- very significant.
- Type restitution works equally for the rest of collections of
- Boost.PolyCollection. When using `boost::base_collection`, though, the case
- of improved performance is more tricky:
- [algorithms_8]
- The problem here is that, even though the argument to the lambda function will
- be restituted (when appropriate) to `warrior&`, `juggernaut&` or `goblin&`,
- using it still involves doing a virtual function call in `s.render(std::cout)`.
- Whether this call is resolved to a non-virtual one depends on the quality
- of implementation of the compiler:
- * If the concrete class is marked as
- [@http://en.cppreference.com/w/cpp/language/final `final`], the compiler /in
- principle/ has enough information to get rid of the virtual function call.
- * Other than this,
- [@http://hubicka.blogspot.com.es/2014/01/devirtualization-in-c-part-1.html ['devirtualization]]
- capabilities /may/ be able to figure out that the type restitution scenario
- is actually casting the element to its true type, in which case, again, virtual
- calls are not needed.
- [endsect]
- [endsect]
- [endsect]
- [section Performance]
- [def _vs2015_x86_ Visual Studio 2015 x86]
- [def _vs2015_x64_ Visual Studio 2015 x64]
- [def _gcc63_x64_ GCC 6.3 x64]
- [def _clang40_x64_ Clang 4.0 x64]
- [template perf_fig[name environment file]
- [section [environment]]
- [role aligncenter
- '''<inlinemediaobject>
- <imageobject><imagedata fileref="'''poly_collection/img/[file].png'''"/></imageobject>
- </inlinemediaobject>'''
- ]
- [role aligncenter [*[name], [environment]]]
- [endsect]
- ]
- [import ../example/perf.cpp]
- (Testing program at [@boost:/libs/poly_collection/example/perf.cpp `perf.cpp`].)
- We ran tests to measure the performance of the containers of
- Boost.PolyCollection in two scenarios:
- * Insertion of elements.
- * Linear traversal and processing with `std::for_each` and `boost::poly_collection::for_each`
- (with and without
- [link poly_collection.tutorial.algorithms.type_restitution type restitution]).
- As a comparison baseline we used containers and facilities from the
- standard library and Boost (details below). Tests were run in the
- following environments:
- * *_vs2015_x86_*: Visual C++ 2015 in 32-bit (x86) release mode, Windows 7 64-bit, Intel Core i5-2520M @2.5GHz
- * *_vs2015_x64_*: Visual C++ 2015 in 64-bit (x64) release mode, same machine
- * *_gcc63_x64_*: GCC 6.3 release mode, Xubuntu 17.04 x64, Intel Core i7-5820 @3.3GHz
- * *_clang40_x64_*: Clang 4.0 release mode, same machine
- [section Container definitions]
- [section `boost::base_collection`]
- * Baseline container: `ptr_vector` = `boost::ptr_vector<base>`
- * Polymorphic collection: `base_collection` = `boost::base_collection<base>`
- * Element types: `T1` = `derived1`, `T2` = `derived2`, `T3` = `derived3`
- [perf_base_types]
- [endsect]
- [section `boost::function_collection`]
- * Baseline container: `func_vector` = `std::vector<std::function<int(int)>>`
- * Polymorphic collection: `function_collection` = `boost::function_collection<int(int)>`
- * Element types: `T1` = `concrete1`, `T2` = `concrete2`, `T3` = `concrete3`
- [perf_function_types]
- [endsect]
- [section `boost::any_collection`]
- * Baseline container: `any_vector` = `std::vector<boost::type_erasure::any<concept_>>`
- * Polymorphic collection: `any_collection` = `boost::any_collection<concept_>`
- * Element types: `T1` = `int`, `T2` = `double`, `T3` = `char`
- [perf_any_types]
- [endsect]
- [endsect]
- [section Insertion tests]
- Tests measure the time taken to insert /n/ elements (/n/ between
- 10'''<superscript>2</superscript>''' and 10'''<superscript>7</superscript>''')
- from a source of values with types following the cyclic sequence
- `T1` `T1` `T2` `T2` `T3` `T1` `T1` `T2` `T2` `T3` ···
- No `reserve` operation is done before insertion.
- The figures show resulting times in nanoseconds/element.
- The horizontal axis is logarithmic.
- [section Results for `boost::base_collection`]
- [perf_fig Insertion.._vs2015_x86_..insert_base_vs2015_x86]
- [perf_fig Insertion.._vs2015_x64_..insert_base_vs2015_x64]
- [perf_fig Insertion.._gcc63_x64_..insert_base_gcc63_x64]
- [perf_fig Insertion.._clang40_x64_..insert_base_clang40_x64]
- [endsect]
- [section Results for `boost::function_collection`]
- [perf_fig Insertion.._vs2015_x86_..insert_function_vs2015_x86]
- [perf_fig Insertion.._vs2015_x64_..insert_function_vs2015_x64]
- [perf_fig Insertion.._gcc63_x64_..insert_function_gcc63_x64]
- [perf_fig Insertion.._clang40_x64_..insert_function_clang40_x64]
- [endsect]
- [section Results for `boost::any_collection`]
- [perf_fig Insertion.._vs2015_x86_..insert_any_vs2015_x86]
- [perf_fig Insertion.._vs2015_x64_..insert_any_vs2015_x64]
- [perf_fig Insertion.._gcc63_x64_..insert_any_gcc63_x64]
- [perf_fig Insertion.._clang40_x64_..insert_any_clang40_x64]
- [endsect]
- [endsect]
- [section Processing tests]
- Tests measure the time taken to traverse a container of size
- /n/ (/n/ between
- 10'''<superscript>2</superscript>''' and 10'''<superscript>7</superscript>''')
- and execute an operation on each of its elements. The operation for
- `boost::base_collection` and `boost::function_collection` (and the associated
- baseline containers) is defined as
- [perf_for_each_callable]
- whereas for `boost::any_collection` we use
- [perf_for_each_incrementable]
- The baseline container is tested with three different setups:
- * Directly as initialized by the process described for the
- [link poly_collection.performance.insertion_tests insertion tests].
- The sequence of types is complex enough that CPU's branch prediction mechanisms
- are not able to fully anticipate it
- [footnote This has been verified empirically: simpler cycles did indeed
- yield better execution times.]. As elements are ordered according to their
- construction time, certain degree of memory contiguity is expected.
- * With an extra post-insertion stage by which elements are sorted
- according to their `typeid()`. This increases branch prediction
- efficiency at the expense of having worse cache friendliness.
- * With an extra post-insertion stage that randomly
- shuffles all the elements in the container. This is the worst possible
- scenario both in terms of caching and branch prediction.
- As for the polymorphic collection, three variations are measured:
- * With `std::for_each` (the same as the baseline container).
- * Using `boost::poly_collection::for_each`.
- * Using `boost::poly_collection::for_each` with
- [link poly_collection.tutorial.algorithms.type_restitution /type restitution/]
- of `T1`, `T2` and `T3`.
- The figures show resulting times in nanoseconds/element.
- The horizontal axis is logarithmic.
- [section Results for `boost::base_collection`]
- [perf_fig Processing.._vs2015_x86_..for_each_base_vs2015_x86]
- [perf_fig Processing.._vs2015_x64_..for_each_base_vs2015_x64]
- [perf_fig Processing.._gcc63_x64_..for_each_base_gcc63_x64]
- [perf_fig Processing.._clang40_x64_..for_each_base_clang40_x64]
- [endsect]
- [section Results for `boost::function_collection`]
- [perf_fig Processing.._vs2015_x86_..for_each_function_vs2015_x86]
- [perf_fig Processing.._vs2015_x64_..for_each_function_vs2015_x64]
- [perf_fig Processing.._gcc63_x64_..for_each_function_gcc63_x64]
- [perf_fig Processing.._clang40_x64_..for_each_function_clang40_x64]
- [endsect]
- [section Results for `boost::any_collection`]
- [perf_fig Processing.._vs2015_x86_..for_each_any_vs2015_x86]
- [perf_fig Processing.._vs2015_x64_..for_each_any_vs2015_x64]
- [perf_fig Processing.._gcc63_x64_..for_each_any_gcc63_x64]
- [perf_fig Processing.._clang40_x64_..for_each_any_clang40_x64]
- [endsect]
- [endsect]
- [endsect]
- [include reference.qbk]
- [section Future work]
- A number of features asked by reviewers and users of Boost.PolyCollection are
- considered for inclusion into future versions of the library.
- [section Alternative RTTI systems]
- Boost.PolyCollection can be extended to use _Boost.TypeIndex_ in RTTI-challenged
- scenarios. Taking this idea further, it is not unusual that some environments
- (game engines, for instance) provide their own RTTI framework: an even more
- ambitious extension to Boost.PolyCollection would then be to make it configurable
- for user-provided RTTI through some sort of traits class specifying replacements for
- [@http://en.cppreference.com/w/cpp/types/type_info `std::type_info`]
- and [@http://en.cppreference.com/w/cpp/language/typeid `typeid`].
- [endsect]
- [section Copy traits]
- `boost::base_collection` requires that stored objects be _MoveConstructible_ and
- _MoveAssignable_; unfortunately, it is customary to restrict copying in OOP
- hierarchies to avoid slicing, which would force users to revisit their class
- definitions in order to use Boost.PolyCollection. This can be alleviated by
- offering a configurable traits class where copy and assignment can be defined
- externally
- ``
- template<typename T>
- struct copy_traits
- {
- void construct(void*,T&&);
- void assign(T&,T&&);
- };
- ``
- with default implementations resorting to regular placement `new` and
- `T::operator=`.
- [endsect]
- [section Parallel algorithms]
- C++17 introduces
- [@http://en.cppreference.com/w/cpp/experimental/parallelism parallel algorithms],
- like for instance a parallel version of _std::for_each_; it is only
- natural then to provide the corresponding
- [link poly_collection.tutorial.algorithms Boost.PolyCollection-specific algorithms].
- The segmented nature of polymorphic collections makes them particularly amenable to
- parallel processing.
- [endsect]
- [section `variant_collection`]
- /Closed polymorphism/ is a kind of dynamic polymorphism where the set of implementation
- types is fixed at definition time: the prime example of this paradigm in C++ is
- [@http://en.cppreference.com/w/cpp/utility/variant `std::variant`]. Although
- `boost::any_collection<boost::mpl::vector<>>` can act as a sort of replacement for
- `std::vector<std::variant<T1,...,TN>>`, this is in fact more similar to a
- `std::vector<`[@http://en.cppreference.com/w/cpp/utility/any `std::any`]`>`,
- and a collection class `boost::variant_collection<T1,...,TN>` could be designed to
- better model closed polymorphism and take further advantage of the fact that
- implementation types are fixed (for instance, internal virtual calls can be
- completely eliminated). From a conceptual point of view, this would require introducing
- a new [* `ClosedPolymorphicCollection`] notion and renaming the current
- [link poly_collection.reference.polymorphic_containers.polymorphic_collections [* `PolymorphicCollection`]]
- model to [* `OpenPolymorphicCollection`].
- [endsect]
- [section Ordered polymorphic collections]
- Users have expressed interest in polymorphic collections where elements are kept
- ordered within their segment and optionally duplicates are excluded, much like
- [@http://boost.org/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx `boost::flat_set`/`boost::flat_multiset`]
- do over their internal data vector. The open question remains of whether these
- collections should also guarantee some order between segments (current ones don't)
- to allow for the definition of container-level `operator<` and related operators.
- [endsect]
- [endsect]
- [section Release notes]
- [section Boost 1.72]
- * Maintenance work.
- [endsect]
- [section Boost 1.71]
- * Maintenance work.
- [endsect]
- [section Boost 1.70]
- * Improved handling of stateful allocators and allocator propagation traits,
- after an error reported by Billy O'Neal ([github_pr poly_collection 9]).
- * Fixed a potentially serious bug with an internal cache structure.
- [endsect]
- [section Boost 1.69]
- * Added Boost.PolyCollection-specific versions of algorithms
- `std::for_each_n` and `std::sample`.
- [endsect]
- [section Boost 1.67]
- * Maintenance fixes.
- [endsect]
- [section Boost 1.66]
- * Boost.PolyCollection has been backported to GCC 4.8 to 4.9 and Clang 3.3 to 3.6.
- The version of libstdc++-v3 shipped with GCC 4.8 (which can also be used by Clang)
- has deficiencies that result in the following limitations when using
- Boost.PolyCollection:
- * Stateful allocators are not properly supported.
- * Allocator-extended move construction decays to allocator-extended copy construction.
- * Copy construction crashes if an exception is thrown during element copying.
- * Maintenance fixes.
- [endsect]
- [section Boost 1.65]
- * Initial release.
- [endsect]
- [endsect]
- [section Acknowledgments]
- The library uses [@http://www.pdimov.com/ Peter Dimov]'s
- [@http://www.pdimov.com/cpp2/simple_cxx11_metaprogramming.html implementation
- of `std::make_index_sequence`].
- [@http://manu343726.github.io/ Manu Sánchez] aided immensely with CI setup and
- performance testing. [@http://stackoverflow.com/users/85371/sehe Sehe]
- contributed performance results for GCC 5.2, and
- [@https://www.linkedin.com/in/francisco-jose-tapia-iba%C3%B1ez-4239a07a Francisco
- José Tapia] for Clang 3.9.
- The Boost acceptance review took place between the 3rd and 17th of May, 2017. Thank you
- to Ion Gaztañaga for smoothly managing the process. The following people participated
- with full reviews or valuable comments:
- Pete Bartlett, Hans Dembinski, Dominique Devienne, Edward Diener, Vinnie Falco,
- Ion Gaztañaga, Andrzej Krzemienski, Brook Milligan, Thorsten Ottosen, Steven Watanabe,
- Adam Wulkiewicz. Many thanks to all of them. Steven Watanabe gave crucial help in
- solving some hard problems related to the usage of _Boost.TypeErasure_.
- Boost.PolyCollection was designed and written between rainy
- [@https://es.wikipedia.org/wiki/Viav%C3%A9lez Viavélez], noisy Madrid and beautiful
- [@https://en.wikipedia.org/wiki/C%C3%A1ceres,_Spain Cáceres], August-November, 2016.
- Most of the after-review work in preparation for the official Boost release was done
- in the quiet town of [@https://es.wikipedia.org/wiki/Oropesa_(Toledo) Oropesa] during
- the spring of 2017.
- In memory of Joaquín López Borrella (1939-2015), in memory of Héctor (2004-2017):
- may your ghosts keep us company.
- [endsect]
|