Fewer features in each release. More time to fix bugs, test, "get it right the first time".

It currently doesn't, but BSD's code could make the same guarantee, right? At the point where it recurses left and right, compare the length of the two sub-arrays. Sort the shorter one first via a recursive call, then take advantage of the tail recursion and sort the larger one by overwriting the current stack frame and jumping back to the top of the function. They already go halfway (taking advantage of the tail recursion); they just don't use any heuristic to choose which sub-array gets sorted via the recursive call. It's always the "left" side.

It looks like GNU actually allocates its custom stack *on the stack*. However, in the comments they claim their algorithm guarantees that the stack need only be as large as log(sort elements), so they allocate a stack that is (in theory) guaranteed to be big enough. You can check out the code here. I'm not sure what version of glibc that's from, but it looks similar to what I extracted from 2.10 a while back.

It should be noted that since both BSD and GNU versions rely on a stack (and neither chooses its pivot point randomly, so far as I know) they're both vulnerable to crafted data that's designed to cause the algorithm to exhaust its stack. It's possible GNU dynamically grows its custom stack when it nears the point of exhaustion, but I kind of doubt it.

Slasdot ate my less-than symbol. They short-circuit to insertion when N < 7.

They use the method described in Bentley & McIlroy's paper, which uses a "median of medians" for large arrays, a simple median of first/last/middle for mid-sized arrays and the mid-point for small arrays. See page 1255 here. No idea how effective that is. They also short-circuit to insertion sort when N 7 for a given sort window.

So your current salary is approximately 2x what you started at 10 years ago (i.e. 1.07^10)? Nice. I'm 15.5 years into my career since graduating with a M.S. If my salary 15 years ago is what I think it was (am having trouble remembering) then I'm averaging only 5%/year. It's possible that the yearly increase is steeper during the first 10 years than in the next 10. Then again, maybe I'm just consoling myself. :)

Agreed. It would be interesting to know the smallest number of crafted sort elements needed to cause BSD's qsort() to exceed a "normal" stack size, whatever that happens to be. If an array with that number of elements and a reasonable element size (probably sizeof(void*) since elements are almost always pointers) will always be larger than the largest system memory size then, in theory, we wouldn't need to worry about exceeding the available call stack.

It may be the case, though, that it is possible to fit a crafted sequence of keys into a reasonable amount of space that will cause BSD qsort() to exceed a "normal" stack size.

How many of those apps are simply re-branded versions of some core you wrote?

All of them. The company couldn't exist if we had to code up a unique app for every customer. My point is that the fact of there being "lots of apps in the store" doesn't mean the number of app "producers" is correspondingly large. I thought I made that clear when I said, "it's not quite a 1-1 from app to company".

This is just one data point, but I recently compared the BSD and GNU qsort() code. Built both with LLVM (on a Mac), tried both -O2 and -O3, and did some crude benchmarking. IIRC the BSD code was slightly more efficient, not to mention drastically simpler. BSD basically uses the Bentley & McIlroy code from "Engineering a Sort Function" with a few small optimizations to make it more adaptive (and exploit the fact that the algorithm is tail-recursive). So the BSD version is still recursive, whereas GNU is non-recursive but manages its own stack.

Yes. I imagine the skill set for low-level video game testers is pretty minimal, and they have a built-in advantage because so many (IMO foolish) people are disproportionately interested in "video game testing" compared to other things they could be doing with their time. I live in Austin, by the way. You can easily get $10 at many high-end fast food places (e.g. Rudy's BBQ). You can undoubtedly make more than $16/hr if you can successfully transition from "video game tester" to "QA Engineer" and get out of the gaming industry. But you'd have to be more than a random-button-pusher. Writing test plans, QA automation, etc.

That changes the equation somewhat, I agree. Some thoughts:

1. Moving cross-country to take a $16/hr job when you have no savings is somewhat risky, as your friend found out. How much could he have made in CA if he hadn't moved? How much did the initial move from California to Texas cost? If it cost $1000 to move one-way and he was able to earn $3/hr more (after taxes) than in CA then he would have recouped the cost of his move (round-trip) in 4 months time.
2. If he was able to earn more in Texas than in CA then I'm going to assume the job prospects for his skill set were superior in Texas. So even after he lost the initial job he was still better positioned in Texas than in CA.
3. The person making $16/hr probably doesn't need a 20ft U-Haul trailer. If he didn't have furniture (or was willing to sell and re-buy after the move) and had a reasonable car then 1750 miles / 20mpg * $2/gallon = $175. That's a much cheaper move.

I love reading stories like this. I'd love it if a concerted effort were made to further optimize various non-FP glibc methods as well. I assume they're already fairly well optimized, but I would be shocked if there weren't still some gains to be made. +10 internets to you, Mr./Ms. Poyarekar.

That's assuming an ability to move in either direction. Companies will not pay for relocation costs. If you don't have the money to move, you're so out of luck.

That's why you budget money for a future move and/or rent instead of buy. A 20ft U-Haul truck from Austin to SanFran is $850, plus gas. Loaded it gets 8mpg, and the trip is 1750 miles. So figure $450 for gas, for a total of $1300. Say your buddy gets an offer for $100k/year back in California. He could counter with "$95k/year + $1500 to relocate." The employer would recoup its cost within 4 months. Most would accept that counter-offer. Sucks to give up base salary, but if the alternative is "no job at all and you're stuck in Texas when you don't want to be" then it starts to look more attractive.

1. Hedge funds/billionaires being able to borrow at the Fed rate and at much higher margins than us peons (95% vs 50% for the rest of us) pumped the money into the stock markets.

Which I'm not sad about, since my savings is mainly in U.S. equities.

2. All the money floating around was used by corporations to do stock buybacks - not because their businesses were worth investing in (contrary to the myth taught in Finance classes and spewed by corporate PR departments) but because it allowed the CEOs and billionaires to get even richer.

And anyone else who owns stock in those companies. Like me. And I'm not even a millionaire.

3. 1 & 2 were all done at our expense because it weakened the dollar - making consumer goods more expensive; while our wages haven't gone up.

The dollar isn't especially weak. Here is a graph of its value vs. a basket of trade-weighted currencies. You'll notice it actually got significantly stronger during the recession. Here is a graph of CPI. Post-recession is has increased at about the same rate as pre-recession. I can't speak for everyone else, but my wages have gone up.

In the meantime, we are working longer and longer hours because in order to keep profits up, companies have been laying people off and making their current workforce work harder and longer.

Not working longer hours here. Here is a graph of average hours worked per week for employed persons. Seems like the current level is roughly the same as the level prior to the recession.

A plan that was supposed to help us out and get employment back to 2007 levels has horribly failed.

In 2007 U-3 unemployment ranged from 4.4% (March) to 5.0% (December). Current unemployment (November 2014) is 5.8%. The rate of decrease since peak unemployment (10.0% in October 2009) has been fairly linear at about 0.069% per month. At that rate we should once again be at "2007 levels" (i.e. 5.0%) in October 2015.