Huy's Blog

Is bit shifting in JavaScript fast?

As a programmer, we know that bitwise operators are fast. And to optimize our code, we usually replace the regular operators like multiply, divide to bit shifting.

On currently available processors, a bit-wise shift instruction is faster than a multiply instruction and can be used to multiply (shift left) and divide (shift right) by powers of two. - Wikipedia

For example, we can use left shift instead of multiply:

$
(4 \times 2) = (4 \ll 1) = 8
$

Or we can use right shift for division:

$
(16 \div 4) = (16 \gg 2) = 4
$

In fact, some modern compilers automatically convert multiplication to left shift, for example, let's take a look at this simple C program:

shift_test.c

int main() {
    int a = 10;
    return a * 2;
}

If you compile it with Apple's LLVM compiler (on macOS, gcc is just a symlink to LLVM clang):

gcc -S shift_test.c -o shift.s

The assembler code should look like:

//allocate a variable, bind it with 10
movl $10, -8(%rbp)
movl -8(%rbp), %eax
// shift 1 bit left (a << 1)
shll $1, %eax
// return the value
popq %rbp
retq

So, how about JavaScript? Let's do some benchmark.

We will benchmark this two cases, and you can run it yourself here on JSPerf:

Case 1: Using multiply operator

let a = 10;
a * 2;

Case 2: Using left shift

let a = 10;
a << 1;

And here's the result on some popular browsers:

Browser a * 2 a << 1
Firefox 57.0.0 1,728,015,792 ops/sec (faster) 1,707,778,280 ops/sec
Chrome 61.0.3163 633,856,007 ops/sec (faster) 621,598,716 ops/sec
Safari 11.0.0 1,691,557,398 ops/sec (faster) 1,644,711,522 ops/sec

Surprisingly, all of the browsers give us the same result, left shift is slower than multiply. Why?

The reason is hiding behind the implementation of these operators. Let's take a look at the ECMAScript specs to find the answer.

So this is the algorithm behind left shift operator (LEFT << RIGHT):

  1. Let lref be the result of evaluating LEFT.
  2. Let lval be GetValue(lref).
  3. ReturnIfAbrupt(lval).
  4. Let rref be the result of evaluating RIGHT.
  5. Let rval be GetValue(rref).
  6. ReturnIfAbrupt(rval).
  7. Let lnum be ToInt32(lval).
  8. ReturnIfAbrupt(lnum).
  9. Let rnum be ToUint32(rval).
  10. ReturnIfAbrupt(rnum).
  11. Let shiftCount be the result of masking out all but the least significant 5 bits of rnum, that is, compute rnum & 0x1F.
  12. Return the result of left shifting lnum by shiftCount bits. The result is a signed 32-bit integer.

And the algorithm behind multiply operator (LEFT * RIGHT):

  1. Let left be the result of evaluating LEFT.
  2. Let leftValue be GetValue(left).
  3. ReturnIfAbrupt(leftValue).
  4. Let right be the result of evaluating RIGHT.
  5. Let rightValue be GetValue(right).
  6. Let lnum be ToNumber(leftValue).
  7. ReturnIfAbrupt(lnum).
  8. Let rnum be ToNumber(rightValue).
  9. ReturnIfAbrupt(rnum).
  10. Return the result of applying the operator (*, /, or %) to lnum and rnum (in this case is multiply).

That's a lot of things happen in just an operation! And let's look closer at the two function calls ToInt32(), ToUint32() call of left shift, compared to the two ToNumber() calls of multiply.

The algorithm behind ToInt32() function:

  1. Let number be ToNumber(argument).
  2. ReturnIfAbrupt(number).
  3. If number is NaN, +0, −0, +∞, or −∞, return +0.
  4. Let int be the mathematical value that is the same sign as number and whose magnitude is floor(abs(number)).
  5. Let int32bit be int modulo $2^{32}$.
  6. If int32bit ≥ $2^{31}$, return int32bit − $2^{32}$, otherwise return int32bit.

And the algorithm behind ToUint32():

  1. Let number be ToNumber(argument).
  2. ReturnIfAbrupt(number).
  3. If number is NaN, +0, −0, +∞, or −∞, return +0.
  4. Let int be the mathematical value that is the same sign as number and whose magnitude is floor(abs(number)).
  5. Let int32bit be int modulo $2^{32}$.
  6. Return int32bit.

These implementations even make the call to ToNumber(), on the other hand, this is the implementation of ToNumber() if the argument is a number:

  1. Return argument (no conversion).

Nothing happens, just return the value directly. So, by analyzing the algorithms, we can definitely say that ToNumber() is way faster than ToInt32() and ToUint32(). And so on, we can say the multiply algorithm is faster than left shift algorithm.

It's very interesting that it turned out bitwise shifting is not as fast as we think because of the underlying implementation of JavaScript.

Thank you so much for reading this. I hope you found this post helpful. Any feedback would be greatly appreciated!

Created with azeroth.js