From bool to int: 1 or 0

[Frederick Gotham]

If I wanted a super-efficient algorithm for counting the amount of 6's in
an array, (given the address of the first element and the amount of
elements), I might start off with:

#include <cstddef>

unsigned AmountSixes( const int *p, std::size_t const len )
{
unsigned amount = 0;

const T* const p_over = array + len;

do
{
if( *p++ == 6 ) ++amount;
}
while ( p != p_over );

return amount;
}
However, by my own coding style, I'd probably change the loop to:

do
{
amount += (*p++ == 6);
} while ( p != p_over );
This would rely on the bool to int conversion which would yield 1 or 0.

Any thoughts on which would be likely to be more efficient on the
majority of architectures if I was writing fully portable code to be used
on everything from a wristwatch to a personal computer?


--

Frederick Gotham

[Victor Bazarov]

Frederick Gotham wrote:

If I wanted a super-efficient algorithm for counting the amount of
6's in an array, (given the address of the first element and the
amount of elements), I might start off with:
Or you might use 'std::count'...

#include <cstddef>

unsigned AmountSixes( const int *p, std::size_t const len )
{
unsigned amount = 0;

const T* const p_over = array + len;

do
{
if( *p++ == 6 ) ++amount;
}
while ( p != p_over );

return amount;
}
However, by my own coding style, I'd probably change the loop to:

do
{
amount += (*p++ == 6);
} while ( p != p_over );
Why bother when there is 'std::count'? :-)
This would rely on the bool to int conversion which would yield 1 or
0.
It does.
Any thoughts on which would be likely to be more efficient on the
majority of architectures if I was writing fully portable code to be
used on everything from a wristwatch to a personal computer?

return std::count(p, p + len, 6)

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Frederick Gotham]

Victor Bazarov posted:

return std::count(p, p + len, 6)

Thanks for the input, Victor. Checking for the quantity of instances of a
particular elemental value was just an example.

The main point of my post was to discuss which of the following two
approaches would be preferable in everyday programming:

if( *p++ == 6 ) ++amount;

or:

amount += (*p++ == 6);

--

Frederick Gotham

[Noah Roberts]

Frederick Gotham wrote:

Victor Bazarov posted:

return std::count(p, p + len, 6)

Thanks for the input, Victor. Checking for the quantity of instances of a
particular elemental value was just an example.

The main point of my post was to discuss which of the following two
approaches would be preferable in everyday programming:

if( *p++ == 6 ) ++amount;

or:

amount += (*p++ == 6);

In an effort to say what you mean I prefer the former; it says exactly
what is intended. The later is more cryptic and full of trickery. The
fact that you have to ask only proves the point.

[mlimber]

Frederick Gotham wrote:

The main point of my post was to discuss which of the following two
approaches would be preferable in everyday programming:

if( *p++ == 6 ) ++amount;

or:

amount += (*p++ == 6);

I would say the former since it is more readable and likely of
negligible performance difference. The meaning of the first is obvious
even to a junior programmer, while one must decode the second, and
programmers have enough to worry about without trying to determine if
an unnecessarily clever statement like that is causing problems.

Cheers! --M

[Frederick Gotham]

In response to both Noah and mlimber,

I am not at all bothered with whether one form is easier to understand
than the other -- I am solely concerned with performance.

If I wanted to simplify it, I could write a macro or a template function.

I suppose I could rephrase my question as follows:

Which of the following two macros would be preferable (performance-wise)
for use in portable code?:
#define IncrementIfTrue(amount,true_or_false)\
{ amount += static_cast<bool>( true_or_false ); }
#define IncrementIfTrue(amount,true_or_false)\
{ if ( true_or_false ) ++amount; }
To be used as follows:

#include <cstddef>

unsigned AmountSixes( const int *p, std::size_t const len )
{
unsigned amount = 0;

const T* const p_over = array + len;

do
{
IncrementIfTrue( amount, *p++ == 6 );
}
while ( p != p_over );

return amount;
}
--
Frederick Gotham

[Frederick Gotham]

