3 ms·
FWIW, this code's over a decade old. Presumably if it had any negative performance implications, someone would have noticed by now: author kocienda <kocienda
by js2 14y ago
FWIW, this code's over a decade old. Presumably if it had any negative performance implications, someone would have noticed by now:
author kocienda <kocienda@>
Fri, 24 Aug 2001 10:24:45 -0400 (14:24 +0000)
Imported sources from kde-2.2 distribution
http://git.chromium.org/gitweb/?p=external/Webkit.git;a=blob;f=JavaScriptCore/kjs/array_object.cpp;hb=66a6d360850d1643dc51807f9c6c0e0029ce3459#l292 http://git.chromium.org/gitweb/?p=external/Webkit.git;a=blob...
- trebor 14y agoThis is a big assumption. See this animated example that danso posted: http://www.sorting-algorithms.com/ 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 14y agoOne 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.
- sesqu 14y agoI 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 agoNote 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 agoThis 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.