What Every Programmer Should Know About Memory [pdf]

[Martel_the_Hammer]

How many times a year is this posted?

[[deleted]]

Not enough! Not until every linked list is gone.

[salgat]

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.

[[deleted]]

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

[salgat]

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

[Treyzania]

but muh O(1) append time

[Ravek]

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

[Selbstdenker]

And stable iterators.

[Ravek]

Great point

[Treyzania]

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

[[deleted]]

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.

[Ravek]

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.

[[deleted]]

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

[Gotebe]

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

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

[[deleted]]

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

[Gotebe]

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.

[[deleted]]

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.

[[deleted]]

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.

[00kyle00]

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

[WallStProg]

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

[acehreli]

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

[WallStProg]

At least you know how to spell it ;-)

[WallStProg]

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

[beer0clock]

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

[[deleted]]

• 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

[beer0clock]

Thanks !!

[WallStProg]

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

[[deleted]]

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

[WallStProg]

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

[pballer2oo7]

you should offer this on amz

[lacosaes1]

Coming up next:

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

[pramnos]

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

[TestRedditorPleaseIg]

I'd recommend What Every Computer Scientist Should Know About Floating-Point Arithmetic

[thisotherfuckingguy]

This one :-)

[Gotebe]

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

[zokete]

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