#define IncrementIfTrue(amount,true_or_false)\
{ amount += static_cast<bool>( true_or_false ); }

I must admit that I'm slightly unsure as to whether this will be as
efficient as I think it will. I wonder if the compiler would treat it
something like:

#define IncrementIfTrue(amount,true_or_false)\
{ amount += ( true_or_false ? 1 : 0 ); }
This might even be more costly than a simple "if" statment... Would it?

--

Frederick Gotham

[Victor Bazarov]

Frederick Gotham wrote:

#define IncrementIfTrue(amount,true_or_false)\
{ amount += static_cast<bool>( true_or_false ); }

I must admit that I'm slightly unsure as to whether this will be as
efficient as I think it will. I wonder if the compiler would treat it
something like:

#define IncrementIfTrue(amount,true_or_false)\
{ amount += ( true_or_false ? 1 : 0 ); }
This might even be more costly than a simple "if" statment... Would
it?

Might. Or might not. If you are "solely concerned with performance",
measure it, don't guess. However, I bet that when the entire program
is measured, the difference between the two methods is going to be
negligible.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[mlimber]

Frederick Gotham wrote:

In response to both Noah and mlimber,

I am not at all bothered with whether one form is easier to understand
than the other -- I am solely concerned with performance.
Different compilers (and optimizers!) will produce different code, and
some CPU architectures and memory/cache configurations may do some
things more efficiently than others. So there's really no way to
determine which is faster in general. You could use a profiler on your
particular system to see which is faster on that system, but I strongly
suspect you're barking up the old "premature optimization" tree (see,
e.g., "Beware Premature Optimization" in
http://www.gotw.ca/publications/mill09.htm).

If I wanted to simplify it, I could write a macro or a template function.

I suppose I could rephrase my question as follows:

Which of the following two macros would be preferable (performance-wise)
for use in portable code?:
#define IncrementIfTrue(amount,true_or_false)\
{ amount += static_cast<bool>( true_or_false ); }
#define IncrementIfTrue(amount,true_or_false)\
{ if ( true_or_false ) ++amount; }
To be used as follows:

#include <cstddef>

unsigned AmountSixes( const int *p, std::size_t const len )
{
unsigned amount = 0;

const T* const p_over = array + len;

do
{
IncrementIfTrue( amount, *p++ == 6 );
}
while ( p != p_over );

return amount;
}

First of all, macros should be avoided when possible because of all
their "issues" (see
http://www.parashift.com/c++-faq-lit....html#faq-9.5).

Second, using a macro or inline function or your clever code here just
obfuscates your meaning again. Write code for humans, not the CPU (let
the compiler/optimizer worry about that!), until you have measured (not
intuited!) that hand optimizing would be of significant benefit.

Cheers! --M

[Noah Roberts]

Frederick Gotham wrote:

In response to both Noah and mlimber,

I am not at all bothered with whether one form is easier to understand
than the other -- I am solely concerned with performance.
http://www.flounder.com/optimization.htm
http://en.wikipedia.org/wiki/Optimiz...en_to_optimize

Since you are asking about the performance of these different methods I
must assume you have NOT gathered data yet.
Which of the following two macros would be preferable (performance-wise)
for use in portable code?:
#define IncrementIfTrue(amount,true_or_false)\
{ amount += static_cast<bool>( true_or_false ); }
#define IncrementIfTrue(amount,true_or_false)\
{ if ( true_or_false ) ++amount; }

Without data I can only guess. My guess is on the later. Reasons:

* In the former the addition is always performed.
* The former requires the loading and addition of two registers, the
later does not.
* The former requires a cast.
* The former requires an additional assignment.

Now, the compiler could eliminate all those differences. The compiler
will have an easier time figuring out how to optimize when the code is
easier to interpret. The compiler was written by a human, therefor
things a human finds easier to interpret are more likely programmed
into the compiler's logic.

Stop trying to second guess your compiler before you even start.
Chances are very high that you are not smarter than the people that
wrote it. By trying to outwhit the experts you are more likely than
not to hinder the compiler's ability to optimize for you.

[int2str]

Noah Roberts wrote:

Which of the following two macros would be preferable (performance-wise)
for use in portable code?:
#define IncrementIfTrue(amount,true_or_false)\
{ amount += static_cast<bool>( true_or_false ); }
#define IncrementIfTrue(amount,true_or_false)\
{ if ( true_or_false ) ++amount; }

Without data I can only guess. My guess is on the later. Reasons:

I made a quick test program and tried it with different optimization
settings etc.
"if( *p++ == 6 ) ++amount;" was pretty much consistantly FASTER than
"amount += (*p++ == 6);". And It's significantly more readable as well.

This backs up Noah's intuition.

However, I agree with everybody here that the original poster needs to
measure HIS program first and then figure out which one is faster and
if improvements are necessary.

Though I'd add that profiling the whole program will very likely
conclude that this particular comparison isn't the biggest bottleneck
in the program anyways ;).

