CODEWITHSUNDEEP
performancecomparisonbitwise-xor
Ismael Miguel
Ismael Miguel

Reputation: 4241

Why is bitwise-xor (^) is faster than not-equal (!=) comparisson in Firefox?

I was reading an article from other website (Computer Science - Can a Minimum Possible Efficiency be proven?) about assuming a minimum Big-O time for the worst cases.

One of the answers goes to a length explaining about the required time to compare binary values (or similar).

And I though to myself: why not bitwise operations?

And I made this mock-up code in Javascript:

console.time('^');
for(var i=0;i<1e5;i++)13^15;
console.timeEnd('^');

console.time('!=');
for(var i=0;i<1e5;i++)13!=15;
console.timeEnd('!=');

And I got really surprised!

The loop using ^ (bitwise-xor) can be almost 3ms faster!

How is this possible?

Why is bitwise-xor (^) is faster than not-equal (!=) comparisson?

Other possibly relevant information:

I've tested on Firefox 34.0.5 running on Windows 7 Home Premium x64.

I've also tried this code on Opera 12.17(x64) and Chrome 39.0.2171.95 and the behaviour is almost similar, being the code using ^ faster 80% of the tests.

Another surprise:

In php, running this:

$now=microtime(true);
for($i=0,$x=0;$i<1e6;$i++)$x+=13^15;
echo microtime(true)-$now,PHP_EOL;

$now=microtime(true);
for($i=0,$x=0;$i<1e6;$i++)$x+=13!=15;
echo microtime(true)-$now,PHP_EOL;

Shows exactly the same effect: ^ is faster than !=.
Using $x+=!13^15; instead of $x+=13^15; is faster 70% of the time.

I've tested on http://writecodeonline.com/php/ which is running PHP 5.3 on linux x64.

This code has a suggestion from the user @AlexK., on the following comment:

13^15 is a constant noop, perhaps its simply optimised away (try something effective x+=13^15;)

Upvotes: 6

Views: 3809

Answers (1)

Rick James
Rick James

Reputation: 142298

You are barking up the wrong trees.

On, say, a 2GHz CPU, ^ or != can be performed in a nanosecond, or thereabouts. To perform 1e6 of them would take 1ms, not 460ms. This tells me two things:

  1. The for takes a significant amount of the time, and
  2. JavaScript is interpreted not compiled.

Note that interpreters don't necessarily spend time optimizing. A really good optimizer would turn for($i=0,$x=0;$i<1e6;$i++)$x+=13^15; into $x = 2000000. It obviously did not do that. OK, it is hard to tell if it turned $x+=13^15 into $x+=2.

Let's look at another thing. At the machine level, or even at the interperter level $x+=13!=15 is more complex than $x+=13^15. Both involve $x+=, but 13^15 is a single operation, whereas 13!=15 (in this context!) is two operations -- First compare 13 and 15 for != to get true, then convert true to 1. There are many ways at the hardware level to do it -- most involve a jump, which is costly. There are other techniques that involve multiple boolean/shift/etc instructions, just to avoid the jump.

Perhaps 13!=15 is slower. But you don't know by how much because of the significant overhead of the for loop.

Anyway, does it matter? Is there some situation where those two operations are interchangeable? You were not comparing to (13^15)!=0 which might be equivalent.

Upvotes: 2

Related Questions