9 ms·
What every programmer should know about memory, Part 1
- ajross 15y agoThese are old, but great. Drepper's history with glibc is a little checkered, but his whitepapers (there's an equally great one on the NPTL work from back when that was being done in glibc) are gold. Understanding the DRAM cycle is critical to performance tuning in modern code, and my experience is that virtually no application developers know how it works.
- klochner 15y agoVery useful information, but this is way overkill for what "every programmer should know". Every programmer should have a basic understanding of latencies. This is slightly out of date but still gives an idea of relative latencies: http://norvig.com/21-days.html#answers http://norvig.com/21-days.html#answers
- prophetjohn 15y agoExactly. This is a significant portion of a graduate-level computer architecture course. You average Rails/Node/etc. programmer doesn't need to know half of what's covered during the 3 weeks of an undergraduate architecture course that's devoted to the memory system. How many programmers in 2012 are ever even going to need to cache-optimize their code? 25%? 10%? The content is fascinating, but the title is pretty wrong.
- sho_hn 15y agoThe title isn't need, it's should. Both are debatable of course, but I'd argue that should is a lot more defensible: Abstractions are leaky, and even if you can get by without knowing what's going on down there, you'll at the very least sharpen your mind and be more surefooted if you do. What you're saying is a bit like the but I'll never need math in life argument. You're going to say that math is a lot more fundamental to existence then computer memory is of course, and that's true, but if you're looking at just computers, the way the memory system works is a fundamental part of the whole not entirely unlike math is to understanding nature. If you really want to know what you're dealing with and make sure you're not limiting yourself, you want to be inquisitive and go there. Basically, I don't really get why the gut reaction to these sort of things (especially if they actually have meat; there's of course a lot of crummy pretenders) is so often to declare them pointless. Yes, you need to filter your information intake, but still, better err on the side of knowing too much.
- prophetjohn 15y agoNo one is declaring this information pointless, but it's certainly a lot less relevant to Every Programmer than it was when this was written in 2007. I've actually got an okay understanding of this stuff, but the number of times that I've split for(int i = 0; i < 10; i++) { j += i; k += i; l += i; } into for(int i = 0; i < 10; i++) j += i; for(int i = 0; i < 10; i++) k += i; for(int i = 0; i < 10; i++) l += i; to reduce cache misses is very small because with today's hardware, it very often just doesn't matter. Obviously there are many programmers whose primary job is to do this, because they need every clock cycle they can squeeze out of the thing. They're just not representative of Every Programmer.
- vilya 15y agoI'd argue it's more important now than when the white paper was first written. Where processor speed or memory size used to be the bottleneck, increasingly these days it's memory bandwidth instead, so managing that effectively is key to writing high performance programs.
- cbsmith 15y agoI was going to say something almost precisely like this. The main thing I was going to add is that it is both memory bandwidth and latency that have become important bottlenecks, and often the latter is more important. You know how people were saying "disk is the new tape"? Guess what the new disk is? RAM. Much as with disk latencies, RAM latencies haven't really improved that much over the last decade or so, though memory bandwidth and CPU power have. Guess what that means? ;-) ..but you can only know this if you understand what's going on underneath the hood. So if you don't, no need to worry; you won't even know when the moment of your utter irrelevance arrives.
- garenp 15y agoMy typical response to the "I'll never need to know X" argument is similar, which is that having as broad and diverse understanding of a system as possible gives you imagination. Without imagination, you will not be able to solve certain problems, not know where to even look when some arise, and at worse be totally unaware that better solutions exist. That said, the OP's context is that of an "interview style" question which raises mental red flags for me. It's a common problem for interviewers to base their assessment of a candidate based on whether or not the interviewee has the same subset of knowledge that they do. In that case, I'd be quick to point out that: * knowledge != intelligence * knowledge != capability * knowledge != skills * correlation != causation
- romaniv 15y agoThey don't need to cache-optimize, but knowing how stuff really works can help prevent some pathological cases of premature optimization in higher-level languages. I've read most of this during my undegrad OS course, and found it absolutely fascinating.
- sho_hn 15y agoThat's an awesome point I really wish I had made myself, so I'll just shamelessly rehash it to drive it home: Knowing how the system actually works down to a low level can help you avoid inadvertently writing code that will perform badly, even if you're dealing with code isn't otherwise required to perform above "reasonable" and thus doesn't call for low-level tuning. Let's take database queries as an example: Knowing something about how the database is implemented will help you avoid writing queries that are pathologically slow, even if the queries you need to write aren't critical path enough to benefit from going to great length to tune them to the implementation.
- ajross 15y agoI 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 ago
- binarycrusader 15y agoIf you work in the game programming or systems programming fields, then definitely. Look at some of the presentations that developers made at GDCONF this past year or other years where they talk about the importance of using structures of arrays instead of arrays of structures. In brief (and greatly simplified) you may be able to fit an entire array into the processor cache and iterate over it quickly, since accessing each element of the array would only potentially bring in a pointer address. Whereas accessing an array of structures would cause the cache to be blown as each large structure attempted to be brought into cache and didn't quite fit. Here's one of the presentations: http://www.research.scea.com/research/pdfs/gdc2006_kokkevis_vangelis_physics.pdf
- vibrunazo 15y ago> Every programmer should have a basic understanding of latencies. Why exactly? Aren't you making the same mistake of the author and confusing "every programmer" with "every low level programmer whose work is highly dependent on speed optimization"? Which, from my understanding are the minority of us. I don't even know how the APIs I use are implemented, let alone know how much "fetching from L2 cache" they're making. But of course, I know very little about hardware. So I could be very mistaken. I would love to be proven wrong.
- dgant 15y agoThere are very few software environments where the cost difference of "Read 1MB sequentially from disk" versus "Read 1MB sequentially from memory" is irrelevant.
- prophetjohn 15y agoIf you're having problems with page faulting, you really just need to use less memory, not necessarily use it more intelligently. If you're programming so poorly that you're blowing through all the available system memory, the problem is likely a little more simple than you not knowing how paging, TLB, etc. work. Either way, since the disk is so slow, virtual memory and paging are handled by the OS, not the hardware; so there's a lot less that the programmer can specifically control once you get that far down the memory hierarchy, as opposed to (say) avoiding cache misses.
- btilly 15y agoNot true! A programmer who is aware of the latency issues around disks can figure out how to move data out of memory into files, and how to change algorithms to arrange for sequential access to data. One who is not aware has no way to figure out how to stop the month-end data processing run taking five days. (That is a real world example.)
- prophetjohn 15y agoTo avoid disk latency, you're moving data out of memory and onto disk? That's essentially a coping mechanism for having stuff taking up space in memory that doesn't need to be in memory. Knowing how and when to do that is useful, but doesn't require a lot of knowledge of the memory hierarchy beyond "the disk is incredibly freaking slower than memory." edit: and I just realized I'm in the subthread about knowing about latencies being important, not the subthread about knowing the entire contents of the linked paper being important, so yes, I think we're agreeing.
- sho_hn 15y agoIf you want to read something more approachable that can serve as a gateway to this, I highly recommend Jon Stokes' Inside the Machine. It goes over microprocessor architecture in a very approachable way, and contains a good chapter on the memory/cache hierarchy that is sort of the light version of a good chunk of Drepper's paper, or at least will be a big help in making sense of it. If you've never been close to the metal, or you want to catch up on newer developments, consider checking it out. Also, here's Drepper's paper compiled into a single PDF, which I think was edited a little later than the LWN publication and might have had some minor errata fixes: http://www.akkadia.org/drepper/cpumemory.pdf http://www.akkadia.org/drepper/cpumemory.pdf
- wmf 15y agoAs much as I liked Stokes's articles in Ars, I think programmers should probably skip Inside the Machine and go straight to Hennessy and Patterson. Inside the Machine is loaded with analogies that I find annoyingly distracting; I'd rather learn how a computer actually works than learn an analogy about how it works.
- asciimo 15y agoThis is perfect because I had forgotten everything I had learned about memory.
- rtkwe 15y agohttp://www.scribd.com/doc/92111472 http://www.scribd.com/doc/92111472 I'll just leave this here, PDF version for anyone who doesn't want to mess with the webpage reformatting.
- rtkwe 15y agohttp://www.scribd.com/doc/92111472 http://www.scribd.com/doc/92111472 I'll just leave this here, PDF version for anyone who doesn't want to mess with the webpage reformatting.
- intractable 15y agoAhh, the "What every programmer should know about X" articles. So, Ulrich Drepper thinks everyone should know about the intricacies of DRAM refreshing. Zed Shaw thinks we should all know statistics. Some other schmoe thinks we should know about SEO. Et cetera. Posts like these should be titled "I worked hard and feel good about myself for knowing X, therefore everyone should know it." It is blisteringly stupid. Every programmer needs to know WHAT THEY NEED TO KNOW. Nobody can know everything. Why don't we all just learn what we need, build the things which interest us, and stop telling others what THEY need? Having said that... interesting stuff. Just needs a title change.
- oakenshield 15y agoIt's on LWN. 90% of programmers who go there really do need to know memory in the detail Drepper talks about. I see your point though - I fully expected the title to be linkbait to a hastily written article. This article, however, is the real deal. Drepper's site (http://www.akkadia.org/drepper/ http://www.akkadia.org/drepper/) won't win any design competitions but is a goldmine of systems programming wisdom.
- tomerv 15y agoI wonder if PCs will ever have non-linear memory. To explain what I mean, suppose you have a big 2-dimensional array in memory. As it works now, if you read a cell from memory, the area in memory around it is brought into the cache. Because of the way that arrays are represented in memory, what you get in the cache is just cells from the same row (or column). This means that if you need to access neighboring cells above of below the current cell you're not making any use of the cache. The way I see it, it might be useful if the system could somehow instruct the memory to bring a different-shaped block into the cache. Maybe there will be a whole part of memory intended for 2-dimensional arrays, and where blocks of memory will be allocated as squares on the plane (instead of segments on a line). Of course, something like this would require support from the programming language, which would need to mark put 2-dimensional arrays in that special part of the memory (and allocation will be much harder, now that you need to allocate 2-dimensional chunks).
- ajross 15y agoThat kind of caching architecture exists for graphics hardware already. GPUs have modes where the natural breakdown of memory is 2D (basically by interleaving the X and Y bits), and indeed that improves cache locality for 2D accesses. But not by a whole lot. The reason caches come in "lines" that are bigger than the words size of the processor is not an optimization (i.e. they're not deliberately bringing in nearby memory in the hope that it will be useful). The reason is that the logic associated with maintaining the cache (index and tag bits) is expensive, and needs to be repeated for each "thing" you have in the cache. So by making the "things" bigger (e.g. the 512 bit cache line on modern CPUs) you reduce the overhead of the bookkeeping.
- Someone 15y ago"The reason caches come in "lines" that are bigger than the words size of the processor is not an optimization (i.e. they're not deliberately bringing in nearby memory in the hope that it will be useful)." I do not think that is true. There is considerable chance that that extra memory will be useful. The simplest example to think of are cache lines that contain program code. The other canonical example is the "for item in array do item = f(x)" loop.
- goggles99 15y agoToday, this is what every "low level programmer" should know. If you are using a high level language with built in memory management and garbage collection, a condensed subset of this will suffice as only a fraction of the content will be helpful to you.
- jiggy2011 15y agoIf every programmer actually had to know the contents of every "what every programmer should know about X" articles before programming then we wouldn't have any programs.
- grundprinzip 15y agoWe use this full document very often during teaching in graduate-level courses and it always helped the students understanding the underlying concepts of data access. Even though for most of the people a thorough understanding of DRAM refresh latencies is not important, it is still a very, very important read for every programmer. Why? The answer is easy: Almost everything in modern computers is about locality spatial and temporal locality. As soon as the complexity of the programs you write is one level above "Hello World" or in Rails-speak a simple controller method. This will become important. It's easy to translate the concepts of aligning data in DRAM because it's faster to Rails-ish behavior. Assume that you read lot's of data from your database and you process it item by item. Inside your loop you perform another fetch from the database, again and again. If you would try to join the data (speak aligning) than you would need less requests to the database. Any system architecture that involves handling data will at one point in time come to the situation where the programmer will think about ordering instructions, database queries or even attributes inside a c-struct (see the discussion about why short ruby strings are faster than long...) If you won't keep anything in your mind from this document, but if you remember that sequential access and exploiting locality will increase the performance, then the document made it's point. Take the hours, read the document, and probably forget most, but take it as an inspiration, rather than an optimization guide.
- Roboprog 15y agoI used to think about locality a fair amount back when I programmed in C. In Java, I have no idea whether or not the fields in a copybook^H^H^H^H^H^H^H^H bean are going to be anywhere near contiguous, or not. Packing and unpacking stuff in a byte array / string gets tedious. It's a shame low level integration isn't somehow easier in Java, like it is in C#.
- olalonde 15y agoThis was posted almost 2 years ago: http://news.ycombinator.com/item?id=1511990 http://news.ycombinator.com/item?id=1511990
- vilya 15y agoI'm surprised to see so many people here getting hung up on the title of this paper, of all things, when there's so much good information in it. The title is just the author's opinion. Deal with it. And then read the paper anyway, because even if you don't use it directly it will help make you a better programmer.
- balloot 15y agoIt seems that every day on HN there is some post offering something "every programmer needs to know", yet the post is actually some very in-depth dive into the minutiae of the author's pet subject. The other day there was some post on front end/client side programming with a crazy amount of things everyone needs to know. Now apparently we also have to know the characteristics of the charging/discharging of capacitors in memory. All in all, this is WAY too in depth too have the title it has. The only way you have to know all this stuff as a software engineer is if you are working on the lowest level of something like an OS kernel or a video game engine.
- deleted 15y ago[deleted]