Cheers,
Andre

[Markus Schoder]

Frederick Gotham wrote:

If I wanted a super-efficient algorithm for counting the amount of 6's in
an array, (given the address of the first element and the amount of
elements), I might start off with:

#include <cstddef>

unsigned AmountSixes( const int *p, std::size_t const len )
{
unsigned amount = 0;

const T* const p_over = array + len;

do
{
if( *p++ == 6 ) ++amount;
}
while ( p != p_over );

return amount;
}
However, by my own coding style, I'd probably change the loop to:

do
{
amount += (*p++ == 6);
} while ( p != p_over );
This would rely on the bool to int conversion which would yield 1 or 0.

Any thoughts on which would be likely to be more efficient on the
majority of architectures if I was writing fully portable code to be used
on everything from a wristwatch to a personal computer?

Here is the result on an AMD64 PC with gcc 4.1.1

version 1:

..L2:
movl (%rdi), %eax
addq $4, %rdi
cmpl $6, %eax
sete %al
movzbl %al, %eax
addl %eax, %edx
cmpq %rdi, %rcx
jne .L2
movl %edx, %eax
ret

version 2:

..L2:
xorl %eax, %eax
cmpl $6, (%rdi)
sete %al
addq $4, %rdi
addl %eax, %edx
cmpq %rdi, %rcx
jne .L2
movl %edx, %eax
ret

Seems that version 2 saves one instruction. Now you just have to check all
the other compiler and platform combinations and you are set :)

[Marcus Kwok]

Noah Roberts <ro**********@gmail.com> wrote:

Frederick Gotham wrote:

Which of the following two macros would be preferable (performance-wise)
for use in portable code?:
#define IncrementIfTrue(amount,true_or_false)\
{ amount += static_cast<bool>( true_or_false ); }
#define IncrementIfTrue(amount,true_or_false)\
{ if ( true_or_false ) ++amount; }

Without data I can only guess. My guess is on the later. Reasons:

* In the former the addition is always performed.
* The former requires the loading and addition of two registers, the
later does not.
* The former requires a cast.
* The former requires an additional assignment.

Hypothetically speaking, an argument against the second version is that
the if test can cause the processor to stall if it doesn't have good
branch prediction capabilities, and it is possible that this could be
slower than performing all the extra instructions every time.

Of course I agree that the only real measure is to profile, and to code
for correctness and clarity first.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply

[mlimber]

Markus Schoder wrote:

Frederick Gotham wrote:

If I wanted a super-efficient algorithm for counting the amount of 6's in
an array, (given the address of the first element and the amount of
elements), I might start off with:

#include <cstddef>

unsigned AmountSixes( const int *p, std::size_t const len )
{
unsigned amount = 0;

const T* const p_over = array + len;

do
{
if( *p++ == 6 ) ++amount;
}
while ( p != p_over );

return amount;
}
However, by my own coding style, I'd probably change the loop to:

do
{
amount += (*p++ == 6);
} while ( p != p_over );
This would rely on the bool to int conversion which would yield 1 or 0.

