Hacker News Reader

Sometimes the job of an interview question is to make it clear to the interviewee that this is not, after all, somewhere they want to work.

That would be my reaction to those interview questions.

As for the follow-up question, my response would be to ask why you are optimizing your B tree for a specific architecture instead of using a cache-oblivious B tree. (Yes, I can think of several reasons why not to. But if the interviewer is asking me BS questions, I want to know whether their knowledge is similarly good.)

Of course in practice I'm generally happy to use BerkeleyDB - the B tree has never been a performance bottleneck for me except when it involved disk latency. And at that point a more fundamental reorganization of algorithms becomes necessary.

Cache wasn't mentioned in the question... there might be no cache at all. ;-)

Cache oblivious B-trees aren't exactly oblivious to how DRAM behaves, and sometimes their operation actually can be counter to what works best in DRAM (though I agree that generally they tend to do better than data structures that are "oblivious" in a very different sense).

But let's ignore that for a moment. Okay, you aren't using BerkeleyDB, MySQL, or any other of the common B-trees out there, but instead you've got your hands on a cache oblivious b-tree. What is the approximate optimal fanout rate and what is the approximate number of reads per second you can achieve with the 7-7-7-23 DDR3 memory (or memory of your choice that is commonly found in modern systems)?

The question isn't really about knowing the specifics of a particular memory infrastructure. It's about understanding the cost of going to memory, which is increasingly as important as understanding disk latency (you know how "disk is the new tape"? well, RAM is the new "disk").

Interestingly, a lot of databases these days are CPU bound , particularly when working with big data, but even in other cases. They aren't really CPU bound, it just looks like that because of how accounting is done. When you poke under the covers, you see the CPU pipelines are comparatively idle because the CPU's are all tied up accessing memory.

Particularly if you are using AWS or other virtualization services, most web applications these days rely on servicing a majority of their requests entirely from memory. Being able to understand the performance characteristics of memory at least within an order of magnitude becomes increasingly important, because the average rate that you can service from memory becomes a critical metric for the scaling of your services.

It's more than even that though. As concurrency becomes increasingly important, locks and atomics become central to a lot of work. The last few iterations of Moore's law have changed the principles of how locks & CAS impact performance. It used to be that locks were bad, because you often burned up CPU going down to the kernel, but more than that because suddenly you are wasting CPU while you wait for something else to complete. CAS allowed you to largely sidestep all that CPU wasting and you're a happy man. Then CAS got integrated in to locks so that locks only really sucked when you had contention, but now... The real expensive cost of a lock these days is the memory fence put around it. CAS is better because the fence is scoped to only the object being swapped, but even that can be horribly expensive if there is contention on the object. Having a clear understanding of just how big that cost is relative to burning some more CPU, wasting some RAM, or even changing the constraints for your code, can be very important.

Trust me. This stuff really matters for any context where performance matters, and it is only going to get more important in the coming years. Memory has pretty much already trumped CPU in terms of its importance for most applications, and the number of cases for which it is more important than disk is growing at a rapid rate.

I believe you.

However I've spent most of my life working within scripting languages. And the same is probably true of most programmers in the startup world.

If you're able to get away with using a scripting language, then your problems had better not be performance critical, because your swiss army knife of choice really sucks as a saw...

Yeah, web apps mostly get to ignore stuff like this until they're really big. But then sometimes you're a startup like Akiban Technologies and this is what you do.

First, the notion that using a scripting language means that performance isn't an issue is a canard. It ought to mean your revenue isn't directly correlated to performance, but that's about it. Indeed, if you are using a scripting language, the odds are more important that you understand the trade offs, as your lack of low level options means you need to make smart choices about high level options.

Second, very few startups don't end up making decisions about performance even in the early days. What? You're using a NoSQL store? Is that because you just hate yourself or because you thought it'd be more efficient/scale better than an RDBMS? Why aren't you just storing it all in memory? Wait, you can run out of that? just let it swap then! Actually, why not just store all the data in a flat file? You don't even need to sort it, you can just scan through it whenever you need to, because performance doesn't matter. Why are you using an associative array there? Do you care about having efficient lookups based on a key or something?

You see my point.

