On 8/21/2014 3:12 AM, Joaquin M Lopez Munoz wrote:

Eric Niebler <eniebler <at> boost.org> writes:

...

On 08/20/2014 07:40 AM, Beman Dawes wrote:

...

See http://beman.github.io/ntcts_iterator/

or https://github.com/Beman/ntcts_iterator

The need for such a thing is an unfortunate side-effect of the fact that a range's begin and end iterators must have the same type. I'm building a range library that loosens that restriction and writing a proposal to get it into the standard.

Hi Eric,

This might be connected in a way with your sentinel idea. Some months ago I explored a container-like construct for polymorphic objects that group elements by run-time type so as to greatly speed up for_each processing:

http://bannalia.blogspot.com.es/2014/05/fast-polymorphic-collections.html

This poly_collection class (currently just a sketch to show the underlying ideas) has a for_each member function

template<typename F> F for_each(F f);

that internally dispatches to the different same-type chunks the collection is comprised of:

template<typename F> F for_each(F f) { for(const auto& p:chunks)p.second->for_each(f); return std::move(f); }

The performance gains are massive, as shown in the article. Now, if we wished to use the standard for_each algorithm rather than the provided member function:

poly_collection<base> c; ... std::foreach(c.begin(),c.end(),f);

then poly_collection would have to implement an iterator type that sequentally traverses all the chunks, which implies a fairly expensive increment operation (in pseudocode):

iterator& operator++() { node+=chunk_element_size; if(node==chunk_end()){ node=next_chunk_begin(node); } return *this; }

That is, incrementing involves checking against chunk end, which, combined with the begin!=end check of std::for_each, implies two checks per step. This is slower than poly_collection::for_each, which can get by with just one check per step.

I wonder: maybe a sentinel-based range can be used so that std::for_each(c,f) is as efficient as c.for_each(f) for a poly_collection c?

You're looking for segmented iterators and hierarchical algorithms. Matt Austern wrote a paper about it: http://lafstern.org/matt/segmented.pdf Segmented iterators force you to rewrite all the algorithms. They are a different beast than iterators with sentinels, which are not nearly so invasive. I'm not proposing segmented iterators. Eric

Mathias Gaunard <mathias.gaunard <at> ens-lyon.org> writes:

On 21/08/2014 12:12, Joaquin M Lopez Munoz wrote:

...

Some months ago I explored a container-like construct for polymorphic objects that group elements by run-time type so as to greatly speed up for_each processing:

http://bannalia.blogspot.com.es/2014/05/fast-polymorphic-collections.html

IMHO you're comparing oranges and apples, the memory layout and traversal properties are entirely different.

Absolutely, this is precisely the point of the article: if you are managing collections of polymorphics objects and traversal order is not relevant, you are probably better off using something like poly_collection (or the intrusive structure you mention) rather than std::vector<std::unique_ptr<Base>> (or boost::ptr_vector<Base>, for that matter). Joaquín M López Muñoz Telefónica

Ion Gaztañaga <igaztanaga <at> gmail.com> writes:

El 23/08/2014 20:53, Joaquin M Lopez Munoz escribió:

...

...

On 21/08/2014 12:12, Joaquin M Lopez Munoz wrote:

...

Some months ago I explored a container-like construct for polymorphic objects that group elements by run-time type so as to greatly speed up for_each processing:

http://bannalia.blogspot.com.es/2014/05/ fast-polymorphic-collections.html

[...] if you are managing collections of polymorphics objects and traversal order is not relevant, you are probably better off using something like poly_collection (or the intrusive structure you mention) rather than std::vector<std::unique_ptr<Base>> (or boost::ptr_vector<Base>, for that matter).

An interesting data structure. Erasure also seems a bit curious. I guess you could implement it with an iterator that maybe contains a pointer to a base class and:

-> calls each segment::erase(it); -> if the segment detects the address of the base is inside vector's memory, then : a) Derived *pderived = static_cast<Derived*>(it.base) b) vec_it = segment.vector.begin() + (pderived - &vector[0]) c) segment.vector.erase(vec_it);

Erasure can be implemented without segment detection if iterators are equipped with a pointer (or, better yet, a std::map<std::type_index, pointer>::iterator) to the chunk (or poly_collection_segment_base in the source code terminology) they belong in --after all, something like this is needed to implement interchunk increment.

A container that is not a sequence, unordered but not associative. unordered_collection might be an alternative name.

