javascript - How did Firefox optimize this loop? - Stack Overflow

admin管理员组

文章数量:1205996

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

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

• javascript
• performance
• algorithm
• firefox-9

Share Improve this question Follow edited Dec 28, 2011 at 15:04 kojiro asked Dec 28, 2011 at 4:22 kojirokojiro 77.1k1919 gold badges150150 silver badges212212 bronze badges 7

• 5 Which one is the Ω(1) method? I do not know of any exponentiation algorithm that is faster than O(log n). – MAK Commented Dec 28, 2011 at 5: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 Commented Dec 28, 2011 at 9:44
• You would assume, but can you provide any evidence to show that there is loop unrolling going on? – David Wolever Commented Dec 28, 2011 at 9:54
• @MAK I was ignoring the cost of exponentiation. Fixed in edit. log n < n for n ≥ 1, so there ought still be an explanation for the speed of the loop. – kojiro Commented Dec 28, 2011 at 15:07
• 1 "O(1) when n is small" sounds funny. :) – Kos Commented Dec 28, 2011 at 15:14

 |  Show 2 more comments

3 Answers 3

Sorted by: Reset to default 11

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

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:

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.

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.

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

本文标签： javascriptHow did Firefox optimize this loopStack Overflow