title: Jump in running time of repeated splice in WebKit
body: <p>Running the following in the WebKit console (in Chrome or Safari) takes ~200ms. Running the same code with numbers smaller than 50855, you get what appears to be an approximately linear O(<em>n</em>) running time. (For example, with 1e4 you get ~40ms.)</p>
  
  <p>However, change that to 50856 &mdash; just an increment by 1 &mdash; and there's a huge jump in the running time (to ~600ms on my 13-inch Al MBP, more like ~2s on an old Debian machine). Thereafter, running time appears to be exponential O(2<sup><em>n</em></sup>): doubling from 50856 to 1e5 yields ~2s on the Mac, which is about a 3.2-fold increase from ~600ms, and doubling again to 2e6 yields a ~10-fold increase. (Note that 3.2<sup>2</sup> &approx; 10.)</p>
  
  <p>In the Opera Dragonfly and in the Firebug consoles, the running time is pretty clearly quadratic O(<em>n</em><sup>2</sup>), as expected (since this splices <em>n</em> times where each splice involves shifting <em>n</em> items in the array).</p>
  
  <p>...what is WebKit doing?</p>
  
  <pre><code>var start = +new Date, a = [];
  for(var i = 0; i &lt; 50855; i++)
    a[i] = i;
  for(var i = 0; i &lt; a.length; i++)
    a.splice(i--, 1);
  +new Date - start
  </code></pre>
  
  <p>If you don't feel like using the console: <a href="http://jsfiddle.net/CVgSt/" rel="nofollow">http://jsfiddle.net/CVgSt/</a> Same behavior, though in WebKit the constant factors are a few times smaller than in the console.</p>