Ah, should have read past the second paragraph of the first post, my bad.
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.
Lots of things have names related to topics in computer science. Like Y Combinator or Stack Overflow. Neither of those represent the respective companies' entire scopes. Y Combinator has the courtesy toward the uninitiated to actually write "Y Combinator created a new model for funding early stage startups." on the first place you lay your eyes on when you visit the page.
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.
There's nothing unique to refcounting garbage collection that implies you need or should use a GIL. Most naive tracing collectors also have one so they can stop the world and trace every thread's stack at the same time. In both cases there are workarounds that reduce throughput as a tradeoff for decreasing latency (and the two mechanisms start to converge into similar algorithms, incidentally).
There is: you either have to use atomic operations on all the reference counters, which is costly, and not available on all platforms, or you can have only one thread active at a time. This is the most classic problem: "x == 0"; parallel execution of "x += 1" and "x += 1"; now "x == 1" or "x == 2".
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.
I'm not sure why you seem to feel your first paragraph here is a disagreement with what I said. As you point out, there is a well known way to have refcounting act correctly in the face of multiple threads. There are other ways as well involving per-thread shadow counts and such, but that is the most basic way to (as I said) trade throughput for latency.
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.
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.
That's a bit pedantic, innit. It isn't strictly O(1) but with any reasonable implementation the collision resolution algorithm will make it have an amortized O(M), where M << N and therefore effectively constant.
You're wrong. What's worse, you're being pedantic about being wrong.
If your hash function works properly, and you are dynamically resizing your hash by a constant fraction whenever it gets too full, you can bound the probability of hash collisions above, and bound the number of expected hash collisions by a constant. As is standard in resized data structure, the resizing is individually O(n) with frequency O(1/n) for an amortized cost of O(1) per insert.
Put all of that together, and the amortized average cost of an insert into the hash is O(1). This is a well-known standard result, and is the reason why hashes are useful.
To be a pedantic here, I don't think term amortized average cost is useful.
For what I've understood, average cost means average over all possible random inputs. So for specific set inputs, the cost can be larger than that.
Amortized cost means the average cost of the operation over any combination of inputs. So for specific set of inputs, the cost is the stated.
For hash table insertion, both the amortized and average cost can be O(1) with linked-list confliction resolution, but whereas average time of a lookup operation is O(1), amortized is larger (I don't know if there's analysis on this, but O(n) seems correct by gut-feeling).
Amortized analysis refers to determining the time-averaged running time for a sequence of operations.
Note that you are averaging over a sequence of operations, and not any combination of inputs. As that article goes on to explain, amortized analysis is the right thing to use for figuring out the total running time of a sequence of operations.
Let's be concrete. In the case of a dynamically resized hash, the bound on an individual hash insertion when the hashing function works is O(n) because you could be looking at the unlucky insertion that resized the hash. The amortized cost is O(1) because you get to spread that expensive resize over many individual operations. If you're building a hard real time system, you should focus on the O(n) and not use that data structure. If you just want to build a hash table, the O(1) is what matters.
What about the amortized cost of many random hash lookups with linked-list conflict resolution? The distribution of buckets with different numbers of items approximately follows a Poisson distribution. From that we can estimate the average number of comparisons. And find out that the amortized cost is on average O(1).
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?
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.
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.
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.
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.
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.
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;
… a million or so times in Javascript, and that means you create a new string and reallocate and copy every time, then you end up with the impression that you have somehow made an infinite loop, but it should be a quadratic function.
Switching the hogan buffer appending code to…
chunks.push(tiny_string);
… and ending with a …
output = chunks.join('');
… gets back down into the milliseconds range instead of the "so long I have no idea if it would ever complete, left running while I developed a work around and it didn't finish" range.
... which is __the__ problem I was referring to, because these two implementations have essentially become black boxes with different performance on differnt runtimes. Should all library writers detect runtime and choose the optimal one? I don't think so. They're far more likely to simply write `a+=b`, which is NOT quadratic without any knowledge of the underlying impl.
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.
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)...
My favorite one of these in JavaScript is building an array by unshifting onto it:
var array = [];
for (...) {
array.unshift(whatever);
}
jQuery (at least used to) do this all over the place, to disastrous results. IIRC, in fact, V8 has special optimizations that allow arrays to grow backwards if there's room in the heap, just because this is so common in JavaScript :(
(Solving this in your code is usually trivial, by the way: just replace unshift with push and use Array.reverse at the end.)
You'd be surprised. Adding 2 instructions to every array operation would probably kill your engine's relative SunSpider or V8 score. JS performance is extremely competitive.
Sure, I can believe it'd affect the score, but I can't believe anyone would actually care about it. It's not like Javascript was designed for performance to begin with.
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.
Interesting. I do wonder what pathological performance is like, though. I would imagine that you can design an access scenario that does pushes/pops and shifts/unshifts in the right order to cause it to keep shuffling elements back and forth within the storage (without reallocating) indefinitely even though the number of elements never grows beyond a set amount.
The pathological case is FIFO. If you store a FIFO queue inside devector, with n elements in the queue, memory usage bounds at 5n/3. This means that the total free space is 2n/3, of which half gets re-used everytime the elements shuffle. This means that after n/3 push_back/pop_front pairs n elements have to be moved. Which is still amortized constant, with an overhead of approximately 1.5 moves per operation.
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.
From looking over your README, when it needs new space on one end, it preserves half of the free space on the other, and requires at least 1/3rd of the size of the vector at the end that's being appended to (assuming >= 16). I didn't check to see how it balances space when the 1/2 free space it harvests from the other end is larger than the 1/3rd size it needs. But my assumption is that when it grows an end, it may end up with more free space at that end than at the other, right? If that's true, then deleting the added elements from that end and switching to appending to the other (until it has to shuffle) would presumably cause it to shuffle more often than a simple FIFO.
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)?
Actually, you are right, I was wrong about my assumption that FIFO is the worst case, and that 5n/2 is the space bound.
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:
Forgive me for not being on-point in a quick reply with my exact maths, but entering this model with n(0) = s(0) = 16 using Python and memoization to speed up the recursion reveals that a(x) / n(x) is exactly 1/2. So after n/2 appends n moves are needed, so 2 moves per operation. s(x) / n(x) turns out to be exactly 3, so 3n is the max space bound.
---
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.
Actually, after revisiting my model below, I found that it's completely wrong.
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.
I've been terrified of linked structures since I saw a video (I think it was here) from a C++ conference talking about how horrible their performance is.
Yep, and that used to be idiomatic, years and years ago when people still wrote their own linked lists. I'd be surprised if it isn't still the standard behavior for that data structure.
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. :(
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.
for(int i = 0; i < strlen(s); i++)
doSomething(s[i]);
strlen() searches for the terminating NUL byte and is thus O(n), which makes the loop quadratic.
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.
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
By "a long time" I mean rather more than an hour (maybe -- my memory grows dim).
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.
Its expected value will likely still be linear - since values are distributed among cells uniformly, and there ratio of empty cells to all cells is bounded from above (otherwise rebucketting occurs), expected position of the first nonempty cell is also close to the beginning. Calculating it is a good exercise, helpful Google keywords are "order statistics of discrete uniform distribution".
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.
79 comments
[ 3.2 ms ] story [ 181 ms ] threadIt'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.
HN discussion: https://news.ycombinator.com/item?id=6912474
http://beza1e1.tuxen.de/articles/accidentally_turing_complet...
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.
If your hash function works properly, and you are dynamically resizing your hash by a constant fraction whenever it gets too full, you can bound the probability of hash collisions above, and bound the number of expected hash collisions by a constant. As is standard in resized data structure, the resizing is individually O(n) with frequency O(1/n) for an amortized cost of O(1) per insert.
Put all of that together, and the amortized average cost of an insert into the hash is O(1). This is a well-known standard result, and is the reason why hashes are useful.
For what I've understood, average cost means average over all possible random inputs. So for specific set inputs, the cost can be larger than that.
Amortized cost means the average cost of the operation over any combination of inputs. So for specific set of inputs, the cost is the stated.
For hash table insertion, both the amortized and average cost can be O(1) with linked-list confliction resolution, but whereas average time of a lookup operation is O(1), amortized is larger (I don't know if there's analysis on this, but O(n) seems correct by gut-feeling).
Amortized analysis refers to determining the time-averaged running time for a sequence of operations.
Note that you are averaging over a sequence of operations, and not any combination of inputs. As that article goes on to explain, amortized analysis is the right thing to use for figuring out the total running time of a sequence of operations.
Let's be concrete. In the case of a dynamically resized hash, the bound on an individual hash insertion when the hashing function works is O(n) because you could be looking at the unlucky insertion that resized the hash. The amortized cost is O(1) because you get to spread that expensive resize over many individual operations. If you're building a hard real time system, you should focus on the O(n) and not use that data structure. If you just want to build a hash table, the O(1) is what matters.
What about the amortized cost of many random hash lookups with linked-list conflict resolution? The distribution of buckets with different numbers of items approximately follows a Poisson distribution. From that we can estimate the average number of comparisons. And find out that the amortized cost is on average O(1).
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.
Switching the hogan buffer appending code to…
… and ending with a … … gets back down into the milliseconds range instead of the "so long I have no idea if it would ever complete, left running while I developed a work around and it didn't finish" range.␄
† http://duktape.org/index.html
‡ http://twitter.github.io/hogan.js/
http://stackoverflow.com/questions/7299010/why-is-string-con...
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...
the obvious gotcha free solution is linear but requires two passes (i'm not sure thats a bad thing)...
(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:
Forgive me for not being on-point in a quick reply with my exact maths, but entering this model with n(0) = s(0) = 16 using Python and memoization to speed up the recursion reveals that a(x) / n(x) is exactly 1/2. So after n/2 appends n moves are needed, so 2 moves per operation. s(x) / n(x) turns out to be exactly 3, so 3n is the max space bound.---
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.
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.
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.
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.
By "a long time" I mean rather more than an hour (maybe -- my memory grows dim).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.
http://blog.willbenton.com/2008/11/rent-a-coder-hilarity/
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.