I'm sure they're asking about this in interviews now. My experience with Google interviews was that the interviewers were very keen on proving that they knew more theoretical CS than I did vs talking about what the actual work would require or entail.
History of massive-scale sorting experiments at Google
31–40 of 82 posts
Re: History of massive-scale sorting experiments at Google
#32I'm sure they're asking about this in interviews now. My experience with Google interviews was that the interviewers were very keen on proving that they knew more theoretical CS than I did vs talking about what the actual work would require or entail.
I worked at Google, and performed quite a few interviews. At least at that time, the interviewer had no idea where in the company the software engineer would go. The people who got hired would go into a pool, and the managers who needed staff would then horse-trade for them. They needed to hire people who could be plugged in to tons of different positions, including some that genuinely had tough problems where if the…
Re: History of massive-scale sorting experiments at Google
#33Earlier quoted context omitted.
It had to feel fucking amazing to be an engineer that was part of that at the time. To know (even if it was publicly unknown) that you were able to so massively destroy a record which still stands 4 years later.
Part of the magic of working at Google is there are lots of projects that can make you feel that way.
Re: History of massive-scale sorting experiments at Google
#34Note that this sort [in 2012] was 500 times larger than the GraySort large-scale requirement and twice as fast in throughput as the **current 2015** official GraySort winner. (emphasis mine)
Re: History of massive-scale sorting experiments at Google
#35Re: History of massive-scale sorting experiments at Google
#36Earlier quoted context omitted.
You may well be asked how a distributed sort would work in principle, and be asked to code a small part of it. Any reasonable answer that shows you can think on your feet would be evidence in favor of hiring. It sounds like you didn't get hired, and I'm sorry about that. Interviewers' preferences are of course diverse, but for at least the last 5 years, probably 10, Google interviews favor practical solutions to prob…
As a datapoint, a while back I was asked (for a G interview within the last 10 years) to code an RB tree from start to finish. I'll admit I was a little miffed at how distanced this seemed from anything I would potentially do; I was not interviewing for a high theory/deep algorithms group. That being said, in my other experience with a G interview, the entire process was much more mundane and as expected. For the rec…
Implementing a well known data structure is pretty far removed from `deep algorithms' and `high theory'.
Re: History of massive-scale sorting experiments at Google
#37Apache Spark completed a 1PB sort on 190 EC2 (i2.8xlarge) instances in 234 mins. Google did their 2011 1PB sort on 8000 computers in 33 minutes.
Moore's law is at work here and the results aren't very comparable but it would be interesting to see a head-to-head test on similarly speced clusters.
[1] https://databricks.com/blog/2014/10/10/spark-petabyte-sort.h...
Re: History of massive-scale sorting experiments at Google
#38To each their own. While impressive I do not find it inspiring. Instead, working on strong AI is, in my mind, the ultimate challenge. Far more amazing by any measure than anything we have acomplished so far.
So is working on antigravity, free energy, and backwards time travel, but people don't do that because they are no reasonable approaches we can try.
Glorifying "AI AI AI" is silly because — there are no approaches we can try. Sure, we can identify ten million images per second, but none of that involves the least bit of "thinking."
Re: History of massive-scale sorting experiments at Google
#39Earlier quoted context omitted.
I worked at Google, and performed quite a few interviews. At least at that time, the interviewer had no idea where in the company the software engineer would go. The people who got hired would go into a pool, and the managers who needed staff would then horse-trade for them. They needed to hire people who could be plugged in to tons of different positions, including some that genuinely had tough problems where if the…
> genuinely had tough problems where if they accidentally did something in O(N^2), their half-day compute job would suddenly literally take centuries to complete. Yes, but this has almost zero bearing on the actual interview. Being able to avoid this in real life means that you measure twice and cut once, you pay attention, and you ask for help and training. Being able to do something similar with dynamic programming…
I mean, heck, something like this? They interview multiple magnitudes of people necessary for this kind of job. I respect it as a hedge, but it probably also takes people out of the industry who could do more vital work someplace else.
Re: History of massive-scale sorting experiments at Google
#40I'm sure they're asking about this in interviews now. My experience with Google interviews was that the interviewers were very keen on proving that they knew more theoretical CS than I did vs talking about what the actual work would require or entail.
I worked at Google, and performed quite a few interviews. At least at that time, the interviewer had no idea where in the company the software engineer would go. The people who got hired would go into a pool, and the managers who needed staff would then horse-trade for them. They needed to hire people who could be plugged in to tons of different positions, including some that genuinely had tough problems where if the…
Fun facts: those are commonly known as "vbytes." They are the slowest kind of variable width integer encoding. The simplest (naive, and generally considered "wrong") implementations of variable-width-by-continuation-bits uses 10 bytes maximum. A proper implementation uses 9 bytes maximum.
There's actually no reason to ever use 10 bytes in this encoding. If you use 10 bytes, that means your last byte only holds one bit of actual user data. That's not very cool. But, your next-to-last byte holds seven bits of user data and one bit of metadata. We can easily say "if we're at the next to last byte, don't use metadata, just use all the bits we need." All you have to do is say "if we are currently at 9 bytes, don't use a 10th byte, just use this 9th byte directly." bam. Your 9th byte now has 8 bits of user data and you don't roll over a useless 10th byte with one bit of data.
The "slide all continuation bits into the first byte" sounds like a trick, but it's really using a TLV encoding where the first byte just holds a number between 1 and 8, so the entire integer+metadata is now [1 type byte][1 to 8 user data] = 2 to 9 bytes total. Using this scheme also kills any "1 byte, standalone, variable width integer" capability (unless you're storing partial values in the first T/L byte, but then that limits you to a much lower max value for one byte).