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

Question

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;)

Sphenogram

Increase the iteration count by 10x to exclude noise effects and give the difference in percent. An absolute value without reference to compare it to is meaningless. – Tunstall

@Tunstall Do you have any example where I can take some ideas of how to do it without flooding this post with printscreens? – Sphenogram

Just say "it's x% faster". I was forced to run the benchmark myself to find out. – Tunstall

@Tunstall Sorry my stupidity, but I'm having a 'math collapse'. Using your suggestion (changing 1e5 to 1e6) I got 457.9ms, 459.2ms and 458.07ms for the ^ test, while != took 465.91ms (+8.01ms), 469.21ms (+10.01ms) and 469.29ms (+11.22ms). How can I calculate the percentage of these? – Sphenogram

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

@AlexK. Using that logic, 13!=15 should be optimized the same way, right? – Sphenogram

@AlexK. Using your suggestion, the code with ^ is 2x slower, but the difference is greater! I've used this: console.time('^'); for(var i=0,x=0;i<1e6;i++)x+=13^15; console.timeEnd('^'); console.time('!='); for(var i=0,x=0;i<1e6;i++)x+=13!=15; console.timeEnd('!=');. – Sphenogram

There would need to be a type conversion in the 2nd. – Abatement

@AlexK. You are correct! I've removed the bias in Javascript, by replacing x+=13^15; with x+=!13^15; (notice the !). – Sphenogram

3ms is absolutely noise – Rhythmics

@Rhythmics Running it 1e6 times instead of 1e5 times will discard that possibility. Otherwise, I would completely agree with you. – Sphenogram

Answer 1

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.

Soapbark

Probably I really am looking at this from the wrong angle. The idea was to avoid != to speedup a sorting algorithm. But the speed difference is real. On the for, in the condition, try replacing i<1e5 with i^1e5 and i!=1e5 respectivelly. On Google Chrome, it ran for(var i=0;i^1e5;i++)13^15; in 82-88ms and for(var i=0;i!=1e5;i++)13!=15; in 98-99ms. I may provide printscreen if required. And the line for($i=0,$x=0;$i<1e6;$i++)$x+=13^15; is for PHP (but it can run on Javascript as well). But even on PHP, the trend is the same. (continue) – Sphenogram

Quoting your answer: "Anyway, does it matter? Is there some situation where those two operations are interchangeable?" --> Yes, there is. You can use it to check if 2 numbers are different. 1^1e5 should produce a truthy value identical to 1!=1e5. And 1e5^1e5 should produce the equivalent truthy result as 1e5!=1e5. They aren't interchangeable all the time, but for this particual case, they are. I guess it matters, right? – Sphenogram

The test case requires converting from boolean (true/false) to a number so that += can be performed. If, instead, you kept it as true/false, the code might be faster. – Soapbark

Time this: for(var i=0;i^1e6;i++)$x+=13^15+99^97; I've added only a plus and another xor. The question is: How much does the 460ms increase? If it goes to only 480 or 500, then that should demonstrate how much "overhead" you have in this timing mechanism. Beware of the overhead. – Soapbark

You confused me... You mixed PHP with Javascript. And in which one should I test it? How will that demonstrate the overhead? – Sphenogram

PHP and Javascript work similarly. I guess I am confused as to which one you are trying to time. Overhead: If the diff is between 480 and 460, that means that 20ms is the time for +99^97. (20ms/1e6 = 20ns each). And the overhead is 460ms. And simply for(var i=0;i^1e6;i++) may be around 430ms. It is hard to get a precise "20" with that much overhead. Notice how your readings varied from 8.01 to 11.22 -- about a 40% variation. – Soapbark

PHP and Javascript work totally different. PHP is converted to opcodes and then compiled to C and executed as machine code. Javascript is executed on a web browser and is interpreted/JITed in a sandbox and executed alongside the heavy web browser code. I used PHP and Javascript because those are 2 languages I know and the syntax is very similar. And it's easy for anyone to test. And I'm timming both languages. And I'm really sorry but I'm not getting the reasoning behind the way you propose to calculate the overhead. My view is that adding +99^97 will sow down the code. And nothing else. – Sphenogram