std vector iterator optimization question

[zl2k]

hi, there,

---------code 1-------------
for (vector<int>::interator it = somevector.begin(); it !=
somevector.end(); it++){...}

---------code 2-------------
vector<int>::iterator stop = somevector.end();
for (vector<int>::interator it = somevector.begin(); it != stop; it++)
{...}

Question:
If the somevector's length does not change, is code2 a better
implementation than code1 (since it saves the end() call for each
loop)?
For const_iterator, does stl already do the optimization so that code1
and code2 won't have much difference?

Thanks a lot.

zl2k

 

[Ian Collins]

hi, there,

---------code 1-------------
for (vector<int>::interator it = somevector.begin(); it !=
somevector.end(); it++){...}

---------code 2-------------
vector<int>::iterator stop = somevector.end();
for (vector<int>::interator it = somevector.begin(); it != stop; it++)
{...}

Question:
If the somevector's length does not change, is code2 a better
implementation than code1 (since it saves the end() call for each
loop)?
For const_iterator, does stl already do the optimization so that code1
and code2 won't have much difference?

What did your measurements show?

Beware the evils of premature optimisation (and trying to out-guess the
compiler!).

 

[T. Schroeder]

a good code style is

a typdef on your containertype for quick container changing

typedef std::vector<int> int_vector;

and no "using namespace std;"

