Is it ok to add iterators to blocked_range?

[robert_jay_gould]

I had been using blocked_range a bit, but was getting tired of writing custom functor objects all the time, so I began trying to use boost/foreach and boost/mem_fn, but got compiler errors about lack of iterator, so looked into the header and found blocked_range doesn't have iterators. It has a const_iterator, but not an iterator. Also the const_iterator isn't actually const at all.

So I added to file:blocked_range.h around line:50

//! A range over which to iterate.

/** @ingroup algorithms */

template

class blocked_range {

public:

//! Type of a value

/** Called a const_iterator for sake of algorithms that need to treat a blocked_range

as an STL container. */

typedef Value iterator; //added this here

typedef const Value const_iterator; //fixed this here

This way I can use boost goodness to simplifywritingloops.

Anyways since const_iterator should have been const anyways I guess this should be backwards compatible with most stuff out there.

Any thoughts?

[AJ13]

There is nothing preventing you from writing something like for_each, but it will have to operate on the Range concept, not use iterators. Remember that the components from STL and Boost might not mix will with TBB when it comes to parallel code. You will have to iterate over the ranges, not the elements of the blocked_range.

I've thought myself about the relation of iterators to ranges. After some thought, I came to the conclusion that iterators are not parallel at all. So long as I have a range, I can do more parallelism. As soon as I introduce the notion of an iterator, I'm writing sequential code. That's my view, and hope this answers your question as to why iterators in a blocked_range might not be a good idea.

BTW, I assume that the idea for having iterators is that within the function body that operates on a range, you want to simplify your work on those elements. I think there could be a better approach to solving that problem, though I need to think a bit on what it might be.

[Alexey-Kukanov]

The blocked_range "iterators" are not really iterators, and you should realize that. The concept of Value for blocked_range has much less requirements than the one for an iterator. blocked_range is most often instantiated with some integer type as the template parameter; obviously dereference of blocked_range::const_iterator is impossible if the latter is actually int.

For the same reason, defining const_iterator as const Value is wrong, because after that you will not even be able to increment and decrement it, whichis required by virtually any use of an iterator, I think.

Defining blocked_range::iterator as Value is probably no more harmless than what we have now.

Could you please share a simple example of how you use boost, andthe equivalent code that uses custom function objects? I wonder why the boost algorithms can not work with our const_iterator but can with non-const one, having in mind that the actual "implementation" does not meet requirements for either one?

[ARCH_R_Intel]

This is a hard problem. The root problem is const.

It is true that the general Range concept, or even the general case of blocked_range, does not necessarily have an obvious iterator. However, the original intent was that blocked_range::const_iterator would be valid if Value itself is an iterator. The blocked_range could then be interpreted as a read-only container. We made it const_iterator because it does not actually modify the blocked_range itself.

But there is another interpretation of a blocked_range: it can be considered a pointer to a subrange of a container. In that case, the constness of the blocked_range itself should have no bearing on whether iterators extracted from it can be used to modify the underlying container. The analogy is with "T*const p". The fact that p is const does not impact whether *p can be modified.

Note that "typedef const Value const_iterator" puts the constat the wrong level of indirection. The const needs to be on the target of the iterator. Alas, as far as I can tell there is no automatic way to map an iterator toits correspondingconst_iterator.

I was hoping that the C++0x Range might offer guidance on this issue, but it solves the problem by knowing what the underlying container is. (See end of 23.1.6.3 of the draft.) However, in the concept_map Range, it does call the resulting type an "iterator", not "const_iterator".

I see two possible solutions. One is to treat a range as a pointer as far as constness:

• Add "typedef Value iterator".
• Keep"typedef Value const_iterator" for backwards compatibility, but deprecate it.
• Change methods "begin() const" and "end() const" to return an iterator.

The second solution is to leave blocked_range as it is, and introduce a new template "container_range that treates constness similarly to the C++0x Range.

- Arch

[robert_jay_gould]

Quoting - AJ

BTW, I assume that the idea for having iterators is that within the function body that operates on a range, you want to simplify your work on those elements. I think there could be a better approach to solving that problem, though I need to think a bit on what it might be.

Yes your right, my goal here is to make life easier to operate on the range of a container w/iterators. Thus after the range has been split for concurrency, the serial work left to do wasbecominga drag, if nothing else.

But thinking about it now that I read the posts, range can work on a simple c-array and possibly other "containers" that aren't really std-like containers at all. So its not really practical to change range for everyone.

However as an idea, with the introduction of "Concepts" for templates in C++0x, TBB could provide iterators into the range if the underlying class provides iterators. That way it could specialize as needed and make things easier when meshing with std/boost like concepts. I'm sure this could also be done now without "Concepts", but the code might become quite byzantine.

[robert_jay_gould]

Quoting - Alexey Kukanov (Intel)

The blocked_range "iterators" are not really iterators, and you should realize that. The concept of Value for blocked_range has much less requirements than the one for an iterator. blocked_range is most often instantiated with some integer type as the template parameter; obviously dereference of blocked_range::const_iterator is impossible if the latter is actually int.

For the same reason, defining const_iterator as const Value is wrong, because after that you will not even be able to increment and decrement it, whichis required by virtually any use of an iterator, I think.

Defining blocked_range::iterator as Value is probably no more harmless than what we have now.

Could you please share a simple example of how you use boost, andthe equivalent code that uses custom function objects? I wonder why the boost algorithms can not work with our const_iterator but can with non-const one, having in mind that the actual "implementation" does not meet requirements for either one?

Thanks for reminding me of that (range's requirements), in my case all ranges happened to be built on std/boost-like containers so it wasn't a problem. But yes it make no sense on a int[].

Here is a simplified example:

void update()

{ //Visit all actors (Order is not critical)

tbb::parallel_for(

tbb::blocked_range(actors_.begin(),actors_.end()),

ApplyUpdate(),

tbb::auto_partitioner()

);

}

class ApplyUpdate

{

public:

void operator()( tbb::blocked_range& r ) const

{

//Serial work

BOOST_FOREACH(actor_t& actor, r)

{

actor.Update();

}

}

};

Now this works when I add the my typedef Value iterator, because I need to modify the objects, and a const_iterator won't do.

As the code stands right now for blocked_range I could pull this off using a const_iterator (defined in range), but then I can't update my objects ( because Update isn't const ). So the iterator and const_iterator are both needed.

The trick here is my range already consists of iterators. So it happens to work.

//For the same reason, defining const_iterator as const Value is wrong, because after that you will not even be able to increment and //decrement it, whichis required by virtually any use of an iterator, I think.

//Defining blocked_range::iterator as Value is probably no more harmless than what we have now.

Yes you are right here, I shouldn't have added the const to Value, it won't allow the iterator to be moved.

[robert_jay_gould]

Quoting - Arch Robison (Intel)

This is a hard problem. The root problem is const.

It is true that the general Range concept, or even the general case of blocked_range, does not necessarily have an obvious iterator. However, the original intent was that blocked_range::const_iterator would be valid if Value itself is an iterator. The blocked_range could then be interpreted as a read-only container. We made it const_iterator because it does not actually modify the blocked_range itself.

But const_iterator just means we can't modify the objects pointed to by the iterator, not that the container can't be changed.

So although its not legal to modify the range, because its a range, const_iterator doesn't help. In the case of a vector modifying the container would cause undefined behavior, probably the same as with range, but you could insert more objects into a container say a map even when using const_iterators, and nothing would break. (Not sure how iteration space might be affected but it'll compile, and reach end)

