<story><title>Accidentally Quadratic</title><url>http://accidentallyquadratic.tumblr.com</url></story><parent_chain></parent_chain><comment><author>kentonv</author><text>Ruby (or maybe specifically Gems) startup is still quadratic in another -- IMO worse -- way: Every require() (that misses cache) searches for the requested file in _every_ dependency package until found. It seems that instead of having the file name itself include the precise package name, Ruby instead treats the packages as a search path that unions a bunch of separate trees into a single logical file tree.&lt;p&gt;The result is that Ruby does O(n^2) stat() calls at startup, where n is the number of dependency packages. Most of these operations are for files that don&amp;#x27;t exist, which means they&amp;#x27;ll miss the filesystem cache and perform absolutely atrociously on top of FUSE, NFS, etc. A typical Ruby app sitting on a loopback FUSE device (i.e. one just mirroring the local filesystem, no network involved) will take &lt;i&gt;minutes&lt;/i&gt; to start up, even with aggressive caching enabled. :(</text></comment>
<story><title>Accidentally Quadratic</title><url>http://accidentallyquadratic.tumblr.com</url></story><parent_chain></parent_chain><comment><author>mikeash</author><text>A fun one in C is:&lt;p&gt;&lt;pre&gt;&lt;code&gt;    for(int i = 0; i &amp;lt; strlen(s); i++)
        doSomething(s[i]);
&lt;/code&gt;&lt;/pre&gt;
strlen() searches for the terminating NUL byte and is thus O(n), which makes the loop quadratic.&lt;p&gt;What makes this especially fun is that strlen is part of the standard library and has defined semantics. That means the compiler is free to hoist the strlen call out of the loop if it can prove that it wouldn&amp;#x27;t alter the standards-specified behavior, like if you never modify the contents of the string. That means your asymptotic performance will depend on which compiler you&amp;#x27;re using and even which optimization level you&amp;#x27;re using.</text></comment>