ISO 14882:2003 17.4.4.1.1 `A C++ header may include other
C++ headers.' . If you include any C++ header in your
program and then do using namespace std; in some scope,
you might be bringing every C++ standard library
identifier into that scope.
There is no way of portably knowing which ones.

for (int_vector::interator
itb(somevector.begin())
, ite(somevector.end())
; itb != ite
; ++it)
{ ... }

and last but not least, pre increment on iterators

and your question, no there are no optimizations in your code, or big
differences...

Am 01.09.2010 06:27, schrieb zl2k:

hi, there,

---------code 1-------------
for (vector<int>::interator it = somevector.begin(); it !=
somevector.end(); it++){...}

---------code 2-------------
vector<int>::iterator stop = somevector.end();
for (vector<int>::interator it = somevector.begin(); it != stop; it++)
{...}

Question:
If the somevector's length does not change, is code2 a better
implementation than code1 (since it saves the end() call for each
loop)?
For const_iterator, does stl already do the optimization so that code1
and code2 won't have much difference?

Thanks a lot.

zl2k

--

Mit freundlichen Grüßen,
Yours sincerely,

Torsten Schröder
Systemadministrator, Softwareentwickler
Networking Officer, Development Officer

Email: (e-mail address removed)
Web: www.ipe-chemnitz.de

Sitz der Gesellschaft: 09120 Chemnitz, Annaberger Strasse 105
Handelsregister: HRB 11035 Amtsgericht Chemnitz
Geschäftsführer: Dr.-Ing. Ulrich Scharschmidt

 

[tni]

hi, there,

---------code 1-------------
for (vector<int>::interator it = somevector.begin(); it !=
somevector.end(); it++){...}

---------code 2-------------
vector<int>::iterator stop = somevector.end();
for (vector<int>::interator it = somevector.begin(); it != stop; it++)
{...}

Question:
If the somevector's length does not change, is code2 a better
implementation than code1 (since it saves the end() call for each
loop)?

Depends on your definition of better. Version 2 will frequently be
slightly faster (and result in smaller code).

Pre / post-increment shouldn't make a difference for STL iterators, but
for some complex iterators (where the optimizer doesn't do its job),
pre-increment can be faster.

For const_iterator, does stl already do the optimization so that code1
and code2 won't have much difference?

Const generally doesn't buy the compiler much in terms of optimization
capabilities. In almost all the cases where the compiler is allowed to
use that const-ness for optimization, the compiler has enough
information not to need the const declaration itself.

(You should keep in mind though, that there are COW-based containers,
where accessing a non-const method can trigger a copy.)

 

[Ian Collins]

a good code style is

a typdef on your containertype for quick container changing

typedef std::vector<int> int_vector;

and no "using namespace std;"

>
for (int_vector::interator
itb(somevector.begin())
, ite(somevector.end())
; itb != ite
; ++it)
{ ... }

What ghastly style and that's not just the top-posting!

 

[Thorsten Mueller]

Subscripting should be the fastest option, if it's all about
performance:

for(unsigned int x = 0; x < somevector.size(); ++x) {
do something with somevector[x]
}

Also using for_each() would be an alternative, if you can put the loop
functionality in a functor

 

[Jonathan Lee]

a good code style is

a typdef on your containertype for quick container changing

typedef std::vector<int> int_vector;

In this specific case, I'd (personally) rather typedef the
iterator itself:

void fn(std::vector<int>& v) {
typedef std::vector<int>::iterator iterator;
for (iterator it = v.begin(), jt = v.end(); it != jt; ++it)
...
}

--Jonathan

 

[Fred Zwarts]

Subscripting should be the fastest option, if it's all about
performance:

for(unsigned int x = 0; x < somevector.size(); ++x) {
do something with somevector[x]
}

Why would this be faster in general than using iterators?
When using iterators somevector.end () and iterator operators ++ and != and * are used repeatedly.
When using subscripting, somevector.size () and somevector[] are used repeatedly.
I fail to see why you say that subscripting is faster,
without further knowledge of the implementation of these functions and operators.

 

[AnonMail2005]

On 09/ 1/10 06:12 PM, T. Schroeder wrote:> a good code style is




What ghastly style and that's not just the top-posting!

Agreed!

Other than the formatting, I use the above idiom for similar loops.

The key points being:
1) call v.end() just once instead of on each iteration
2) pre-increment the iterator

 

[Juha Nieminen]

Subscripting should be the fastest option, if it's all about
performance:

for(unsigned int x = 0; x < somevector.size(); ++x) {
do something with somevector[x]
}

Note that in many std::vector implementations the size() function will
return "end() - begin()" (rather than some member variable of std::vector).
It's then up to the compiler to be smart enough to optimize that
subtraction away from the loop, if it can. Depending on the loop body
the compiler might be unable to (because it can't tell if the size of
the vector is being modified inside the loop).

If we are micro-optimizing, then we usually want to avoid calling
std::vector::size() in the loop condition.

Also, indexing an array will never be faster than iterating it with
a pointer (or, in this case, an iterator). If anything, it can only be
slower (because there's one extraneous variable being used). Hence, again,
if we are micro-optimizing, then using std::vector iterators is the
safest choice.

 

[Juha Nieminen]

for (vector<int>::interator it = somevector.begin(); it !=
somevector.end(); it++){...}

You should learn to use the prefix increment operator by default,
and use the postfix one only if you really need it.

With basic integral types it makes no difference in terms of efficiency,
but with iterators it can make a significant difference. That's because
the postfix increment operator has to return a copy of the original
iterator, and then it's up to the compiler to optimize that copy away,
if it can (often it can't). There's no such problem with the prefix
increment operator.

 

[Bo Persson]

Depends on your definition of better. Version 2 will frequently be
slightly faster (and result in smaller code).

My bet is very slightly, and very infrequently.

The vector iterator is a pointer (possibly wrapped in a class). If you
don't do anything fancy inside {...} the compiler can easily see that
end() is a loop invariant and only compute it once.

If you do a lot of work in {...}, it doesn't matter anyway.


Bo Persson

 

[Kai-Uwe Bux]

hi, there,

---------code 1-------------
for (vector<int>::interator it = somevector.begin(); it !=
somevector.end(); it++){...}

---------code 2-------------
vector<int>::iterator stop = somevector.end();
for (vector<int>::interator it = somevector.begin(); it != stop; it++)
{...}

Question:
If the somevector's length does not change, is code2 a better
implementation than code1 (since it saves the end() call for each
loop)?
For const_iterator, does stl already do the optimization so that code1
and code2 won't have much difference?

Thanks a lot.

Here is what g++ (version 4.4.3, optimization level -O2) does.

input:
======
#include <vector>

typedef std::vector< int > int_vector;

int sum_a1 ( int_vector const & arg ) {
int result = 0;
for ( int_vector::const_iterator iter = arg.begin();
iter != arg.end(); ++iter ) {
result += *iter;
}
return ( result );
}

int sum_a2 ( int_vector const & arg ) {
int result = 0;
for ( int_vector::const_iterator iter = arg.begin();
iter != arg.end(); iter++ ) {
result += *iter;
}
return ( result );
}

int sum_a3 ( int_vector const & arg ) {
int result = 0;
int_vector::const_iterator past_end = arg.end();
for ( int_vector::const_iterator iter = arg.begin();
iter != past_end; ++iter ) {
result += *iter;
}
return ( result );
}

int sum_b1 ( int_vector & arg ) {
int result = 0;
for ( int_vector::iterator iter = arg.begin();
iter != arg.end(); ++iter ) {
result += *iter;
}
return ( result );
}

int sum_b2 ( int_vector & arg ) {
int result = 0;
for ( int_vector::iterator iter = arg.begin();
iter != arg.end(); iter++ ) {
result += *iter;
}
return ( result );
}

int sum_b3 ( int_vector & arg ) {
int result = 0;
int_vector::iterator past_end = arg.end();
for ( int_vector::iterator iter = arg.begin();
iter != past_end; ++iter ) {
result += *iter;
}
return ( result );
}

output of g++ -O2 -S:
=====================

.file "optimization_001.cc"
.text
.p2align 4,,15
..globl _Z6sum_a1RKSt6vectorIiSaIiEE
.type _Z6sum_a1RKSt6vectorIiSaIiEE, @function
_Z6sum_a1RKSt6vectorIiSaIiEE:
..LFB435:
.cfi_startproc
.cfi_personality 0x0,__gxx_personality_v0
pushl %ebp
.cfi_def_cfa_offset 8
movl %esp, %ebp
.cfi_offset 5, -8
.cfi_def_cfa_register 5
movl 8(%ebp), %eax
movl (%eax), %edx
movl 4(%eax), %ecx
xorl %eax, %eax
cmpl %ecx, %edx
je .L3
.p2align 4,,7
.p2align 3
..L6:
addl (%edx), %eax
addl $4, %edx
cmpl %edx, %ecx
jne .L6
..L3:
popl %ebp
ret
.cfi_endproc
..LFE435:
.size _Z6sum_a1RKSt6vectorIiSaIiEE, .-_Z6sum_a1RKSt6vectorIiSaIiEE
.p2align 4,,15
..globl _Z6sum_a2RKSt6vectorIiSaIiEE
.type _Z6sum_a2RKSt6vectorIiSaIiEE, @function
_Z6sum_a2RKSt6vectorIiSaIiEE:
..LFB436:
.cfi_startproc
.cfi_personality 0x0,__gxx_personality_v0
pushl %ebp
.cfi_def_cfa_offset 8
movl %esp, %ebp
.cfi_offset 5, -8
.cfi_def_cfa_register 5
movl 8(%ebp), %eax
movl (%eax), %edx
movl 4(%eax), %ecx
xorl %eax, %eax
cmpl %ecx, %edx
je .L11
.p2align 4,,7
.p2align 3
..L14:
addl (%edx), %eax
addl $4, %edx
cmpl %edx, %ecx
jne .L14
..L11:
popl %ebp
ret
.cfi_endproc
..LFE436:
.size _Z6sum_a2RKSt6vectorIiSaIiEE, .-_Z6sum_a2RKSt6vectorIiSaIiEE
.p2align 4,,15
..globl _Z6sum_a3RKSt6vectorIiSaIiEE
.type _Z6sum_a3RKSt6vectorIiSaIiEE, @function
_Z6sum_a3RKSt6vectorIiSaIiEE:
..LFB437:
.cfi_startproc
.cfi_personality 0x0,__gxx_personality_v0
pushl %ebp
.cfi_def_cfa_offset 8
movl %esp, %ebp
.cfi_offset 5, -8
.cfi_def_cfa_register 5
movl 8(%ebp), %eax
movl 4(%eax), %ecx
movl (%eax), %edx
xorl %eax, %eax
cmpl %edx, %ecx
je .L18
.p2align 4,,7
.p2align 3
..L21:
addl (%edx), %eax
addl $4, %edx
cmpl %edx, %ecx
jne .L21
..L18:
popl %ebp
ret
.cfi_endproc
..LFE437:
.size _Z6sum_a3RKSt6vectorIiSaIiEE, .-_Z6sum_a3RKSt6vectorIiSaIiEE
.p2align 4,,15
..globl _Z6sum_b1RSt6vectorIiSaIiEE
.type _Z6sum_b1RSt6vectorIiSaIiEE, @function
_Z6sum_b1RSt6vectorIiSaIiEE:
..LFB438:
.cfi_startproc
.cfi_personality 0x0,__gxx_personality_v0
pushl %ebp
.cfi_def_cfa_offset 8
movl %esp, %ebp
.cfi_offset 5, -8
.cfi_def_cfa_register 5
movl 8(%ebp), %eax
movl (%eax), %edx
movl 4(%eax), %ecx
xorl %eax, %eax
cmpl %ecx, %edx
je .L25
.p2align 4,,7
.p2align 3
..L28:
addl (%edx), %eax
addl $4, %edx
cmpl %edx, %ecx
jne .L28
..L25:
popl %ebp
ret
.cfi_endproc
..LFE438:
.size _Z6sum_b1RSt6vectorIiSaIiEE, .-_Z6sum_b1RSt6vectorIiSaIiEE
.p2align 4,,15
..globl _Z6sum_b2RSt6vectorIiSaIiEE
.type _Z6sum_b2RSt6vectorIiSaIiEE, @function
_Z6sum_b2RSt6vectorIiSaIiEE:
..LFB439:
.cfi_startproc
.cfi_personality 0x0,__gxx_personality_v0
pushl %ebp
.cfi_def_cfa_offset 8
movl %esp, %ebp
.cfi_offset 5, -8
.cfi_def_cfa_register 5
movl 8(%ebp), %eax
movl (%eax), %edx
movl 4(%eax), %ecx
xorl %eax, %eax
cmpl %ecx, %edx
je .L32
.p2align 4,,7
.p2align 3
..L35:
addl (%edx), %eax
addl $4, %edx
cmpl %edx, %ecx
jne .L35
..L32:
popl %ebp
ret
.cfi_endproc
..LFE439:
.size _Z6sum_b2RSt6vectorIiSaIiEE, .-_Z6sum_b2RSt6vectorIiSaIiEE
.p2align 4,,15
..globl _Z6sum_b3RSt6vectorIiSaIiEE
.type _Z6sum_b3RSt6vectorIiSaIiEE, @function
_Z6sum_b3RSt6vectorIiSaIiEE:
..LFB440:
.cfi_startproc
.cfi_personality 0x0,__gxx_personality_v0
pushl %ebp
.cfi_def_cfa_offset 8
movl %esp, %ebp
.cfi_offset 5, -8
.cfi_def_cfa_register 5
movl 8(%ebp), %eax
movl 4(%eax), %ecx
movl (%eax), %edx
xorl %eax, %eax
cmpl %edx, %ecx
je .L39
.p2align 4,,7
.p2align 3
..L42:
addl (%edx), %eax
addl $4, %edx
cmpl %edx, %ecx
jne .L42
..L39:
popl %ebp
ret
.cfi_endproc
..LFE440:
.size _Z6sum_b3RSt6vectorIiSaIiEE, .-_Z6sum_b3RSt6vectorIiSaIiEE
.ident "GCC: (Gentoo 4.4.3-r2 p1.2) 4.4.3"
.section .note.GNU-stack,"",@progbits

The versions sum_x1 and sum_x2 (x=a,b) are compiled into identical code. The
difference of whether to manually store the termination value of the loop
after computing it once or leaving the computation inside the loop is _gone_
after the compiler is done. I expect other optimizing compilers to reproduce
this observation: the technique (moving code outside a loop when possible)
used in this optimization have been known for a long time. So, let the
compiler worry about micro-optimizations such as these and just choose the
version that fits best the coding style used in the project unless profiling
shows that there is a real bottleneck.


Best

Kai-Uwe Bux

 

[Jeff Flinn]

a good code style is

a typdef on your containertype for quick container changing

typedef std::vector<int> int_vector;

and no "using namespace std;"

ISO 14882:2003 17.4.4.1.1 `A C++ header may include other
C++ headers.' . If you include any C++ header in your
program and then do using namespace std; in some scope,
you might be bringing every C++ standard library
identifier into that scope.
There is no way of portably knowing which ones.

for (int_vector::interator
itb(somevector.begin())
, ite(somevector.end())
; itb != ite
; ++it)
{ ... }

and last but not least, pre increment on iterators

Or

std::appropriate_algorithm( v.begin(), v.end(), ... );

or using boost range algorithms

boost::appropriate_algorithm( v, ...);

now all those worries are a thing of the past.

Jeff