[Alexey-Kukanov]

Quoting - robert.jay.gould

void operator()( tbb::blocked_range& r ) const

{

//Serial work

BOOST_FOREACH(actor_t& actor, r)

{

actor.Update();

}

}

Now I see; actor (which is the value obtained from an iterator) is updated inside so const_iterator cannot be used.

I think the best thing for the moment would beto define iterator for blocked_range, possibly deprecate const_iterator (if one needs constness, blocked_range<:CONST_ITERATOR> could be used I think); and when C++0x is supported enough, we might use concepts to implement two different kinds of blocked ranges.

[Alexey-Kukanov]

Quoting - Alexey Kukanov (Intel)

... possibly deprecate const_iterator ...

No it seems it should not be deprecated. What if in the example above is rewritten as following?

void operator()( tbb::blocked_range& r ) const

{

BOOST_FOREACH(const actor_t& actor, r) { ... // do something that does not change actor }

}

In this case, boost::for_each would probably require const_iterator over the range, wouldn't it?

Or will this code be rejected by compilers anyway, because even though the range has const_iteratore defined, it would then be recognized as a non-const iterator over actor_list_t and not allowed to use?

As my last guess seems very plausible, it seems then that ideallythe blocked_range<:ITERATOR> should only define iterator but not const_iterator, and vice versa the blocked_range<:CONST_ITERATOR> should only define the const form. I am not sure whether this can be done even with concepts, provided that "there is no automatic way to map an iterator toits correspondingconst_iterator" (and vice versa, I assume).

[Dmitry_Vyukov]

Quoting - Alexey Kukanov (Intel)

void operator()( tbb::blocked_range& r ) const

{

//Serial work

BOOST_FOREACH(actor_t& actor, r)

{

actor.Update();

}

}

Now I see; actor (which is the value obtained from an iterator) is updated inside so const_iterator cannot be used.

I think the best thing for the moment would beto define iterator for blocked_range, possibly deprecate const_iterator (if one needs constness, blocked_range<:CONST_ITERATOR> could be used I think); and when C++0x is supported enough, we might use concepts to implement two different kinds of blocked ranges.

What about providing:

[cpp]TBB_PARALLEL_FOR(actor_t& a, actors_, tbb::auto_partitioner())
{
  a.Update();
}};[/cpp]

