3 ms·
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
by 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 agoBy 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 agoHmm… 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.