branches (if) and iterations (for)

[s]

Hello all,

I was wondering on the following:

Regarding modern C++ compilers, is there a performance difference
between the following pseudo
code snips regarding the effects of:

* the taken/not taken conditions/branches and the CPU branch
prediction;
* and/or pipeline invalidations on missed branches;

And if there's no performance difference, which version would you
choose (regarding maintainability,etc.)?



## version 1 with `break`

for (int i=0; i < array_len; i++ )
{
if ( array == requested_item )
{
found = true;
break;
} // if

} // for

if found ....

## version 2 with `continue`

for (int i=0; i < array_len; i++ )
{
if ( array != requested_item )
{
continue;
} // if

found = true;
break;
} // for

if found ....

 

[Jonathan Lee]

for (int i=0; i < array_len; i++ )
{
  if ( array == requested_item )
  {
     found = true;
     break;
  } // if

} // for

Well, presumably you don't want i to go out of scope
so I'd end up writing

int i = 0;
while (i < array_len && array != requested_item) {
// if (!found) ...
++i;
}
if (i < array_len) { /* i.e., found */ } else { ... }

This is easier to read for me. Performance wise I doubt
you'd find any significant difference between the
versions.

--Jonathan

 

[Jeff Flinn]

for (int i=0; i < array_len; i++ )
{
if ( array == requested_item )
{
found = true;
break;
} // if

} // for

Well, presumably you don't want i to go out of scope
so I'd end up writing

int i = 0;
while (i < array_len && array != requested_item) {
// if (!found) ...
++i;
}
if (i < array_len) { /* i.e., found */ } else { ... }

This is easier to read for me. Performance wise I doubt
you'd find any significant difference between the
versions.

or since the op didn't define the type of array, and since this is 2009
and the op should be using a std container:

Array::iterator itr =
std::find(array.begin(), array.end(), requested_item);

if( itr != array.end())
{
...
}

and if it's not a std container

requested_item_type* itr =
std::find(array, array + array_len, requested_item);

if( itr != (array + array_len))
{
...
}

Jeff

 

[Jonathan Lee]

or since the op didn't define the type of array, and since this is 2009
and the op should be using a std container:

I think he's asking about the form of the loop, as opposed
to how to find things in an array.

--Jonathan

 

[Pavel]

Hello all,

I was wondering on the following:

Regarding modern C++ compilers, is there a performance difference
between the following pseudo
code snips regarding the effects of:

* the taken/not taken conditions/branches and the CPU branch
prediction;
* and/or pipeline invalidations on missed branches;

And if there's no performance difference, which version would you
choose (regarding maintainability,etc.)?



## version 1 with `break`

for (int i=0; i< array_len; i++ )
{
if ( array == requested_item )
{
found = true;
break;
} // if

} // for

if found ....

## version 2 with `continue`

for (int i=0; i< array_len; i++ )
{
if ( array != requested_item )
{
continue;
} // if

found = true;
break;
} // for

if found ....

The modern compilers sometimes provide implementation-specific means for
a programmer to let compiler know what branch is likely to happen in the
program (see __builtin_expect in gcc or

http://kerneltrap.org/node/4705

for some discussion).

The "old-school" thinking was that you wanted to put the break on a
condition that happens rarely in the loop header (the compiler would
commonly generate a forward jump for that) and the one you check within
a loop will be assumed to happen more often but I am not sure if it is
still a common assumption by the compiler writers.

On a side note, if you use loop unrolling optimization (such as
-funroll-loops for gcc), you may end up with a completely unexpected
generated code (gcc especially loves unrolling the form of "for" loop
you used in your example).

As every modern compiler is even more different than way back, your best
bet is probably just reading the assembly listing of the code generated
by your compiler of choice with the particular set of options you are
going to use in your release configuration.

-Pavel

 

[s]

Hi,

Thanks for the replies.

I stumbled upon some papers on C++ optimzations:

http://www.agner.org/optimize/
http://www.linux-kongress.org/2009/slides/compiler_survey_felix_von_leitner.pdf


Bye,


.... snip ...

 

[Jerry Coffin]

Hello all,

I was wondering on the following:

Regarding modern C++ compilers, is there a performance difference
between the following pseudo
code snips regarding the effects of:

* the taken/not taken conditions/branches and the CPU branch
prediction;
* and/or pipeline invalidations on missed branches;

And if there's no performance difference, which version would you
choose (regarding maintainability,etc.)?

Neither. I prefer to include the real exit condition from the loop in
the condition for the loop itself, so I'd probably do something like:

bool found = false;

for (int i=0; i<array_len && !found; i++)
found = (array == requested_item);

if (found)
// ...

While it's possible that you might be able to measure a speed
difference between this and one of the others, I wouldn't bet a lot
on it. One compiler might favor one, and another compiler another.