5 ms·
I hear this so much, but it's just wrong. Here's a "interview style" question which is hopefully practical enough to show why: Let's say you have a giant in-m
by ajross 15y ago
I hear this so much, but it's just wrong. Here's a "interview style" question which is hopefully practical enough to show why:
Let's say you have a giant in-memory balanced binary tree (for your data store, maybe) with mean depth of ... 27, say. And you're deployed on a machine with 4 DRAM channels populated with (for the sake of argument) 7-7-7-23 DDR3 memory. Give me a ballpark estimate for how many reads per second you can achieve from that tree.
My experience is that virtually no one can answer this question well, and most programmer's intuition is wildly off (they think it's much faster than it is). And even the ones who get it mostly right usually just use "100 cycles" as their assumption of DRAM latency and get tripped up on the subtleties (like the interaction with the number of channels vs. precharge overlap; or the already-active row latency for sequential access which this question doesn't cover).
Reading this paper will teach you how to answer that question from first principles. 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.
(edit: A bonus followup question -- hopefully just as practical -- would be: "So maybe binary trees aren't great. Given a node data size of N, what is the most appropriate fanout to use in a B tree implementation?". This pulls knowledge of caching architectures into the mix.)
- klochner 15y agoSurely 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.
- ajross 15y agoI 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.
- efuquen 15y agoI 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.
- cube13 15y agoGoogle. 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.
- thwarted 15y agoMore 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.
- sliverstorm 15y agoThat 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.
- cube13 15y agoI 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.
- lolcraft 15y ago
- sbov 15y agoWhen 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.
- ajross 15y agoI 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.
- Deestan 15y agoNo. I already have a ton of other vegetables on my plate. Lambda calculus, compiler architecture, Haskell arrows.
- illumen 15y agoOther 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>
- btilly 15y agoSometimes 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.
- cbsmith 15y agoCache 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.
- Retric 15y agoThat'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.
- ajross 15y agoOK, 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?
- Retric 15y agoA 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 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.
- balloot 15y agoThat 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.
- haberman 15y ago> 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.
- obtu 15y agoHe 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.