StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><em>Note added August 2013, updated February 2015: The answer below from 2009 relates to JavaScript's generic <code>Array</code> type. It doesn't relate to the newer <strong>typed</strong> arrays defined in ES2015 [and available now in many browsers], like <code>Int32Array</code> and such. Also note that ES2015 adds a <code>fill</code> method to both <a href="http://www.ecma-international.org/ecma-262/7.0/index.html#sec-array.prototype.fill" rel="nofollow noreferrer">Arrays</a> and <a href="http://www.ecma-international.org/ecma-262/7.0/index.html#sec-%typedarray%.prototype.fill" rel="nofollow noreferrer">typed arrays</a>, which is likely to be the most efficient way to fill them...</em></p> <p><em>Also, it can make a big difference to some implementations how you create the array. Chrome's V8 engine, in particular, tries to use a highly-efficient, contiguous-memory array if it thinks it can, shifting to the object-based array only when necessary.</em></p> <hr> <p>With most languages, it would be pre-allocate, then zero-fill, like this:</p> <pre><code>function newFilledArray(len, val) { var rv = new Array(len); while (--len >= 0) { rv[len] = val; } return rv; } </code></pre> <p><strong>But</strong>, JavaScript arrays <a href="http://blog.niftysnippets.org/2011/01/myth-of-arrays.html" rel="nofollow noreferrer">aren't really arrays</a>, they're key/value maps just like all other JavaScript objects, so there's no "pre-allocate" to do (setting the length doesn't allocate that many slots to fill), nor is there any reason to believe that the benefit of counting down to zero (which is just to make the comparison in the loop fast) isn't outweighed by adding the keys in reverse order when the implementation may well have optimized their handling of the keys related to arrays on the theory you'll generally do them in order.</p> <p>In fact, Matthew Crumley pointed out that counting down is markedly slower on Firefox than counting up, a result I can confirm — it's the array part of it (looping down to zero is still faster than looping up to a limit in a var). Apparently adding the elements to the array in reverse order is a slow op on Firefox. In fact, the results vary quite a bit by JavaScript implementation (which isn't all that surprising). Here's a quick and dirty test page (below) for browser implementations (very dirty, doesn't yield during tests, so provides minimal feedback and will run afoul of script time limits). I recommend refreshing between tests; FF (at least) slows down on repeated tests if you don't.</p> <p>The fairly complicated version that uses Array#concat is faster than a straight init on FF as of somewhere between 1,000 and 2,000 element arrays. On Chrome's V8 engine, though, straight init wins out every time...</p> <p>Here's the test page (<a href="http://jsbin.com/osijop" rel="nofollow noreferrer">live copy</a>):</p> <pre><code><!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>Zero Init Test Page</title> <style type='text/css'> body { font-family: sans-serif; } #log p { margin: 0; padding: 0; } .error { color: red; } .winner { color: green; font-weight: bold; } </style> <script type='text/javascript' src='prototype-1.6.0.3.js'></script> <script type='text/javascript'> var testdefs = { 'downpre': { total: 0, desc: "Count down, pre-decrement", func: makeWithCountDownPre }, 'downpost': { total: 0, desc: "Count down, post-decrement", func: makeWithCountDownPost }, 'up': { total: 0, desc: "Count up (normal)", func: makeWithCountUp }, 'downandup': { total: 0, desc: "Count down (for loop) and up (for filling)", func: makeWithCountDownArrayUp }, 'concat': { total: 0, desc: "Concat", func: makeWithConcat } }; document.observe('dom:loaded', function() { var markup, defname; markup = ""; for (defname in testdefs) { markup += "<div><input type='checkbox' id='chk_" + defname + "' checked>" + "<label for='chk_" + defname + "'>" + testdefs[defname].desc + "</label></div>"; } $('checkboxes').update(markup); $('btnTest').observe('click', btnTestClick); }); function epoch() { return (new Date()).getTime(); } function btnTestClick() { // Clear log $('log').update('Testing...'); // Show running $('btnTest').disabled = true; // Run after a pause while the browser updates display btnTestClickPart2.defer(); } function btnTestClickPart2() { try { runTests(); } catch (e) { log("Exception: " + e); } // Re-enable the button; we don't yheidl $('btnTest').disabled = false; } function runTests() { var start, time, counter, length, defname, def, results, a, invalid, lowest, s; // Get loops and length s = $F('txtLoops'); runcount = parseInt(s); if (isNaN(runcount) || runcount <= 0) { log("Invalid loops value '" + s + "'"); return; } s = $F('txtLength'); length = parseInt(s); if (isNaN(length) || length <= 0) { log("Invalid length value '" + s + "'"); return; } // Clear log $('log').update(''); // Do it for (counter = 0; counter <= runcount; ++counter) { for (defname in testdefs) { def = testdefs[defname]; if ($('chk_' + defname).checked) { start = epoch(); a = def.func(length); time = epoch() - start; if (counter == 0) { // Don't count (warm up), but do check the algorithm works invalid = validateResult(a, length); if (invalid) { log("<span class='error'>FAILURE</span> with def " + defname + ": " + invalid); return; } } else { // Count this one log("#" + counter + ": " + def.desc + ": " + time + "ms"); def.total += time; } } } } for (defname in testdefs) { def = testdefs[defname]; if ($('chk_' + defname).checked) { def.avg = def.total / runcount; if (typeof lowest != 'number' || lowest > def.avg) { lowest = def.avg; } } } results = "<p>Results:" + "<br>Length: " + length + "<br>Loops: " + runcount + "</p>"; for (defname in testdefs) { def = testdefs[defname]; if ($('chk_' + defname).checked) { results += "<p" + (lowest == def.avg ? " class='winner'" : "") + ">" + def.desc + ", average time: " + def.avg + "ms</p>"; } } results += "<hr>"; $('log').insert({top: results}); } function validateResult(a, length) { var n; if (a.length != length) { return "Length is wrong"; } for (n = length - 1; n >= 0; --n) { if (a[n] != 0) { return "Index " + n + " is not zero"; } } return undefined; } function makeWithCountDownPre(len) { var a; a = new Array(len); while (--len >= 0) { a[len] = 0; } return a; } function makeWithCountDownPost(len) { var a; a = new Array(len); while (len-- > 0) { a[len] = 0; } return a; } function makeWithCountUp(len) { var a, i; a = new Array(len); for (i = 0; i < len; ++i) { a[i] = 0; } return a; } function makeWithCountDownArrayUp(len) { var a, i; a = new Array(len); i = 0; while (--len >= 0) { a[i++] = 0; } return a; } function makeWithConcat(len) { var a, rem, currlen; if (len == 0) { return []; } a = [0]; currlen = 1; while (currlen < len) { rem = len - currlen; if (rem < currlen) { a = a.concat(a.slice(0, rem)); } else { a = a.concat(a); } currlen = a.length; } return a; } function log(msg) { $('log').appendChild(new Element('p').update(msg)); } </script> </head> <body><div> <label for='txtLength'>Length:</label><input type='text' id='txtLength' value='10000'> <br><label for='txtLoops'>Loops:</label><input type='text' id='txtLoops' value='10'> <div id='checkboxes'></div> <br><input type='button' id='btnTest' value='Test'> <hr> <div id='log'></div> </div></body> </html> </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload