FWIW, this code's over a decade old. Presumably if it had any negative performan...

sesqu · on July 13, 2012

I ran a simple test with Chrome 20:

  var a=new Array(4e9);
  for (var i=1; i<a.length; i=Math.ceil(i*1.0001))
    a[i]=new Number(i).toString();
  a.sort();

The speed suggest that this sparse string array is not sorted with a quadratic algorithm (today).

bdash · on July 13, 2012

This is also fast in Safari because the array isn't sparse enough for JavaScriptCore to send it down the fallback path.

EDIT: In order to go down the fallback path the array needs to be both sufficiently large and sufficiently sparse (< 12.5% occupied). You can see the difference in algorithms by modifying your test case like so:

Dense, fast path:

    var a = [];
    for (var i = 1; i < 4e6; i++)
      a[i * 5] = i.toString();
    a.sort();

Sparse, fallback path:

    var a = [];
    for (var i = 1; i < 4e6; i++)
      a[i * 10] = i.toString();
    a.sort();

sesqu · on July 13, 2012

By my count, it's very sparse - only 0.003% occupied. I suppose the initial size declaration could make it dense, but then it would use a considerable amount of (virtual?) memory. Unfortunately, I don't have access to Safari to test that.

bdash · on July 13, 2012

Hmm… it looks like I misspoke. The "sparse mode" check that Array.prototype.sort performs in JavaScriptCore appears to be different than the its concept of sparse array storage, which is used under the conditions I described. The "sparse mode" check in the sorting code appears to be related to whether the array instance has getters/setters or properties defined via Object.defineProperty. The performance difference my code demonstrates is due to the extra overhead of iterating the sparse array storage compared to a vector, and not due to the different sorting algorithms that are employed.

js2 · on July 13, 2012

Note that while Chromium uses WebKit as the rendering engine, it does not use JavaScriptCore as the JavaScript engine. Rather, Chromium uses V8 (which is not a WebKit project).

http://trac.webkit.org/wiki/JavaScriptCore

trebor · on July 13, 2012

This is a big assumption.

See this animated example that danso posted: http://www.sorting-algorithms.com/

Yes, a difference of maybe 5ms won't be noticed... unless you're going a lot of sorting. Selection Sort is basically the slowest sort of all.

calinet6 · on July 13, 2012

One thing I learned when optimizing code is to never trust my intuition.

That piece of code you think must be slow and must be impacting the application speed? It might not be consequential at all. Spending 4 hours optimizing it might get you exactly 0% improvement.

And that one line you think is benign and would take 5 minutes to opt might end up being the key to speeding up your entire algorithm tenfold.

It's important to understand speed and complexity when architecting software, but it's just as important to know how it really performs in the real world, on the CPU, with real memory constraints and real data.

I'm not saying this is true at all for this particular algorithm, but it's been uncannily true for me in the past and I still fool myself to this day trying to optimise prematurely based on my primitive human computer.