Vectors - iterators vs indexing

[boltar2003]

Hi

I suspect this is a question that gets asked a lot so apologies for that,
but google hasn't given me any definitive answers.

Is there any speed difference between going through a vector sequentially
using indexing or using iterators?

Thanks for any help

B2003

 

[AnonMail2005]

Hi

I suspect this is a question that gets asked a lot so apologies for that,
but google hasn't given me any definitive answers.

Is there any speed difference between going through a vector sequentially
using indexing or using iterators?

Thanks for any help

B2003

Try doing a speed comparison. I suspect that iterators are faster.
With an iterator, you're doing an addition to advance a pointer. With
indexing, you need to do a multiply to get at the offset.

HTH

 

[Victor Bazarov]

Try doing a speed comparison. I suspect that iterators are faster.
With an iterator, you're doing an addition to advance a pointer. With
indexing, you need to do a multiply to get at the offset.

HTH

There is no doubt that when it comes to counting microseconds, one needs
to do a comparison of two runs instead of theorising. However, consider
this: if your iterations do not depend on each other, index-based
iterations are easily paralleliseable, whereas iterator-based ones aren't.

V

 

[Bo Persson]

Try doing a speed comparison. I suspect that iterators are faster.
With an iterator, you're doing an addition to advance a pointer.
With indexing, you need to do a multiply to get at the offset.

HTH

The optimizer can add sizeof(element) to move from one offset to the
next.

So, if it is important, the advice is as you say "Try doing a speed
comparison".


Bo Persson

 

[White Wolf]

There is no doubt that when it comes to counting microseconds, one needs
to do a comparison of two runs instead of theorising. However, consider
this: if your iterations do not depend on each other, index-based
iterations are easily paralleliseable, whereas iterator-based ones aren't.

I must be missing something, because I cannot see how that can happen.
Both index and iterator based jobs do exactly the same thing (concerning
threads), AFAIU. They give you an address based on the result of a
calculation. Whether or not an iteration can be affectively
parallelized depends on two other things:

- Does the iterator support random access (best case) or at least
forward access (input iterators won't work). Of course, in the latter
case we do not have index available, so let's stick with random access
iterators. We have random access iterator.

- The second thing is the "body" of that iteration. What do you do with
the elements? Is that a pure operation (for_each with a normal everyday
stateless, pure functor) or do the operation on element N depend on the
previous operations on elems begin...N-1?

What did I miss?

BR, WW

 

[Victor Bazarov]

I must be missing something, because I cannot see how that can happen.
Both index and iterator based jobs do exactly the same thing (concerning
threads), AFAIU. They give you an address based on the result of a
calculation. Whether or not an iteration can be affectively
parallelized depends on two other things:

- Does the iterator support random access (best case) or at least
forward access (input iterators won't work). Of course, in the latter
case we do not have index available, so let's stick with random access
iterators. We have random access iterator.

- The second thing is the "body" of that iteration. What do you do with
the elements? Is that a pure operation (for_each with a normal everyday
stateless, pure functor) or do the operation on element N depend on the
previous operations on elems begin...N-1?

What did I miss?

Well, you missed perhaps a couple of things. First, I didn't say
"effectively" (I take it you meant that), I said "easily". In many
cases it is enough to use OMP and say #pragma parallel for, and your
loop is parallelised. The compiler knows nothing about iterators, so
parallelisation of those is up to you. And, two, I did say "if
iterations do not depend on each other", which you just repeated (as if
in disagreement).

V

 

[James Kanze]

[...]

I must be missing something, because I cannot see how that can
happen. Both index and iterator based jobs do exactly the
same thing (concerning threads), AFAIU. They give you an
address based on the result of a calculation. Whether or not
an iteration can be affectively parallelized depends on two
other things:

- Does the iterator support random access (best case) or at
least forward access (input iterators won't work). Of course,
in the latter case we do not have index available, so let's
stick with random access iterators. We have random access
iterator.

- The second thing is the "body" of that iteration. What do
you do with the elements? Is that a pure operation (for_each
with a normal everyday stateless, pure functor) or do the
operation on element N depend on the previous operations on
elems begin...N-1?

What did I miss?

You both seem to have missed that the compiler can only do the
parallization if it can see the internal pointer of std::vector
(usually the case, since all of the relevant functions should be
inlined), and prove that there is no aliasing of that pointer,
and that it's value is a loop invariant. Once the compiler has
done that, of course, iterators or indexes are all the same to
the compiler---it will map one into the other, and use whichever
is fastest in the given circumstances.

 

[White Wolf]

Well, you missed perhaps a couple of things. First, I didn't say
"effectively" (I take it you meant that), I said "easily". In many
cases it is enough to use OMP and say #pragma parallel for, and your
loop is parallelised. The compiler knows nothing about iterators, so
parallelisation of those is up to you. And, two, I did say "if
iterations do not depend on each other", which you just repeated (as if
in disagreement).

Well, what I was thinking about is what Herb and MS did together, where
in their implementation of std::for_each they do the parallelization.

Also, most vector implementations (not in debug mode) will typedef the
iterator to be a simple T*, so there should be no problem with that
pragma,. If it works with a for loop based on indices, it should work
with a for using iterator. Unless I missed something again.

BR, WW

 

[Victor Bazarov]

[..] most vector implementations (not in debug mode) will typedef the
iterator to be a simple T*, so there should be no problem with that
pragma,. If it works with a for loop based on indices, it should work
with a for using iterator. Unless I missed something again.

Uh... I haven't seen any OMP implementation that was capable of
parallelising a loop based on pointers. Probably because originally OMP
was written for Fortran which isn't really known for its pointers...
But then again, I can be easily missing something

V