How did Firefox optimize this loop?

Question

Firefox 9.0.1 surprised me by showing up my Ω(log n) number-padding algorithm with a Ω(n) loop method when n is small. In every other browser I've seen, the loop is slower, even for small values of n. I know all the browsers are working on optimizing JS, but since all the other, modern browsers are showing the loop to be slower, is there any explanation for the behavior in Firefox 9?

// Ω(log n)
function padNumberMath(number, length) {
    var N = Math.pow(10, length);
    return number < N ? ("" + (N + number)).slice(1) : "" + number
}

// Ω(n):
function padNumberLoop(number, length) {
    var my_string = '' + number;
    while (my_string.length < length) {
        my_string = '0' + my_string;
    }
    return my_string;
}

Update: I don't think this is related to the original question, but I just discovered that IE 9 switches behavior when switching from 32- to 64-bit modes. In 32-bit mode, the Math method wins. In 64-bit mode, the Loop method wins. Just thought I should point that out.

Update 2: MAK caught me in his comment below. The math method's not Ω(1), it's probably more like Ω(log n).

Which one is the Ω(1) method? I do not know of any exponentiation algorithm that is faster than O(log n). — MAK, Dec 28 '11 at 05:22
The key here is it only happens for small values of n. I would assume that there is some sort of loop-unrolling occurring when n is small, leading to the O(1) result. If they further optimized string concatenation in a loop, this could be even quicker. Only looking at the code would provide the true answer, though. — jeffknupp, Dec 28 '11 at 09:44
You would assume, but can you provide any evidence to *show* that there is loop unrolling going on? — David Wolever, Dec 28 '11 at 09:54
@MAK I was ignoring the cost of exponentiation. Fixed in edit. [log n < n for n ≥ 1](http://math.stackexchange.com/questions/65202/how-to-prove-log-n-n), so there ought still be an explanation for the speed of the loop. — kojiro, Dec 28 '11 at 15:07

bobobobo · Accepted Answer · 2011-12-29T00:34:28.030

11

Looking at the results its pretty clear that Firefox didn't do anything to achieve a performance gain.

browserscope

These bars can be read as "speeds" (operations/sec) so bigger bars are better. Everything is to scale.

In Firefox 9, its very clear the "Math" method performs abysmally, while there is little change in "Loop" method between versions.

So there was no "optimization" of any sort in Firefox 9. All that happened between Firefox 8 and 9 with regard to these tests is somehow their math library got slower (Math.pow being slow), or their string library got slower (.slice() being slow).

Looking into this further, it's clear somehow these elementary operations got a bit slower in ff9:

ff8 vs ff9

Both concatenation and Math.pow are a bit slower in FF 9 than in FF 8, which may account for the difference you see in your tests.

Interestingly, the new no-op bar is much longer in FF8 than FF9.

edited Dec 29 '11 at 00:34

answered Dec 28 '11 at 15:49

bobobobo

64,917
62
258
363

Wow, looks like a bug should be opened? I did benchmark some of my code on Firefox 9 and it seemed the 30% improvement from Type Inference they claim is largely accurate... but my code is not math-heavy – P Varga Dec 28 '11 at 16:39
1

That second screenshot just shows that if you make a useless Math.pow call that doesn't have side-effects, Firefox 8 will dead-code eliminate it while Firefox 9 won't. It doesn't have much bearing on the original slowdown which is due to Math.pow being about 40% slower in Firefox 9 than in Firefox 8 because it's not being called as efficiently. I'd suggest always keeping dead-code elimination optimizations in mind when writing benchmarks..... – Boris Zbarsky Dec 28 '11 at 19:24
@BorisZbarsky would assigning the output of the function to a name offset the dead-code check? – kojiro Dec 28 '11 at 21:58
@BorisZbarsky You're right, so I [modified the test](http://jsperf.com/ways-to-0-pad-a-number/7) and added a `dead()` section (that does nothing) to make sure the tests don't do nothing (if they do, they will line up with `dead()`). The results point to the same conclusion, however, but there isn't as large a difference in the new test – bobobobo Dec 29 '11 at 00:27
@kojiro The only way to defeat dead-code elimination is to make sure the value ends up stored somewhere permanently (e.g. in a global variable). Assigning to a local var might work sometimes, but not others; it's basically depending on bugs in the dead-code eliminator. – Boris Zbarsky Dec 29 '11 at 01:20
@bobobobo Sure, there's an actual 40% or so slowdown too. I did say that! – Boris Zbarsky Dec 29 '11 at 01:20

score 3 · Answer 2 · answered Dec 28 '11 at 15:32

It could be as fast a arraycopying the parameter string into a new char array, which perhaps are by default initialized to a relevant character, in this case a numeral.

Perhaps something about recognizing the recursive assignment that involves a constant permits a quick concatenation of a string of length-mystring.length+1 '0's with mystring.

Alternately it could be something as simple as the Firefox exponentiation becoming sloppier in not using the exponent's binary expansion for repeated squaring.

score 0 · Answer 3 · answered Dec 28 '11 at 15:13

0

Firefox 9.0.1 surprised me by showing up my Ω(1) number-padding algorithm with a Ω(n) loop method when n is small.

Isn't that sentence missing some parts? It was showing up as being faster, or something? And why are you concatenating empty Strings to Numbers? Why not just construct a String?

And yeah, your O(1) is really O(log)...

Anyways, the explanation is probably due to Type Inference in Firefox 9

answered Dec 28 '11 at 15:13

P Varga

19,174
12
70
108

1

"showing up" can mean "did better than", as in "I scored 9 points, but Péter Varga showed me up by scoring 11 points". Not sure that's what OP meant, but that's how I interpreted it. – Wesley Murch Dec 28 '11 at 15:38
3

"showing up" is used in a different sense from "appearing" here. he is employing "to show up" to mean "to prove superior to". http://idioms.thefreedictionary.com/show+up – jela Dec 28 '11 at 15:50
@jela Indeed, that is how I meant it. – kojiro Dec 28 '11 at 15:54

How did Firefox optimize this loop?

3 Answers3