Accidentally Quadratic
accidentallyquadratic.tumblr.com
accidentallyquadratic.tumblr.com
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. :(
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.
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.)
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.
This means that performance, even in the pathological case, is quite good. If you know you're dealing with a FIFO queue you can always replace devector with a specialized queue. But as a general default container devector is never a bad choice.
Is my assumption wrong, would such a pattern of access not actually result in the "other end" having less free space (and therefore switching the ends it appends to would not result in more shuffles)?
Let's first establish that to get the worst case it's always optimal to append to the end with the least free space. Anything else and you're using allocations more efficiently.
There's two cases. One where reallocation is needed, and one where it is not. Let's look at both seperately.
No reallocation needed: half of the free space "harvested" (as you call it) is enough. End result after shuffling is same free space on both ends, thus it doesn't matter if you switch sides. This is the FIFO case which I analyzed above.
Reallocation needed: the side that needed more space _always_ has more space than the side that was harvested from, because if the harvesting alone was enough we'd be in the "no reallocation" case. This means that if you want the worst case, you will always switch sides.
Let's say there are n elements, the side you're appending to has a free space, and the other side has b free space, and the total memory usage is s. So the model after x reallocations is:
s(x) = 1.5s(x-1)
n(x) = n(x-1) + a(x-1)
a(x) = b(x-1) / 2
b(x) = s(x) - n(x) - a(x)
---
This means that the memory bound is worse than a ring buffer in the worst case, but the 2 moves per operation isn't even worse than just appending to a regular array, assuming the growth factor is 1.5 for both.
In my model below I forgot to account for the mechanism that we sometimes shuffle, rather than reallocate. I've written a new model which can be found here: https://gist.github.com/orlp/439890748c6d55897ba5
The new model shows that the memory bound is indeed 5n/3, and amortized 3 moves per operation are needed in the worst case, compared to 2 moves per operation in perfect conditions.
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.
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.
for (char* p = s; *p; p++) {
doSomething(*p);
}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
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.
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.
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.
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.
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.
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.
output += tiny_string;
Switching the hogan buffer appending code to…
chunks.push(tiny_string);
output = chunks.join('');
␄
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.
…and because SunSpider does it.
https://github.com/WebKit/webkit/blob/master/PerformanceTest...
std::vector<int> v;
while (...) {
v.reserve(v.size() + 3);
v.push_back(0);
v.push_back(1);
v.push_back(2);
}
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.
r = []
for i in range(1000000):
r.append({})
I don't see why tracing collectors need GIL in particular to stop all threads, i.e. why should only one thread be running at a time.
Re. your second paragraph, it is again not inherent to the algorithm, but it does greatly simplify things. In particular, pretty much all tracing algorithms require at least some kind of stop the world event, though some can make this event very limited in duration.
It is much much easier (and results in greater throughput) to stop the world if only one thread is running at a time, because you just do your collection when that one thread triggers a heap mutation.
If you have multiple threads running at once you need to coordinate when you stop the world, which means waiting for the threads to all wind up in a state where they can be stopped (which gets a lot harder if, say, one of the threads never allocates because it's in a tight loop). If it takes too long to do this coordination, your heap might explode on you.
Again, what I'm saying is that a GIL is not an inherent feature of either garbage collection mechanism. This is really pretty obvious when you consider that there's an abundance of implementations of all combinations of (RC, tracing)(GIL, no GIL). Python and Ruby's main implementations both chose a GIL for simplicity's sake (and an at the time safe assumption that single-core performance was more important than multi-core), but most C++ refcounting code uses interlocked counters and the JVM has obviously never used a GIL.
/* 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);HN discussion: https://news.ycombinator.com/item?id=6912474
hash_set<char*> hash;
// <fill up/use hash>
while(!hash.empty()) {
free(*hash.begin());
hash.erase(hash.begin());
}
It's an interesting read, but at the first glance it doesn't look all that different from a lot of other programming blogs out there. A brief one-sentence description of the blog's scope under the title would be nice.
the obvious gotcha free solution is linear but requires two passes (i'm not sure thats a bad thing)...
http://beza1e1.tuxen.de/articles/accidentally_turing_complet...