▲ 175 points
back
78 comments
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.
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't exist, which means they'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 minutes to start up, even with aggressive caching enabled. :(
Well more like O(m * n) calls where m << n, but that is a fair point.
In this case, the constant really can't be ignored since file system access is so slow. Ruby scans for .rb and .so files (or .jar on JRuby).
Some other fun is RubyGems always appends to the $LOAD_PATH, so whenenver you require from a gem that hasn't been loaded yet, you're guaranteed to scan the entire $LOAD_PATH on the off-chance there's a conflicting partial path. And you can't cache contents of the $LOAD_PATH entries unless you have a filesystem watcher because the contents of the path can change and Ruby allows that.
My favorite one of these in JavaScript is building an array by unshifting onto it:
var array = [];
for (...) {
array.unshift(whatever);
}
(Solving this in your code is usually trivial, by the way: just replace unshift with push and use Array.reverse at the end.)
On a related note, NSArray, the standard array class in Cocoa, is actually implemented as a circular array under the hood, allowing you to unshift/shift just as efficiently as you can push/pop.
The reason it's able to do this is because it doesn't have any API that exposes a pointer to its object storage. Without the need to have a pointer to its storage, there's no need to ensure the objects are actually stored contiguously and in-order, which means using a circular array is a trivial optimization. There are other data structures it could use instead, such as a sequence of fixed-length arrays like (common implementations of) std::deque, but I guess a circular buffer was chosen because it meets all of the complexity guarantees and is still pretty simple. Although I'm also generalizing a bit, because it turns out that NSArray/CFArrayRef actually changes the implementation it uses when the array gets large enough (I don't remember precisely where to find it, but there's a blog post out there with details on the observed performance of NSArray/CFArrayRef as it grows). But in most cases, it's probably a circular array.
On that note, I'd think that using a circular array would be an obvious optimization for any JavaScript implementation. JavaScript doesn't have any need to store its values contiguously and in-order (since JavaScript doesn't have pointers so it can't possibly expose a pointer to its storage). I would expect that unshifting arrays (and shifting them) is common enough that this optimization is an obvious win for all engines.
I'm working on a data structure that is double-ended as well as contiguous: https://github.com/orlp/devector
Of course, it depends on the language. If you're using a language with linked lists, appending is the wrong way to do it. :)
On a different note: it's nice to see this here, it validates my choice to .reverse() and .push() when using an array as a queue today.
Linked lists are only useful in very few situations and this is not one of them.
You could keep pointers to both the head and tail in the list object though. Then adding and removing stuff would be O(1) for both ends.
IMO all arrays should be double-ended.
But wouldn't that slow down all arrays in the general case....?
A fun one in C is:
for(int i = 0; i < strlen(s); i++)
doSomething(s[i]);
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'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're using and even which optimization level you're using.
The effect you're describing can happen to any inlined function.
Of course a better way of doing it in C is:
for (char* p = s; *p; p++) {
doSomething(*p);
}Fun stuff.
My favorite example goes a long way back. The string garbage collection in Applesoft BASIC (Microsoft BASIC for the Apple II, introduced in 1977) had a loop that was written backwards. The result worked correctly, but it was accidentally quadratic.
Variables were stored low in memory. A string variable held a pointer to its value, which was stored in high memory. When high memory filled up, GC ran on the string values, pushing the ones that were still used up to the top of memory. The main loop for this GC routine should have run from the top of string space to the bottom, copying each string value that was still used to its final location higher in memory. But, alas, it ran from the bottom of string space to the top, so each iteration copied up all used string values that had been found so far. Thus, if there were n used string values, the GC routine would do O(n^2) copy operations, instead of the O(n) copies that the correctly written routine would have done.
So code like the following -- with K set to some appropriate value -- would, at some point, pause for a long time indeed.
10 DIM A$(K): REM STRING ARRAY; K SHOULD BE A LARGE-ISH NUMBER
20 FOR I = 0 TO K
30 A$(I) = "X": REM EVENTUALLY UNUSED VALUE; GC WILL DELETE
40 A$(I) = "Y": REM USED VALUE
50 NEXT I
Kind of tangent, but this is the reason I find a formal CS degree important, despite the "hacker school movement" that tells you otherwise. Sure, you may never need the stuff you learned in Algorithms or Computer Architecture, but having gone through these classes you sort of develop a knack of recognizing these kind of bad code: you instantly know the time/space complexity of your code, and what the best-known complexity might be.
Sure, premature optimization is the root of all evil, but there's a huge difference between not knowing there's a faster solution and actively choosing not to use the faster solution because it's harder to read/harder to maintain/more bug prone/etc.
This was a good one:
Post it, will you? :)
So. Having just messed up an interview at a large tech company by having trouble deriving an O(n) solution on the whiteboard, anyone got any good tips on how to take algorithms / data structures to the next level and look good at this sort of thing?
Having given a lot of complexity interviews, I value a candidate who says, "This is O(n^2) and it seems like there's a faster way, but I can't see it" over one who stumbles on the right solution.
If they had to tell you your solution was slow, and a linear solution exists it might not be your inability to find it that made you mess up the interview. Get good at recognizing inefficient computation first, then worry about making it more efficient. On the job you can always consult a coworker/google, but if you don't know to do that you're going to ship some slow code.
Really, unless you're trying to find a tighter upper bound on something like matrix multiplication, it just comes down to practice.
Most of the things you're going to run into on a daily basis are going to follow the same pattern, and so you just get an intuitive sense of runtimes after a little while. At my first internship, whenever I wrote a new function, I would mentally take note of what the runtime complexity was, which served two purposes:
1) It got me into the habit of thinking about runtime complexities.
2) It forced me to think about why different operations have different runtimes, which made them easy to reason about in the vast majority of cases.
If you're having a hard time thinking about complexity analysis, the same process might work for you.
It seems the holy grail is almost always linear. Especially in interviews. Main thing to look for is if you find yourself doing something you have already done before.
Above that, just know the general idea behind different data structures. HashTables and binary trees will probably have you covered. More data structures can't hurt, though. Tries, BTrees, etc.
Though, I can't think of a single time I have used some of the more advanced items. Linear searches with sentinal values being my personal favorite optimization that I will likely never directly code.
That's a really good point, thanks taeric.
Anything less than O(n) obviously means not needing to look at every element of the input, i.e. it's already sorted or similar. For most other interview problems that seems like a reasonable lower bound in the absence of more detailed analysis. I guess the recruiter's advice to go practice on TopCoder wasn't just copy-paste.
As far as analysis, I believe this is the course I followed awhile back on MIT OCW and found quite good:
http://ocw.mit.edu/courses/electrical-engineering-and-comput...
"Introduction to Algorithms" (2005) but according to OCW more similar to what's now the more advanced "Design and Analysis of Algorithms".
Not sure how much it'll help you in deriving solutions, but good if you have an interest in actually learning the subject.
Project Euler is great for practicing this sort of thing. With the early questions, you can solve them however and it's fine, but many of the later problems have an obvious quadratic (or worse) solution that ends up being too slow in practice to finish in a sane amount of time, and it forces you to come up with a better algorithm to actually solve the puzzle. As a bonus, once you solve it you get to see other people's solutions, which are often super clever.
Pick up the book Elements of Programming Interviews and practice.
How timely. I just ran into one today using the duktape† javascript engine and the hogan‡ mustache template expansion code. If you make a ~4MB output using deep in your library bowels…
output += tiny_string;
Switching the hogan buffer appending code to…
chunks.push(tiny_string);
output = chunks.join('');
␄
I ran into this a few years back. In a gawk program, I had to build a 300,000,000 character string by concatenating about 10,000,000 32-character strings. My naive code of doing 10,000,000 "a = a+str" took forever. I finally did sqrt(n) iterations of sqrt(n) concatenations and it took about 10 seconds.
Yes.
I'm not using the V8 engine. Tiny embedded engine, no super powers other than EC5 correct, small size, and reasonable performance.
Of course V8 and its multimillion dollar development cost rivals probably only have this superpower because programers kept writing quadratic code.
Not all Javascript implementations use ropes internally.
From C++: calling vector<T>::reserve in a loop can lead to quadratic behavior. For example:
std::vector<int> v;
while (...) {
v.reserve(v.size() + 3);
v.push_back(0);
v.push_back(1);
v.push_back(2);
}
My "favourite" example of this was a previous company that used TeamCity for CI builds. At the time (no idea if it's still true) TeamCity knew when a maven project depended on another project, directly or transitively - but it didn't distinguish between the two cases.
So if you committed a change to the low-level "core" library, it would rebuild every project - and then every project except for the two that depended directly on core. And then every project but those three, and so on. It took days.
With a naive mark-and-sweep GC and a policy that runs the GC every N allocations minus frees, it's very easy to write an N^2 algorithm:
r = []
for i in range(1000000):
r.append({})
Incidentally, if you're worried about the appends' reallocations throwing off your linear time, take a look at Objects/listobject.c :
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);Sure, the growth of the list itself is not quadratic, but the allocations of the new objects (the {} part) invokes a GC every K iterations, and a naive, stop-the-world, mark-and-sweep GC is O(n) in number of live objects.
Python uses reference counting to save on GC time. This is one of the reasons why it has GIL.
I recall a story about one of these in Haskell's Cabal, but I can't find it on google now.
I think you're thinking of this bugfix: https://github.com/nominolo/HTTP/commit/b9bd0a08fa09c6403f91...
HN discussion: https://news.ycombinator.com/item?id=6912474
If I remember correctly it was a left associated buffer building operation.
I once found this bug, where a destructor was taking forever:
hash_set<char*> hash;
// <fill up/use hash>
while(!hash.empty()) {
free(*hash.begin());
hash.erase(hash.begin());
}
If this was quadratic, then the hash table was not implemented correctly. Erase in hash table should be amortized O(1).
What exactly am I looking at here?
Discussions of systems-level applications that turn out to operate in quadratic (O(n^2)) time. It's a poke at algorithmic inefficiency.
Algorithms that unintentionally have quadratic complexity, it would seem.
i seem to remember that the (gotcha, and bizarre) link order requirement for gcc reveals that it has a problem like this where it looks for symbols in order. although i can't be sure without looking at the code (and i cba)
the obvious gotcha free solution is linear but requires two passes (i'm not sure thats a bad thing)...
Nice concept to go along with things like Accidentally Turing Complete.
http://beza1e1.tuxen.de/articles/accidentally_turing_complet...
Interesting that it stops at Pokemon Yellow - maybe that's all that was known at the time. It seems like any video game where you can corrupt memory is potentially "Turing complete" - which is many of the old console game as the speedrunning community has discovered.