What every programmer should know about memory, Part 1

by Anon84 • 14 years ago

236 79 14 years ago

ajross9• 14 years ago

These 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.

klochner2• 14 years ago

Very 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

prophetjohn8• 14 years ago

Exactly. 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_hn3• 14 years ago

The 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.

romaniv• 14 years ago

They 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.

ajross9• 14 years 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.)

vibrunazo• 14 years 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• 14 years ago

There are very few software environments where the cost difference of "Read 1MB sequentially from disk" versus "Read 1MB sequentially from memory" is irrelevant.

sho_hn3• 14 years ago

If 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

wmf• 14 years ago

As 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.

rtkwe• 14 years ago

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• 14 years ago

Ahh, 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• 14 years ago

It'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/) won't win any design competitions but is a goldmine of systems programming wisdom.

tomerv• 14 years ago

I 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).

ajross9• 14 years ago

That 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.

Someone3• 14 years 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.

Someone3• 14 years ago

Not what you describe, but tries to solve the same problem: PowerPC has instructions that tell the system what memory you are planning to use. See for example https://developer.apple.com/hardwaredrivers/ve/caches.html

There also are CPUs that attempt to detect access patterns without help from the programmer, for example Power: http://chipdesignmag.com/display.php?articleId=3926&issu....

I think Intel CPUs have similar functionality, but these were the ones I found first (using "cache stride hints" as Google query), perhaps because Intel uses different terminology.

goggles99• 14 years ago

Today, 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• 14 years ago

If 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• 14 years ago

We 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• 14 years ago

I 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• 14 years ago

This was posted almost 2 years ago: http://news.ycombinator.com/item?id=1511990

vilya2• 14 years ago

I'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.

balloot4• 14 years ago

It 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.

What every programmer should know about memory, Part 1

Related Stories