undefined | Better HN

0 pointsmunificent7y ago0 comments

C leads you to believe that memory access has uniform cost regardless of address. What is the perf cost of:

    *foo

Depending on what foo points to, and which memory you have previously read, the cost can vary by close to two orders of magnitude on many chips.

C does give you the ability to control those costs, but controlling how you lay out your data in memory and controlling imperatively in which order you access it. But the language doesn't show you those costs in any way.

0 comments

jstimpfle7y ago

> But the language doesn't show you those costs in any way.

I think it's pretty clear. Access memory sequentially, and you can expect to hit the cache. Access more memory than the cache size in a random order, and you can expect to pay memory access latencies (100s of CPU cycles).

I doubt you would be willing to manage the cache yourself in every line of code. That would be a lot of code. Some programmers might want to tune cache eviction behaviour by changing it in a few controlled points in time. But not in a way that couldn't be exposed to assembler/C. (I don't know if that's even realistic from a hardware architect's point of view).

dragontamer7y ago

> Access memory sequentially

Except memory is virtual. Memory location 0x1000 might be forward, or backwards compared to 0xFFF, depending on the state of the Translation-lookaside buffer (TLB).

Ever notice how (when ASLR is disabled), programs all start at the same location?? (https://stackoverflow.com/questions/14795164/why-do-linux-pr...)

Hint: Virtual address 0x0804800 doesn't belong at physical address 0x0804800. The OS can put that memory anywhere, and the CPU will "translate" the memory during runtime.

This means that in an obscure case, going forward a linked list (ie: node = node->next) may involve FIVE memory lookups on x86-64

* Page Map Lookup

* Page Directory Pointer lookup

* Page Directory lookup

* Page Table lookup

* Finally, the physical location of "node->next".

An even more obscure case (looking at maybe address 0xFFFC, unaligned) may require two lookups, for a total of 10-memory lookups (the page-directory walk for page 0xFFFC, and then the page-directory walk for 0x1000).

There is a LOT of hardware involved in just a simple "node = node->next" in a linked list. Its not even CPU-dependent. Its OS configurable too. x86 supports 4kb pages (typical in Linux / Windows), 2MB Large Pages and 1GB Huge Pages.

jstimpfle7y ago

> Except memory is virtual. Memory location 0x1000 might be forward, or backwards compared to 0xFFF, depending on the state of the Translation-lookaside buffer (TLB).

Does that matter though? I would assume that the "prefetcher" (or whatever it's called) can make its predictions in terms of virtual memory.

Regarding the linked list, it has been common wisdom for a long time that one should prefer sequential memory instead of linked lists. A nice benefit is that this simplifies the code as well :-). Growing and reallocating sequential buffers might not be possible in very dynamic/real-time and decentralized architectures - like a kernel - though.

1 more reply

EvilTerran7y ago

And all that's without even getting into things like swap, or memory-mapped files. Or, to really go all-out, mmap() an NFS file - and you could find your mere pointer dereference waiting for the network.

j / k navigate · click thread line to collapse

0 comments

jstimpfle7y ago

> But the language doesn't show you those costs in any way.

dragontamer7y ago

> Access memory sequentially

Except memory is virtual. Memory location 0x1000 might be forward, or backwards compared to 0xFFF, depending on the state of the Translation-lookaside buffer (TLB).

Ever notice how (when ASLR is disabled), programs all start at the same location?? (https://stackoverflow.com/questions/14795164/why-do-linux-pr...)

Hint: Virtual address 0x0804800 doesn't belong at physical address 0x0804800. The OS can put that memory anywhere, and the CPU will "translate" the memory during runtime.

This means that in an obscure case, going forward a linked list (ie: node = node->next) may involve FIVE memory lookups on x86-64

* Page Map Lookup

* Page Directory Pointer lookup

* Page Directory lookup

* Page Table lookup

* Finally, the physical location of "node->next".

jstimpfle7y ago

> Except memory is virtual. Memory location 0x1000 might be forward, or backwards compared to 0xFFF, depending on the state of the Translation-lookaside buffer (TLB).

Does that matter though? I would assume that the "prefetcher" (or whatever it's called) can make its predictions in terms of virtual memory.

1 more reply

EvilTerran7y ago

j / k navigate · click thread line to collapse