bitwise optimizations

564 views
Skip to first unread message

Michael Deal

unread,
Feb 22, 2012, 5:00:10 PM2/22/12
to Closure Compiler Discuss
Would it be possible to add bitwise optimizations to the closure
compiler? Or would this be out of the scope?

For instance, the following are all the same, but the bitwise versions
are faster;

Math.ceil(n) === (n + 1) >> 0; // + 20%
Math.floor(n) === (n >> 0);
Math.round(n) === (n + 0.5) >> 0;
Math.max(a, b) === (a > b) ? a : b; // + 15%
Math.min(a, b) ===  (a < b) ? a : b;
Math.abs(n) === n > 0 ? -n : n; // + 10%

I think these would all be good candidates for optimization.

Alan Leung

unread,
Feb 22, 2012, 5:19:58 PM2/22/12
to closure-comp...@googlegroups.com

Nick Santos

unread,
Feb 22, 2012, 5:34:56 PM2/22/12
to closure-comp...@googlegroups.com
You have to be very careful. For example,

var n = '1.6';
Math.ceil(n);
=> 2
(n + 1) >> 0
=> 1

John Lenz

unread,
Feb 23, 2012, 1:17:24 AM2/23/12
to closure-comp...@googlegroups.com
There is also range issues.  bitwise ops truncate to 32 bits, but javascript numbers can represent 53-bits intergers.  So you can only use bit-ops if you know you are working with a 32-bit range integers.  The compiler doesn't currently have any range checking logic so those are no-starters in the general case.

With Math.abs/min/max you would need to check the behavior around -0 and NaN but I expect the logic needs to be more complex, which is why the substitutions are faster (they are making assumptions about values).

Damian M. R.

unread,
Feb 23, 2012, 8:07:34 AM2/23/12
to Closure Compiler Discuss
According to JSPerf, the bitwise operations run more or less as fast
as the Math operations in Chrome (although I couldn't find performance
test cases for all of the operations you mentioned).

http://jsperf.com/math-floor-vs-math-round-vs-parseint/5

The difference seems to be bigger in other browsers, though. Even in
Safari, the bitwise ops. seem to run faster.

Damian M. R.

unread,
Feb 23, 2012, 8:09:37 AM2/23/12
to Closure Compiler Discuss
Anyway, I just wanted to mention that. I wasn't aware of the details
John and Nick mentioned.

Michael Deal

unread,
Feb 23, 2012, 4:44:12 PM2/23/12
to Closure Compiler Discuss
Nick Santos - Thanks for the headsup on Math functions parsing float
strings. To get around this, a plus can be added before the number to
be parsed: (+'1.6'+0.5)>>0;  There was also an issue when the number
is less than zero.  With these modifications, the new bitwise
operations looks like this;

Math.round(n) === +n+(n<0?-0.5:+0.5)>>0
Math.ceil(n) === +n+(n<0?-1:0)>>0;
Math.floor(n) === +n+(n<0?-1:0)>>0;

John Lenz - That's a great point about the range truncation… I have no
workarounds there…  And, you're right again on the NaN handeling,
there are issues there, as NaN is neither greater 1 or less than 1—as
well as with Infinity, as Infinity>>0 === 0.  I have no neat
workarounds there either.

Damien M. R. - That perf test is an older revision, the newer one
shows much more dramatic improvements.  I think the difference is the
perf test has an overhead, and the newest test runs multiple Math.*'s
on each iteration, giving a better idea of how the Math.* functions
are performing, and less on the overhead of the perf test.  Also, the
shuffle makes sure that the engine cannot cache the results… but might
be totally off there, you can check out the latest test here;  http://
jsperf.com/math-floor-vs-math-round-vs-parseint/35

I've modified this perf test to target these updates bitwise
operations;

http://jsperf.com/bitwise-vs-math-object

My results indicate a 54% speed increase on the Bitwise floor;

Math.floor: 4,158,453
Bitwise floor: 9,092,205

And a 74% increase on Bitwise round;

Math.round: 2,383,835
Bitwise round: 9,197,770

Conclusion: Probably not appropriate for Closure Compiler?  But still
a worthwhile optimization, if you trust the data you're working with
(no NaN's), don't need 52bit precision, and don't need to compare
against Infinity... and you are processing lots of data :)





On Feb 22, 10:17 pm, John Lenz <concavel...@gmail.com> wrote:
> There is also range issues.  bitwise ops truncate to 32 bits, but
> javascript numbers can represent 53-bits intergers.  So you can only use
> bit-ops if you know you are working with a 32-bit range integers.  The
> compiler doesn't currently have any range checking logic so those are
> no-starters in the general case.
>
> With Math.abs/min/max you would need to check the behavior around -0 and
> NaN but I expect the logic needs to be more complex, which is why the
> substitutions are faster (they are making assumptions about values).
>
>
>
>
>
>
>
> On Wed, Feb 22, 2012 at 2:34 PM, Nick Santos <nicksan...@google.com> wrote:
> > You have to be very careful. For example,
>
> > var n = '1.6';
> > Math.ceil(n);
> > => 2
> > (n + 1) >> 0
> > => 1
>
> > On Wed, Feb 22, 2012 at 5:19 PM, Alan Leung <acle...@google.com> wrote:
> > > Take a look at:
>
> >http://code.google.com/p/closure-compiler/wiki/FAQ#How_do_I_submit_a_...
>
> > > Can you provide more information?
>
> > > -Alan
>

Alan Leung

unread,
Feb 24, 2012, 5:22:40 PM2/24/12
to closure-comp...@googlegroups.com

I've modified this perf test to target these updates bitwise
operations;

http://jsperf.com/bitwise-vs-math-object

My results indicate a 54% speed increase on the Bitwise floor;

Math.floor: 4,158,453
Bitwise floor: 9,092,205

And a 74% increase on Bitwise round;

Math.round: 2,383,835
Bitwise round: 9,197,770

Conclusion: Probably not appropriate for Closure Compiler?  But still
a worthwhile optimization, if you trust the data you're working with
(no NaN's), don't need 52bit precision, and don't need to compare
against Infinity... and you are processing lots of data :)


Agree. Thanks for testing those out.

If your app relies heavily on these operations, you can easily monkey patch it or implement your own.

Size wise, if you have your own implementation of these, Closure Compiler is pretty good at inlining them for you.

The cost of doing all the range and value analysis is probably not worth it.

-Alan
Reply all
Reply to author
Forward
0 new messages