Any thoughts on which would be likely to be more efficient on the
majority of architectures if I was writing fully portable code to be used
on everything from a wristwatch to a personal computer?

Here is the result on an AMD64 PC with gcc 4.1.1

version 1:

.L2:
movl (%rdi), %eax
addq $4, %rdi
cmpl $6, %eax
sete %al
movzbl %al, %eax
addl %eax, %edx
cmpq %rdi, %rcx
jne .L2
movl %edx, %eax
ret

version 2:

.L2:
xorl %eax, %eax
cmpl $6, (%rdi)
sete %al
addq $4, %rdi
addl %eax, %edx
cmpq %rdi, %rcx
jne .L2
movl %edx, %eax
ret

Seems that version 2 saves one instruction. Now you just have to check all
the other compiler and platform combinations and you are set :)

Don't forget to try all the optimization flags, too! (You had also
better set up regression tests for when new versions/service packs for
compilers are released.)

Cheers! --M

[Mark P]

Frederick Gotham wrote:

Victor Bazarov posted:

return std::count(p, p + len, 6)

Thanks for the input, Victor. Checking for the quantity of instances of a
particular elemental value was just an example.

The main point of my post was to discuss which of the following two
approaches would be preferable in everyday programming:

if( *p++ == 6 ) ++amount;

or:

amount += (*p++ == 6);

If performance is the sole concern, you might equally well worry about a
temporary produced by p++.

[Steve Pope]

Frederick Gotham <fg*******@SPAM.com> wrote:

The main point of my post was to discuss which of the following two
approaches would be preferable in everyday programming:

if( *p++ == 6 ) ++amount;

or:

amount += (*p++ == 6);

If you turn on all optimization and they're not the same,
then something is amiss.

In any case, if it's important you will have to measure
the run-time, rather than relying on a belief as to
which is faster.

Steve

[Jim Langston]

"Frederick Gotham" <fg*******@SPAM.com> wrote in message
news:Xn***************************@194.125.133.14. ..

If I wanted a super-efficient algorithm for counting the amount of 6's in
an array, (given the address of the first element and the amount of
elements), I might start off with:

#include <cstddef>

unsigned AmountSixes( const int *p, std::size_t const len )
{
unsigned amount = 0;

const T* const p_over = array + len;

do
{
if( *p++ == 6 ) ++amount;
}
while ( p != p_over );

return amount;
}
However, by my own coding style, I'd probably change the loop to:

do
{
amount += (*p++ == 6);
} while ( p != p_over );
This would rely on the bool to int conversion which would yield 1 or 0.

Any thoughts on which would be likely to be more efficient on the
majority of architectures if I was writing fully portable code to be used
on everything from a wristwatch to a personal computer?

Why don't you just test?

Output of following program for me is:
Start:62 End:93 Difference:31
Start:109 End:187 Difference:78

It made no difference to either if value was 0 or 6.

although with only 1 million iterations the values come out to 0. Meaning
this is trivial and you shouldn't even worry about it anyway. clock() on my
system returns values in milliseconds. Meaning that ten million iterations
takes 31 milliseconds, or .031 of a second. Divide that by 10 million each
assignment and test is taking 0.0000000031 of a second for the fastest,
0.0000000078 of a second for the slower. Is something that is going to take
you 0.0000000047 of a second more really enough to worry about optimizing?
Especially since your optimization makes it slower.

#include <iostream>
#include <string>
#include <time.h>

int main ( void )
{
time_t Start;
time_t End;

int value = 0;

int amount = 0;
Start = clock();

for ( int i = 1; i < 10000000; ++i )
{
if ( value == 6 )
++amount;
}

End = clock();

std::cout << "Start:" << Start << " End:" << End << " Difference:" <<
End - Start << std::endl;

amount = 0;
Start = clock();

for ( int i = 1; i < 10000000; ++i )
{
amount += ( value == 6 );
}

End = clock();

std::cout << "Start:" << Start << " End:" << End << " Difference:" <<
End - Start << std::endl;

std::string wait;
std::cin >> wait;
}