4 ms·

> 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

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

dragontamer 9y 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-program-text-sections-start-at-0x0804800-and-stack-tops-start-at-0 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.
- jstimpfle 9y 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.
  - dragontamer 9y ago
    > Does that matter though? Yeah. Meltdown means that the OS (as a security measure) wipes away the TLB whenever you make a system call. So all of those cached TLB entries disappear every syscall due to Kernel Page-Table Isolation. And then the CPU core has to start from scratch, rebuilding the TLB-cache again. So last year (when we didn't know about Meltdown), a system-call was fast and efficient. This year, on Intel and ARM systems (vulnerable to Meltdown), system-calls are now forced to wipe TLB. (But not on AMD-systems, which happened to be immune to the problem) Both AMD and Intel implement x86 instruction set, and now the performance characteristics is different between the two boxes for something as simple as "blah = blah->next". ------------- The important bit is that C is still quite "high level", and indeed, even Assembly language "lies" to the programmer through virtual memory. The OS (specifically page-tables) can interject and have some magic going on even as assembly-code looks up specific addresses. The simple pointer-dereference *blah is actually incredibly complicated. There's no real way to know its performance characteristics from a C-level alone. It depends on the machine, the OS, the configuration of the OS (ie: MMap, Swap, Huge Page support, Meltdown...) and more.
- EvilTerran 9y 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.

dragontamer 9y 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-program-text-sections-start-at-0x0804800-and-stack-tops-start-at-0 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.

jstimpfle 9y 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.
- dragontamer 9y ago
  > Does that matter though? Yeah. Meltdown means that the OS (as a security measure) wipes away the TLB whenever you make a system call. So all of those cached TLB entries disappear every syscall due to Kernel Page-Table Isolation. And then the CPU core has to start from scratch, rebuilding the TLB-cache again. So last year (when we didn't know about Meltdown), a system-call was fast and efficient. This year, on Intel and ARM systems (vulnerable to Meltdown), system-calls are now forced to wipe TLB. (But not on AMD-systems, which happened to be immune to the problem) Both AMD and Intel implement x86 instruction set, and now the performance characteristics is different between the two boxes for something as simple as "blah = blah->next". ------------- The important bit is that C is still quite "high level", and indeed, even Assembly language "lies" to the programmer through virtual memory. The OS (specifically page-tables) can interject and have some magic going on even as assembly-code looks up specific addresses. The simple pointer-dereference *blah is actually incredibly complicated. There's no real way to know its performance characteristics from a C-level alone. It depends on the machine, the OS, the configuration of the OS (ie: MMap, Swap, Huge Page support, Meltdown...) and more.
EvilTerran 9y 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.