Saturday, 7 July 2012

Well, I'm floored

How do you floor (or truncate) a floating-point number in JavaScript? (E.g., take a value like 5.7 and get just the 5?). The answer is simple: Use Math.floor. That's the right answer at least 99.99% of the time. It's clear, straightforward, easy to read, easy to maintain. It does what it says on the tin:

console.log(Math.floor(5.7)); // "5"

Sorted.

But you see people doing other things in the name of "performance," which is the purpose of this post: Primarily, to explain what they're doing; and also to see how much actual benefit they're getting from it.

Why performance? On rare occasions, you may have an operation where you need to squeeze every last bit of performance out that you can. The theory here is: Function calls are cheap, but they aren't free, and unless the JavaScript engine you're using does static analysis of your code, when call Math.floor it has to look up the Math identifier (which means walking the scope chain to see if it's been shadowed, before ultimately finding it at the outermost level, the global object), look up its floor property, and then call the function that property points to. So if there's a more direct route, people want to take it when they're looking for every last cycle.

And what they turn to is bitwise operations. JavaScript only has floating-point numbers, of course, but its bitwise operations are defined in terms of 32-bit integers. So when you apply those operations to a number, the first thing that happens is that the number is turned into an integer (whole number) by just chopping off any fractional part (see the internal ToInt32 operation for details). Chopping off the fractional portion is, of course, floors the number — exactly what we want. (Well, with a caveat: The bitwise operators "floor" positive numbers, but they "ceil" negative numbers. "Floor" always goes down, and of course for negative numbers "down" is away from zero rather than toward it; so Math.floor(-12.1) is -13, not -12. When you just chop off the fractional part like the bitwise ops do, you get -12 instead.)

There are lots of operations to choose from that will floor the number without actually changing its value; I'll list them in rough order of how often I've seen people use them:

  • Double bitwise NOT: ~~num
  • Bitwise OR with zero: num | 0
  • Left bitwise shift, but not really shifting: num << 0
  • Right bitwise shift, but not really shifting: num >> 0
...and there are also these, which I've never seen anyone actually use as they're a bit clunkier than the above:
  • Unsigned right bitwise shift, but not really shifting: num >>> 0
  • Bitwise AND with all-bits-on: num & 0xFFFFFFFF
  • Double bitwise XOR with zero: num ^ 0 ^ 0 (or indeed, any other number, but zero is easy to type)

But do they really go faster? As always, it depends on what engine you're using:


Figure 1 Math.floor vs. the bitwise operators
(click image for full-size version)
(interactive version on jsperf)

(Compare only the operations on the same browser; the different browsers were run on different machines, so their speed can't be usefully compared with each other.)

The first take-away from that chart is: Things ain't like they used to be. It used to be that the bitwise operators were a lot faster than Math.floor. But engines have really stepped up their game in terms of scope chain resolution speed and function call overhead/inlining. (To give you an idea: IE7 does the bitwise OR with 0 nearly nine times faster than Math.floor, much more dramatic than any of the results above.)

The second take-away is: On most engines, yes, the bitwise operators are faster than Math.floor, either very slightly faster, or markedly faster. The outlier here is Firefox 3.6, which must have some specific Math.floor optimization as it screams past the bitwise operators. More recent versions of Firefox don't show that behavior.

The third take-away is: All bitwise operators are not equal. Looking at the chart, the best on most engines is the bitwise OR with zero (num | 0; the bright red lines) — unless you're using Safari. The most reliable all-rounder (performs well across engines, even if not in first place most of the time) is, oddly, the signed right-shift (num >> 0; the reddish-pink, second from the bottom of each grouping).

And finally, we can't tell this from that chart per se, but it's worth noting that using the bitwise operators tends to give you the greatest benefit on the slowest engines; e.g., there's not much in it on recent Chrome or Firefox, but there's a much larger difference on the slower IE8, IE9, Opera, and Safari engines (again, Firefox 3.6 seems to be the outlier here).

So if you've been wondering what that n = n|0 was doing in that code you saw, now you know; it's chopping the fractional part off n — either for performance reasons, or because the coder wanted 12.7 to become 12 and -12.1 to become -12 rather than -13. And it looks like, in those very rare situations where it matters, you do actually get a performance benefit where you need it using the more-obscure, but faster bitwise operation to get the job done. My recommendation: Just be sure to comment what you're doing. :-)

Happy Coding!

6 comments:

Petr 'PePa' Pavel said...

Very nice.
Excuse my ignorance, but why haven't you included parseInt() in the benchmark?

T.J. Crowder said...

@PePa:

Thanks!

"...why haven't you included parseInt() in the benchmark?"

It didn't occur to me to. :-) parseInt, like Math, is a property of the global object, so we have the same scope resolution thing. Granted we skip the property lookup, and then we do the function call. But since the first step of parseInt is to turn its input into a string, we take a hit there. Then of course, it has to parse the result from a string back into a number, in a generic fashion driven by the radix. So my prediction is that it would be markedly slower than Math.floor. Let's test that. Sure enough, parseInt is indeed slower, pretty much across the board; dramatically so in Chrome. :-)

Petr 'PePa' Pavel said...

Interesting results. I'm surprised parseInt is so slow in Chrome when it's faster in FF.
Thanks for finding the test for me, I'm a lazy bastard.

T.J. Crowder said...

@PePa:

"I'm surprised parseInt is so slow in Chrome when it's faster in FF."

It isn't, for me on Linux. I was really surprised by your statement, so I went back to the jsPerf page, and saw that there had been a second Firefox 13 test. I'm guessing that's yours. I seem to recall you use Windows. Very surprising that parseInt should be slower than Math.floor for me on Linux and the opposite for you on Windows, when we're both running Firefox 13.0.1!

Just goes to prove: It's almost never worth optimizing until/unless you have a real problem to solve. :-) I've said before, this is even more true in JavaScript on the web (all those different engines!) than it is normally...

Best,

-- T.J. :-)

mcprogrammer said...

It might be worth mentioning that when you're dealing with negative numbers, the bitwise operations are equivalent to the ceiling operation, not floor. So, as always, make sure the code is *really* going to do what you want it to do first.

T.J. Crowder said...

@mcprogrammer:

Critical point to make, thank you! I've added that in.

Best,

-- T.J.