This name misses the critical feature that elements are polymorphic.

An interesting addition to Boost.Container?

If I had the time :-/ I' ve been considering working a little more on this to turn the initial sketch into something resembling a full-fledged container, but it'd take me some days' work I don't have. Joaquín M López Muñoz Telefónica

Ion Gaztañaga wrote:

An interesting addition to Boost.Container? ;-)

Some time ago I tested a container which should also improve the cacheing, depending on the access pattern. The key point is to separate the hot and cold data so its purpose is slightly different than poly_collection but the idea is similar, to group the same objects together. The idea is to transform a vector of tuples into a tuple of vectors and store tuple's components in separated containers, e.g.: std::vector<std::tuple<T1, T2>> -> std::tuple<std::vector<T1>, std::vector<T2>> The usage should be as close to std::vector as possible, so e.g.: |tuple_vector<std::tuple<T1, T2, T3, ...>> v; v.resize(count); for (int i = 0; i < count; ++i) { T1 t = std::get<0>(v[i]); std::get<0>(v[i]) = ...; }| A thing worth noticing is that the tuple_vector's reference type is a tuple of references: std::tuple<T1&, T2&> The iterator could either store a tuple of iterators of underlying vectors or a ptr to tuple_vector and index. If you wanted to check it out: https://github.com/awulkiew/test-tuple_vector The prototype requires C++11 but such container could be implemented in C++98 as well. Regards, Adam

On 24/08/2014 13:29, Adam Wulkiewicz wrote:

Ion Gaztañaga wrote:

...

An interesting addition to Boost.Container? ;-)

Some time ago I tested a container which should also improve the cacheing, depending on the access pattern. The key point is to separate the hot and cold data so its purpose is slightly different than poly_collection but the idea is similar, to group the same objects together. The idea is to transform a vector of tuples into a tuple of vectors and store tuple's components in separated containers, e.g.:

std::vector<std::tuple<T1, T2>> -> std::tuple<std::vector<T1>, std::vector<T2>>

This is AoS -> SoA conversion. We also do that kind of thing with NT2 containers (this is necessary for vectorization).

The usage should be as close to std::vector as possible, so e.g.:

|tuple_vector<std::tuple<T1, T2, T3, ...>> v; v.resize(count);

for (int i = 0; i < count; ++i) { T1 t = std::get<0>(v[i]); std::get<0>(v[i]) = ...; }|

A thing worth noticing is that the tuple_vector's reference type is a tuple of references:

std::tuple<T1&, T2&>

Could also be any proxy type, that's more flexible. The important aspect is that tuple_vector's reference cannot be value_type&.

Thijs Van Den Berg wrote:

...

...

The usage should be as close to std::vector as possible, so e.g.:

|tuple_vector<std::tuple<T1, T2, T3, ...>> v; v.resize(count);

for (int i = 0; i < count; ++i) { T1 t = std::get<0>(v[i]); std::get<0>(v[i]) = ...; }|

A thing worth noticing is that the tuple_vector's reference type is a tuple of references:

std::tuple<T1&, T2&> Could also be any proxy type, that's more flexible. The important aspect is that tuple_vector's reference cannot be value_type&.

I’ve been looking at heterogenous containers without type erasure using tuple_vectors. My solution was to define an “invoke” function that allowed you to manipulate all (types) of elements in the container.

In this example I have a set of shapes in the tuple_vector like circle, rectangle… and a set of operations like move, rotate that I invoke on all elements.

Here is the C++14 code snippet: http://pastebin.com/s7dBfWDX

AFAIU your approach seems to be more like the static poly_collection mentioned by Joaquin since the purpose is to store the same types of objects in the same containers and then iterate over them all. So internally it looks like this: v1: |Pt|Pt|Pt|Pt| v2: |Line|Line| v2: |Rect| Iteration(Flattening): |Pt|Pt|Pt|Pt||Line|Line||Rect| As Ion wrote in one of the emails, "a container that is not a sequence, unordered but not associative". My container's purpose is to separate hot and cold data. In my tuple_vector there are the same numbers of elements stored in each vector. The i-th elements in each vector are related with each other. It's possible to access one element or all of them. The idea is to make the interface as close to the std::vector<std::tuple<...>> as possible. Internally it looks like this: v1: |D1|D1|D1|D1| v1: |D2|D2|D2|D2| v1: |D3|D3|D3|D3| ^ | <D1,D2,D3> Regards, Adam

