3 ms·

> cost of cache misses How is the C memory model a leaky abstraction here? What better way do you suggest? Are we not fine coding sequential (in memory) datast

> cost of cache misses How is the C memory model a leaky abstraction here? What better way do you suggest? Are we not fine coding sequential (in memory) datastructures in C?

munificent 9y ago
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.
- jstimpfle 9y 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).
  - 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.
pedasmith 9y ago
How about a different example entirely? Memory nowadays is either CPU (and the GPU can access it) or GPU (and the CPU has a window into it). It's terribly important to use the right one: if a chunk of memory is mostly used by the CPU, it needs to be CPU memory, and if it's mostly used by the GPU, it needs to be GPU memory. But there's no good way to specify that. You might argue that a modern computer is more like programming a tightly-bound, nonuniform multi-processor system. And I'd agree. But C doesn't much to help program such a thing.
- jstimpfle 9y ago
  Still, what you normally do and can assume is that you're using just "CPU" memory with pretty predictable (I think) latencies and a transparent caching layer. When different things are mapped into the address space, that's an abstraction the programmer (or the user) consciously made. It should be possible to figure out the performance characteristics there. Of course, many programs work on various machines with their own performance characteristics. You should still be able optimize for any one of them by querying the hardware and selecting an appropriate implementation. If you want to put in the work. I don't think assembler/C is such a big problem here. But then again, I'm not a low level guy (in this sense) for now.

> cost of cache misses How is the C memory model a leaky abstraction here? What better way do you suggest? Are we not fine coding sequential (in memory) datastructures in C?

munificent 9y ago

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.

jstimpfle 9y 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).
- 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.

pedasmith 9y ago

How about a different example entirely? Memory nowadays is either CPU (and the GPU can access it) or GPU (and the CPU has a window into it). It's terribly important to use the right one: if a chunk of memory is mostly used by the CPU, it needs to be CPU memory, and if it's mostly used by the GPU, it needs to be GPU memory. But there's no good way to specify that. You might argue that a modern computer is more like programming a tightly-bound, nonuniform multi-processor system. And I'd agree. But C doesn't much to help program such a thing.

jstimpfle 9y ago
Still, what you normally do and can assume is that you're using just "CPU" memory with pretty predictable (I think) latencies and a transparent caching layer. When different things are mapped into the address space, that's an abstraction the programmer (or the user) consciously made. It should be possible to figure out the performance characteristics there. Of course, many programs work on various machines with their own performance characteristics. You should still be able optimize for any one of them by querying the hardware and selecting an appropriate implementation. If you want to put in the work. I don't think assembler/C is such a big problem here. But then again, I'm not a low level guy (in this sense) for now.