446,389 Members | 1,795 Online
Need help? Post your question and get tips & solutions from a community of 446,389 IT Pros & Developers. It's quick & easy.

# From bool to int: 1 or 0

 P: n/a 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 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 Jun 16 '06 #1
16 Replies

 P: n/a 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 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 Jun 16 '06 #2

 P: n/a 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 Jun 16 '06 #3

 P: n/a 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. Jun 16 '06 #4

 P: n/a 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 Jun 16 '06 #5

 P: n/a 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( true_or_false ); } #define IncrementIfTrue(amount,true_or_false)\ { if ( true_or_false ) ++amount; } To be used as follows: #include 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 Jun 16 '06 #6

 P: n/a #define IncrementIfTrue(amount,true_or_false)\ { amount += static_cast( 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 Jun 16 '06 #7

 P: n/a Frederick Gotham wrote: #define IncrementIfTrue(amount,true_or_false)\ { amount += static_cast( 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 Jun 16 '06 #8

 P: n/a 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( true_or_false ); } #define IncrementIfTrue(amount,true_or_false)\ { if ( true_or_false ) ++amount; } To be used as follows: #include 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 Jun 16 '06 #9

 P: n/a 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( 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. Jun 16 '06 #10

 P: n/a 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( 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 Jun 16 '06 #11

 P: n/a 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 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 :) Jun 16 '06 #12

 P: n/a Noah Roberts 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( 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 Jun 16 '06 #13

 P: n/a 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 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 Jun 16 '06 #14

 P: n/a 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++. Jun 16 '06 #15

 P: n/a Frederick Gotham wrote: The main point of my post was to discuss which of the following twoapproaches 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 Jun 16 '06 #16

 P: n/a "Frederick Gotham" 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 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 #include #include 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; } Jun 17 '06 #17

### This discussion thread is closed

Replies have been disabled for this discussion.