javascript performance - How did Firefox optimize this loop?




measure window.performance (4)

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


Answers

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


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.


This algorithm is not optimal for winning the game, but it is fairly optimal in terms of performance and amount of code needed:

  if(can move neither right, up or down)
    direction = left
  else
  {
    do
    {
      direction = random from (right, down, up)
    }
    while(can not move in "direction")
  }




javascript performance algorithm firefox-9