Hacker News Reader

Comment by sesqu | Hacker News Reader

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

View on HN

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();

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.

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.

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

Reply on news.ycombinator.com