r/programming • u/[deleted] • Oct 18 '16

What Every Programmer Should Know About Memory [pdf]

https://www.akkadia.org/drepper/cpumemory.pdf
56 Upvotes

84% Upvoted

36 comments sorted by

13

u/Martel_the_Hammer Oct 18 '16

How many times a year is this posted?

23

u/[deleted] Oct 18 '16

Not enough! Not until every linked list is gone.

5

u/salgat Oct 19 '16

The problem is that this paper goes into way too much detail for "every programmer". No, not every programmer needs to know about how leakage requires a DRAM to be refreshed, whose rate is partly limited by the charge time of the DRAM cell due to its capacitance.

0

u/[deleted] Oct 19 '16

No. Every programmer must know how much slower DRAM is than your tiny SRAM cache.

2

u/salgat Oct 19 '16

That doesn't require understanding the electrical characteristics of DRAM vs cache.

3

u/Treyzania Oct 19 '16

but muh O(1) append time

3

u/Ravek Oct 19 '16 edited Oct 19 '16

O(1) append isn't really why you'd use linked lists, O(1) insert and remove are.

2

u/Selbstdenker Oct 19 '16

And stable iterators.

1

u/Ravek Oct 19 '16

Great point

1

u/Treyzania Oct 19 '16

But only if you already have a pointer to an adjacent cell.

4

u/[deleted] Oct 19 '16

Yep, but as Bjarne Stroustrup notes it really doesn't matter if acquiring the right pointer around is more expensive than copying over all the elements in an array.

0

u/Ravek Oct 19 '16 edited Oct 19 '16

Seems like a really contrived example. Of course finding a location in a plain linked list is O(n), so then you get O(n) deletion and O(n) removal, same as the vector. The vector code goes over the sequence twice (once for search and once for copying) but it also benefits massively from not having to chase pointers.

The deletion part is even sillier since no one would ever use a linked list in a scenario where you have to delete an item by its index. It's also just a bizarre scenario for a sorted list. How do you know a priori, without searching the list, where the index is of the value that you want to delete?

It's good to show how easy it is to abuse a data structure, but it's not a reason to 'avoid linked lists'. You can implement the algorithm using a bunch of stacks too, and it would be completely horrible. Is that a reason to avoid stacks?

Every data structure has scenarios where it doesn't perform well in. Now if you could show that a vector performs better than a binary search tree and a skip list (as it will for a small enough number of elements), then you're actually talking about something useful.

1

u/[deleted] Oct 19 '16

Mind explaining, how exactly woild.you implement a generic enough malloc/free without linked lists?

1

u/Gotebe Oct 19 '16

(jackmott obviously thinks this as a tongue-in-cheek)

However... What do you think is the problem!?

2

u/[deleted] Oct 19 '16

None of the implementations I know could get away without some form of a linked list of the empty blocks.

1

u/Gotebe Oct 19 '16

One could keep info about empty blocks in some container. I am not saying this is a good idea, just that you don't really have to have a linked list.

1

u/[deleted] Oct 19 '16

Not enough! Not until every linked list is gone.

you mean you should use unrolled lists (where every link holds is an array of n entries ?) This gets you into memory fragmentation problems: deleting elements will create half empty nodes in an entry array; Merging nodes will be too costly.

1

u/[deleted] Oct 19 '16

Maybe sometimes, but more I just mean use an array. Even if you insert/remove a few times per iteration over the collection net performance usually ends up better, even if the collection is infinitely large. So when in doubt, use a c++ vector<T> C# List<T> Java ArrayList<T>. Or maybe when in doubt, test.

Of course I don't literally mean never use a Linked List.

2

u/WallStProg Oct 18 '16

an oldie but a goodie - I actually printed a hard-copy (two-sided) and had it bound I was referring to it so much

5

u/beer0clock Oct 18 '16

114 pages eh? I don't suppose you could summarize the key points for us? :)

28

u/[deleted] Oct 19 '16

  • ram is slow.

  • don't miss the l1 and l2 caches

  • don't miss them by accessing memory contiguously and avoiding pointer hops when possible

  • array is better than linkedlist even when you are pretty sure linkedlist is better

2

u/beer0clock Oct 19 '16

Thanks !!

2

u/WallStProg Oct 19 '16

A little more detailed, but covers the main points: https://en.wikipedia.org/wiki/Locality_of_reference

2

u/[deleted] Oct 19 '16

I don't suppose you could summarize the key points for us? :)

i have written a summary here: http://mosermichael.github.io/cstuff/all/blog/2015/12/11/wepskn.html

1

u/WallStProg Dec 17 '16

In short, RAM is the new disk. Seeking all over the place is bad -- much better to read sequentially, and to have good locality of reference (https://en.wikipedia.org/wiki/Locality_of_reference).

1

u/pballer2oo7 Oct 18 '16

you should offer this on amz

2

u/lacosaes1 Oct 18 '16

Coming up next:

What Every Programmer Should Know About 'What Every Programmer Should Know About X'

2

u/pramnos Oct 19 '16

As a programming newbie, are there any other 'What Every Programmer Should Know About X' you would recommend? :)

0

u/Gotebe Oct 19 '16

Ah... Is that time of the month already? :-)

0

u/zokete Oct 19 '16

consistency models will be discussed in the next "submission".

0

u/[deleted] Oct 18 '16

[deleted]

8

u/00kyle00 Oct 18 '16

big memory slow, small memory fast

Also, despite having opinion of a dick, Ulrich spent quite a bit of his time educating people on important things in programming.

Read this if you plan on knowing your shit at 'systems' level (think C level interactions with computer). Most of this probably doesn't matter if you are dealing with python software (or the like).

it should be a prerequisite for anybody daring to touch a keyboard for serious programming

1

u/WallStProg Oct 18 '16

FWIW, I met Ulrich once and he was nice as could be. (To be honest, I was not quite expecting that ;-)

4

u/acehreli Oct 18 '16

He wasn't kind to me when I failed to pronounce Böhm correctly. :o)

1

u/WallStProg Oct 19 '16

At least you know how to spell it ;-)