?

Underlying tasks will work with ranges of source container, but user functor is called for every single element in the range, so user doesn't see ranges, he works only with single elements.

Looks nice!

[Alexey-Kukanov]

Quoting - Dmitriy V'jukov

What about providing:

TBB_PARALLEL_FOR(actor_t& a, actors_, tbb::auto_partitioner()) { a.Update(); }};

?

Isn't the following even better (with auto_partitioner by default, and other partitionerspossible)?

[cpp]tbb::parallel_for(actors.begin(),actors.end(), [](actor_t& a) {
    a.Update();
});
[/cpp]

[robert_jay_gould]

Quoting - Alexey Kukanov (Intel)

Isn't the following even better (with auto_partitioner by default, and other partitionerspossible)?

[cpp]tbb::parallel_for(actors.begin(),actors.end(), [](actor_t& a) {
    a.Update();
});
[/cpp]

Agreed, this is THE best solution. Now if Lambda was widespread enough...

Also Alexey's BOOST_FOREACH(const arctor_t& a, r){//non modifying work} does work as expected, I actually use that construct too, since I had already added typedef iterator to my blocked_range headers.

As for the TBB_FOR_EACH macro solution proposed, I think I could get that working, but with the weekend here, I don't have the code infront of me, but will try it next week. The main advantage being I could avoid the range operators all together, kindof a poor-mans lambda.

[Dmitry_Vyukov]

Quoting - Alexey Kukanov (Intel)

Isn't the following even better (with auto_partitioner by default, and other partitionerspossible)?

[cpp]tbb::parallel_for(actors.begin(),actors.end(), [](actor_t& a) {
    a.Update();
});
[/cpp]

Definitely it's better... not counting that lambda support in all production compilers will be in 2010, stable implementations will be in 2012, and one can rely on them in library for the general public in 2015 when late adopters will finally upgrade their compilers :)