std::vector: Should [] be faster than an iterator?

Question

0.00/5 (No votes)

See more:

For sequential read access to a C++ std::vector and a modern optimizing compiler, would those more experienced than I guess that an integer subscript would compile to faster-running machine code than a std::vector::iterator, or would an optimizing compiler probably be clever enough to generate roughly the same code in either case?

And yes, I know the caveats on "what would compile to the fastest code?": (a.) to really know, you have to benchmark or profile; (b.) except in unusual situations a couple of nanoseconds of CPU time is unlikely to mean anything; and (c.) maintainability is generally more important than execution speed.

Please consider this an intellectual curiosity question.

Thanks,

Posted 28-Jul-15 2:44am

zCharles

Updated 28-Jul-15 3:16am

Richard MacCutchan

v2

Add a Solution

Comments

Richard MacCutchan 28-Jul-15 9:18am

a) Very true.
b) ibid.
c) It depends.

Andreas Gieriet 28-Jul-15 9:27am

As an intellectual exercise, how about looking into the code and
1) compare the implementation
2) count the produced instructions?
;-)
Cheers
Andi

Philippe Mori 28-Jul-15 21:39pm

In pratice, it will rarely have any significant impact in real life application.

2 solutions

Solution 2

There are various ways to write such loops, e.g.

C++

std::vector<int> v = ...;
for (size_t i = 0; i < v.size(); ++i)
// size() does some pointer arithmetic
{
   ...v[i]...
   // v[i] does some pointer arithmetic and de-references the pointer
}

And with iterators:

C++

std::vector<int> v = ...;
for(auto it = v.begin(); it != v.end(); ++it)
// begin: pointer, end: pointer, ++it: pointer arithmetic and de-references pointer
{
    ...*it...
    // *it de-references a pointer
}

Note: writing it++ leads in general to worse results since some temp value must be stored first.

Assumed "instructions"

first case

second case

      Load reg_i,0
      Load reg_v,address_of_v
      Load reg_begin,[v,begin]
Loop: Load reg_size,[v,end]
      Sub  reg_size,reg_begin
      Cmp  reg_size,reg_i
      Branch_if_less_or_equal Endloop
      ...
      Load reg_data,[reg_begin,reg_i]
      ...
      ; sizeof(int) == 4
      Add  reg_i,4
      Branch Loop
Endloop:
      ...

      Load reg_v,address_of_v
      Load reg_it,[v,begin]
Loop: Cmp  reg_it,[v,end]
      Branch_if_equal Endloop
      ...
      Load reg_data,[reg_it]
      ...
      ; sizeof(int) == 4
      Add  reg_it,4
      Branch Loop
Endloop:
      ...

I tried to do a fair comparison. With the assumed "instruction set", the iterator based approach has two instruction less in the loop. Mainly the size calculation counts here.

So much for the intellectual challenge ;-)
Cheers
Andi

Posted 28-Jul-15 4:33am

Andreas Gieriet

Updated 28-Jul-15 4:37am

v4

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Accepted Answer · 2015-07-28T03:25:00

Solution 1

Quote:
or would an optimizing compiler probably be clever enough to generate roughly the same code in either case

I bet on that.
However, you could inspect the produced assembly codes to make a comparison.

Posted 28-Jul-15 3:25am

CPallini