views:

387

answers:

10

I'm doing a bit of coding, where I have to write this sort of code:

if( array[i]==false )
    array[i]=true;

I wonder if it should be re-written as

array[i]=true;

This raises the question: are comparisions faster than assignments?

What about differences from language to language? (contrast between java & cpp, eg.)

NOTE: I've heard that "premature optimization is the root of all evil." I don't think that applies here :)

+12  A: 

Well, since you say you're sure that this matters you should just write a test program and measure to find the difference.

Comparison can be faster if this code is executed on multiple variables allocated at scattered addresses in memory. With comparison you will only read data from memory to the processor cache, and if you don't change the variable value when the cache decides to to flush the line it will see that the line was not changed and there's no need to write it back to the memory. This can speed up execution.

sharptooth
Agreed, on the other hand some architectures also have a penalty for branching... Only true answer can be found by measuring. Or looking at the generated assembly code, to see if it changes at all (my guess is no).
kotlinski
+1 for "measure"
Binary Worrier
Don't caches do this automatically? i.e. check if the data that's written is the same as the data that's there.
Jules
@julesjacobs: Not sure if it checks for equality. It surely checks whether or not it has been updated, but I've never heard of it checking for the update to be an actual change. That's a good point to keep in mind.
sharptooth
+19  A: 

This isn't just premature optimization, this is micro-optimization, which is an irrelevant distraction.

Assuming your array is of boolean type then your comparison is unnecessary, which is the only relevant observation.

cletus
I agree..may be it will be good from readability point of view, but certainly not if the change is being done to 'impreove' the performance.
Naveen
+1: I couldn't agree more
Binary Worrier
A: 

I really wouldn't expect there to be any kind of noticeable performance difference for something as trivial as this so surely it comes down to what gives you clear, more readable code. I my opinion that would be always assigning true.

Mark
Neither would I expect a performance difference. Its a matter of knowing the better choice from performance POV.
Here Be Wolves
A: 

Might give this a try:

if(!array[i])
    array[i]=true;

But really the only way to know for sure is to profile, I'm sure pretty much any compiler would see the comparison to false as unnecessary and optimize it out.

Davy8
If your compiler is any good this will produce identical machine code.
Jules
A: 

It all depends on the data type. Assigning booleans is faster than first comparing them. But that may not be true for larger value-based datatypes.

Benoît
+9  A: 

Edit: I wrote a script in PHP. I just noticed that there was a glaring error in it meaning the best-case runtime was being calculated incorrectly (scary that nobody else noticed!)

Best case just beats outright assignment but worst case is a lot worse than plain assignment. Assignment is likely fastest in terms of real-world data.

Output:

  • assignment in 0.0119960308075 seconds
  • worst case comparison in 0.0188510417938 seconds
  • best case comparison in 0.0116770267487 seconds

Code:

<?php
$arr = array();

$mtime = explode(" ", microtime());
$starttime = $mtime[1] + $mtime[0];

reset_arr($arr);

for ($i=0;$i<10000;$i++)
    $arr[i] = true;


$mtime = explode(" ", microtime());
$firsttime = $mtime[1] + $mtime[0];
$totaltime = ($firsttime - $starttime);
echo "assignment in ".$totaltime." seconds<br />"; 

reset_arr($arr);

for ($i=0;$i<10000;$i++)
    if ($arr[i])
     $arr[i] = true;

$mtime = explode(" ", microtime());
$secondtime = $mtime[1] + $mtime[0];
$totaltime = ($secondtime - $firsttime);
echo "worst case comparison in ".$totaltime." seconds<br />"; 

reset_arr($arr);

for ($i=0;$i<10000;$i++)
    if (!$arr[i])
     $arr[i] = false;

$mtime = explode(" ", microtime());
$thirdtime = $mtime[1] + $mtime[0];
$totaltime = ($thirdtime - $secondtime);
echo "best case comparison in ".$totaltime." seconds<br />"; 

function reset_arr($arr) {
    for ($i=0;$i<10000;$i++)
     $arr[$i] = false;
}
Oli
Thats interesting: assignment is actually faster!
Here Be Wolves
Ad by a significant margin, too: 14 ms versus 22 to 39 ms. That's about a factor of 2!
MSalters
A: 

As others have noted, this is micro-optimization.

(In politics or journalism, this is known as navel-gazing ;-)

Is the program large enough to have more than a couple layers of function/method/subroutine calls?

If so, it probably had some avoidable calls, and those can waste hundreds as much time as low-level inefficiencies.

On the assumption that you have removed those (which few people do), then by all means run it 10^9 times under a stopwatch, and see which is faster.

Mike Dunlavey
A: 

If you just want to flip the values, then do:

array[i] = !array[i];

Performance using this is actually worse though, as instead of only having to do a single check for a true false value then setting, it checks twice.

If you declare a 1000000 element array of true,false, true,false pattern comparision is slower. (var b = !b) essentially does a check twice instead of once

David Anderson
A: 

Depends on the language. However looping through arrays can be costly as well. If the array is in consecutive memory, the fastest is to write 1 bits (255s) across the entire array with memcpy assuming your language/compiler can do this.

Thus performing 0 reads-1 write total, no reading/writing the loop variable/array variable (2 reads/2 writes each loop) several hundred times.

VeNoM
or with `memset` rather than `memcpy` ...
Edmund
A: 

Why would you even write the first version? What's the benefit of checking to see if something is false before setting it true. If you always are going to set it true, then always set it true.

When you have a performance bottleneck that you've traced back to setting a single boolean value unnecessarily, come back and talk to us.

Andy Lester