Eric Niebler wrote:

On 08/20/2014 07:40 AM, Beman Dawes wrote:

...

See http://beman.github.io/ntcts_iterator/

or https://github.com/Beman/ntcts_iterator The need for such a thing is an unfortunate side-effect of the fact that a range's begin and end iterators must have the same type. I'm building a range library that loosens that restriction and writing a proposal to get it into the standard.

This reminds me about the Boost.Geometry rtree query iterators. The most basic way of querying the rtree is to call a query() member function and pass a set of predicates into it, like this: rtree.query(bgi::intersects(box1) && !bgi::within(box2), std::back_inserter(result)); There is also possible to perform iterative queries implemented as iterators. To get the iterator one calls a member function the same way as the one above: rtree.qbegin(bgi::intersects(box1) && !bgi::within(box2)); this means that the type of an iterator depends on the type of the query. But the container in general should also define the type of an iterator. To keep the story short, I was forced to implement type-erased iterators. This also allowed me to internally use different iterators for begin and end. Otherwise it would be required to pass pass the query also to qend() method, since its type would also depend on the query's type. So the user may just write: rtree.qend(); to get the end iterator. Technically the end iterator of course could have the same type and also store the query however then iterative queries are slower because the iterator is bigger. And as you can imagine type-erased iterators are also slower than "regular" ones. The straightforward solution would be to allow different types of begin and end iterators but they'd require C++11/auto or Boost.Typeof and would be basically unusable since STL algorithms and Boost.Range requires the same types. Have you thought about relaxing this requirement for the whole STL (algorithms, containers ctors, etc.)? Your proposal could solve the problem described above, as long as it wouldn't be a good habit (wasn't done in one of the STL containers) to define some subrange types in the containers, since again - the type of a query range would depend on the type of a query. So something like this could work: auto rng = rtree.qrange(bgi::intersects(box1) && !bgi::within(box2)); or if they were also supported by a range-based for loop: for (auto g : rtree.qrange(bgi::intersects(box1) && !bgi::within(box2))) // something Regards, Adam

Hi, 2014-08-22 5:34 GMT+08:00 pfultz2 <pfultz2@yahoo.com>:

...

There is also possible to perform iterative queries implemented as iterators. To get the iterator one calls a member function the same way as the one above:

rtree.qbegin(bgi::intersects(box1) && !bgi::within(box2));

this means that the type of an iterator depends on the type of the query. But the container in general should also define the type of an iterator. To keep the story short, I was forced to implement type-erased iterators. This also allowed me to internally use different iterators for begin and end. Otherwise it would be required to pass pass the query also to qend() method, since its type would also depend on the query's type. So the user may just write:

rtree.qend();

to get the end iterator. Technically the end iterator of course could have the same type and also store the query however then iterative queries are slower because the iterator is bigger. And as you can imagine type-erased iterators are also slower than "regular" ones.

There is no need to use type-erased iterators here.

They're required to provide STL-like interface: rtree_t::const_query_iterator it = rtree.begin(/*some query*/);

Instead it should return a range:

rtree.qrange(bgi::intersects(box1) && !bgi::within(box2));

Then the range that is returned will know the query type that is needed for the `.begin()` and `.end()` member functions. Plus, returning a range is helpful if the user wants to use it in a range-for loop or with Boost.Range.

Yes, and in this case various queries would produce various types of Ranges. So the user would be forced to use BOOST_TYPEOF(), C++11 auto keyword or one of the Boost.Range algorithms or adaptors.

Also, I'm not sure using different iterators types in this case has a boost in performance, since the end iterator is pointing to a 'valid' place in the sequence, unlike an end iterator for a null-terminated string which is just a placeholder for the end.

The query iterator must store query predicates. If the end iterator has the same type as e.g. the begin iterator it must store it as well, and those are fat iterators. So there is a tiny performance penalty related to the initialization and copying of unneeded data into the end iterator. And the rtree query end iterator is really a sentinel because the iterator returned by begin() knows exactly when the iteration should be stopped, e.g. when it already iterated over k-nearest objects or there is no other bounding box intersecting some passed region, etc. Well, the Range could store the required data and the iterators returned by the Range could only store references/pointers to this Range. So if it was guaranteed that the Range returning some Iterators would be forced to exist as long as those Iterators exist, this approach should work. But I'm not sure if there is such requirement. Regards, Adam