4 ms·

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

by sesqu 14y ago

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

deleted 14y ago
[deleted]
js2 14y ago
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 http://trac.webkit.org/wiki/JavaScriptCore
bdash 14y ago
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 14y ago
  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 14y ago
    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.

by sesqu 14y ago

deleted 14y ago

[deleted]

js2 14y ago

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 http://trac.webkit.org/wiki/JavaScriptCore

bdash 14y ago

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 14y ago
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 14y ago
  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.