I get that some people are playing around in a segment of startup land where programming isn't really that important, but presumably your long term plan isn't for every startup you participate in to never go anywhere. What if you are a success? Do you still want to be on the technical side when you've now got a team of developers and a serious customer base? If not, that's fine and likely a great career plan, but you aren't a programmer in the professional sense (which is what the paper is referring to). If you are planning on staying on that side, either learn this stuff or expect to be cast aside and not grow with the organization, because you aren't ready for the bigger world you'd now be playing in.

To be clear here, I'm not suggesting you'd have to pick up a systems programming language. Heck, when I started my career two decades ago, when CPU's were a lot slower and interpreters weren't as efficient as they are now, there was already this notion that "oh, I'm working in an interpreted language which provides a layer of abstraction so I don't need to know how computers work". I made a good start of my career (and met a lot of people who had been doing so for quite some time) essentially kicking those guys out of their jobs because it turned out doing scripting with an understanding of the computing consequences of your choices is applicable in a very broad set of situations, but scripting without that understanding is barely more useful than knowing how to use Excel.

High level languages actually can kick quite a bit of butt in performance critical situations, because they let you focus on the bigger picture of how you are executing, where the bigger performance wins can be had (I've seen "scripting languages" winning performance bake-offs for exactly this reason), but you have to know what the heck you are doing. People often make the mistake of thinking this won't matter. They tend to have very short careers.

Within the limitations of a scripting language, of course you try to get the best performance that you can.

However in general within a scripting language you are not trying to optimize things at the CPU cache level. You're worried about overall efficiency of your algorithms, avoiding disk, identifying performance bottlenecks, etc. But the pervasive use of hashes everywhere and memory hungry data structures makes careful use of CPU caches pretty much a lost cause.

Furthermore the language does so much behind your back that an analysis of performance from first principles is very unlikely to be right. Instead you need to benchmark.

That's a ridiculously contrived example, in the real world binary tree's are generally terrible data-structures. But, for most programmers most of the time even knowing what data structure is being used ahead of time is a waste of time.

PS: Wait, so your hand rolling your own caching system. That's nice, your fired.

OK, let's roll with that: you have a better idea for an in-memory data structure with better performance than a RB- or AVL- tree? How much faster? How many DRAM cycles does it save?

You can't defend your point without understanding the hardware works, you know. Either it's a "terrible data structure" for DRAM stores (and you know why) or "this is all a waste of time" and it's not a terrible data structure by definition. Which is it?

A Hybrid data structure. How many DRAM cycles does it save? Depends on your data and access patterns, 10-20 is reasonable, but it also saves processing time etc.

EX: Let's say you want to store 1/2 to 100 million GUID's. They should have a random distribution so you don't have to go crazy just start with a lookup table for the first 16 bits (sized to fit into L2 cache) and a radix tree on the leaf nodes. http://en.wikipedia.org/wiki/Radix_tree or a AVL-tree or whatever you want it's just not that important because these small trees are unlikely be cached. You may want to use a mid range of lockup tables to cut down on DRAM round trips, but again that's the type of micro optimization that starts to get really specific to your usage patterns and the amount of memory on your system etc.

But wait, what if your using time-stamps? The first N digits are going to be the same right? Again, knowing the DRAM timings is pointless verify its in the range you want, mask some middle bits, use that as an index... etc. Or, if it's a pure lookup and it's ok to give up ordering you can flip the bit order to have a fairly random distribution. (Again a micro optimization based on data usage patterns but it may help out.)

And, here is the thing if your storing the data on a HDD the same idea is still useful, just use a larger index in RAM. The important things is relative latency's and storage space not specific timings.

PS: Still, this assumes speed is really important. Generally speaking there are far more important things to worry about like keeping all your data in RAM in the first place, space efficiency can be more important than access patterns. And you might be better creating a batch of query's and ordering them to be more efficient vs changing how your data is stored.

"you have a better idea for an in-memory data structure"

The problem with this question is (and your original example) is it entirely contrived. A better in-memory data structure for what? String indexings? Integers keys? Complex objects? Metric data? Region Data? What is your query load? Range queries? Exact queries? Substring queries? K-edits queries? Nearest Neighbors? etc....

Before worrying about DRAM performance on the particular machine you may be running your code on for a year or two in production you need to answer those questions. The performance of your system will depend far more on your understanding of the work load (read vs write), object type and query types than on the data structures understanding of the DRAM. That is the last optimisation you make, after you have done everything else because it is machine specific.

That logic makes no sense to me. By that definition any focused question is "entirely contrived". So I'll throw it out to you: pick one. Come up with any large in-memory data store (any structure, any stored data, any indexing) and give me an answer about its performance that doesn't require knowledge of how DRAM works.

(Edit: signing off this ridiculous flame war. We're now in full circular logic mode: examples showing the utility of DRAM knowledge are contrived because DRAM knowlege is never useful. Sigh. I'll just point out that, because I know how this stuff works, you are wrong. You can do your jobs without being a good hacker, but you'll never be a great hacker if you don't know how your machinery works.)

To a first approximation, all focused questions that rely on knowing DRAM timing details are entirely contrived. That's because almost no programmers need to focus on performance on hardware that specific, outside of people targeting mass produced identical hardware, like consoles.

Trying to predict performance from first principles is a mug's game in any case; there will be things you didn't expect. It's far better to measure.

Wouldn't you rather have at least an approximate map showing the more swampy areas on your random walk up Performance Mountain (or is it down into Performance Valley? The sight of all these top-rooted trees is confusing me)?

I'm criticizing basing your architectural decisions on things as low-level as specific DRAM timings, unless perhaps you're targeting a very focused, extremely mass market niche, like a console.

I never said that one must be ignorant of factors that can affect performance when measuring. Rather, don't try and predict from first principles without measuring.

So, by this logic, when writing code gor a variety of CPU/memory/storage/GPU platforms, there really isn't much point in worrying about performance at all?

Good luck with that interview at Oracle/Google/Facebook/Twitter/Activision/Adobe/Microsoft/AnyoneWhoKnowsAnythingAboutSoftware....

I never said there's not much point worrying about performance. What I said is that working from first principles at the level of detail of DRAM refresh timings is likely to be less productive than measuring different approaches based on higher-level understanding, because there will likely be more low-level details than you expected. But with higher level stuff, like the basics of CPU caching / associativity / risks of cache sloshing etc., you can make some reasonable design decisions - as long as you measure and experiment, continuously, throughout the process.

The window within which caching effects occur varies from machine to machine - specifically, certain access patterns fall off a cliff once you go beyond the window - but with appropriate design, you can take reliable advantage of caching behaviour without needing to target a specific cache size.

I don't think the question was looking for a precise answer, but rather an approximate one. As he said, most programmers don't even get in the ballpark, and you'll note his question didn't mention cache or cache size. In fact, the way the question is phrased, you could answer for a system that had no cache whatsoever if you wanted to, though I'd go with some common cache architecture.

When I run across a problem like the above, surely it's worth a few hours of my time, at that time. If it becomes a habitual problem, I no longer have to spend a few hours of my time.

I think I did - 8 years ago. The problem isn't that I'm lazy, it's that if I have no reason to use something for a long enough period of time, I tend to forget it. Maybe you remember everything you read forever?

There's already a plethora of information that is worth a few hours of my time - the problem is there isn't enough hours in the day. I don't want to spend them on things I'll not use and soon forget.

I certainly don't remember things forever. But I generally find that the hard concepts stick around vestigially. Having read this (admittedly weighty) paper once, you'll find that going back in 4 years to check something isn't nearly so bad.

Really, read it. It's good for you. Like vegetables.

No. I already have a ton of other vegetables on my plate. Lambda calculus, compiler architecture, Haskell arrows.

Other things like cache coherency, number and type of cores, other things running on the system, compression or reduction based on properties of the data all have an effect on what is possible. Not to mention weird things like some specialised FPGA, GPU, network card, or even SSD that might have DMA'd the memory. Various bus types depending on the cpus can also have a massive effect - not to mention memory access patterns your code might use. What about the OS level abilities that you're allowed to use? Is ring 0, or setting the affinity of processes, or enabling Turbo mode allowed? Maybe you don't give a shit about the data structure at all, and are just searching for a word with hyper-optimised grep will win. Then taking advantage of that, you can cheat and get something even faster. As you can see, even getting into the level of detail you mention, there is still a shit-load of extra details that might be needed to take full advantage of the hardware.

</arguing>

   Surely that's worth a few hours of your time. At the very
   least it's worth more than arguing on the internet about 
   how you don't need to know it.

That's a great point.

Regarding your interview question, the kind of optimization you're getting into isn't something 99% of 'programmers' will ever touch.

I suspect you can spin the demographics in lots of directions. But I'd hope that a far higher percentage of startup technical founders (the audience to which the comment was directed) would need to do non-trivial performance estimation in the course of building their products.

I think the point is that they don't.

Tell me any of the sites you visit in which this knowledge would be critical to deploying whatever service/product they're offering? I would imagine it would be pretty close to 0.

Google. Amazon. Bing. Twitter. Facebook.

When you start hitting massive amounts of traffic, these kinds of optimizations can save you a TON of money in equipment and bandwidth.

More likely for people on that path, there's bigger wins from paying down technical debt that exists at a higher level than by trying to optimize your code's memory access patterns.

That depends. Money spent on hardware buys you linear performance improvements. Algorithmic improvements can buy you exponential performance improvements.

There is most certainly a point where money spent on hardware gives a better return, but all the hardware in the world couldn't net you acceptable runtimes using bubblesort on colossal datasets.

I agree completely. Frontend optimizations can probably give a lot more in the short term than these kinds of backend optimizations.

Unfortunately, even if it's paying down technical debt, if you're trying to squeeze out more cycles with your low-level code, a lot of the time it's issues on the algorithm level. When refactoring there, these kinds of optimizations should always be at the back of your head, even if it's just to explain why moving the for loop up 5 lines gave the function a 2% performance boost.

Facebook was implemented in PHP, and still is (though now compiled, whatever). Google was, at a time, implemented in Python. Twitter was built on Rails, probably even ran on MRI. Maybe they switched to Java, who knows. Hardly hardcore-optimizable languages.

Not to mention that premature optimization may be bad, but even when you need it, it's better to just write a few algorithms and test them against real data.

The point isn't so much to think about optimizing assembler, but rather making higher-level algorithmic choices that mesh with your platform. Even if you don't sift through the Ruby bytecode, you can still apply some knowledge about what kind of data structure will be better in which kind of situation.

For example, if posed with the question presented here, if you realize it will not be as fast as you might hope, maybe you can make the choice to build a data structure with much less depth- maybe you can fit it all in a hash table?- and achieve huge performance wins without once touching assembler. (With a 27-deep tree, you need to make 27 reads from memory to find your data; reducing the depth reduces the required reads)

(I am not a computer scientist, and I am not an expert in algorithms, but hopefully I'm not too far off here.)

Last I checked, PHP, Python and Ruby were implemented on computers with DRAM memories. All that analysis applies to them too. "Following a reference" is a memory load (or several) in all languages.

You seriously aren't willing to admit that your question has zero relevance to someone working in PHP?

The entire point of coding in a language like PHP is that you don't think about the low level stuff. And even if you did take the time to truly understand the source of PHP and made some fabulous optimization, they could change implementation details in a future release and break what you did.

Bottom line is that your interview question has almost no correlation with whether someone would be a good PHP developer. You might as well ask what the capital of Macedonia is as that is just as good of a screen for potential applicants.

As far as I know, Google was never implemented in Python. However Python is one of the three major languages at Google. (Mostly used for non-performance critical scripting stuff. If they care about performance it is in C++ or Java.)

The others are correct.

Again, it's a very specialized gig. Each of those companies probably has a small handful of people who work on optimization and could answer the question we're talking about here. But the vast majority of employees in these companies work in higher level languages and never have to think about the specifics of memory management at all.

That interview question would be completely irrelevant for 99.9% of software jobs.

Nobody is denying that this stuff is essential for some very specialized software teams. But the claim that it's something every software engineer needs to know is utterly ridiculous.

> Give me a ballpark estimate for how many reads per second you can achieve from that tree.

Isn't that going to depend on a heck of a lot more than just the RAM latency? Like, for example, how much locality the data has and how big the caches are?

I love this low-level stuff, but I think it's pretty hard to estimate performance of anything from first principles on today's highly complex architectures. There is just too much interplay of confounding factors.

He mentioned the data structure is large, so it's a safe assumption to say the cpu caches won't be useful except maybe for the very top of the tree, and that there is no locality when traversing a tree path.