6 ms·

Indeed, there are a limited number of hard-hitting topics that are definitely must-haves: * Rough latency timings * Caching * Prefetching * Sequential vs. r

by 3JPLW 8y ago

Indeed, there are a limited number of hard-hitting topics that are definitely must-haves: * Rough latency timings * Caching * Prefetching * Sequential vs. random access * N-dimensional layouts (row/column major and arbitrarily strided) * Design of cache-oblivious algorithms * SIMD-able access patterns * False sharing * Instruction cache & code size * Branch prediction and speculative execution I'd be curious to hear what else folks would put on (or remove from) this list.

dragontamer 8y ago
Good list. I'd add "Virtual Memory" to that list. In particular, the TLB cache, memory pages (4kB, 2MB "Large Pages", 2GB "Huge Pages). Although x86 specific, I'd also add x86-64 has 48-bit physical pointers: the top 16-bits are basically ignored by the current virtual memory system. I dunno if the whole Page Directory / Directory Tables / etc. etc. needs to be fully explained, but programmers should have an overall good idea what they are. There's lots of things to do with Virtual Memory. And anyone who actually reads profiler data needs to understand what the heck that TLB Cache Hits performance counter means. > * False sharing More specifically the MESI Protocol (although that's an abstraction), and cache lines should be taught. False Sharing comes as an understanding after you understand those other two concepts. A CPU Core holds a cache line in Exclusive state so that it can write to it. A 2nd CPU Core attempts to gain access, but it cannot until the 1st core releases control (by writing data back to memory and setting the line to the Invalid state). The knowledge of the 64-byte cache line is more general than just false sharing: it helps understand why alignment can be an issue (a load/store across a 64-byte cache line would require 2-reads by the memory controller), etc. etc.
- jawnv6 8y ago
  how is MESI "an abstraction"? why is it the only model proffered instead of MESIF/MOESI? and "the top 16-bits are basically ignored" is a funny way to spell "general protection exception on linear memory reference in non-canonical space" but sure, guess we're just handwaving here
  - dragontamer 8y ago
    > how is MESI "an abstraction"? why is it the only model proffered instead of MESIF/MOESI? Because no CPU actually implements MESI. All CPUs implement more complicated stuff, like MESIF / MOESI. Instead of going into MESIF (which only Intel CPUs implement) or MOESI (only older AMD CPUs implement), lets just stick with the textbook MESI. Which is "wrong", but its "correct enough" to explain the concept. That's what I mean by an abstraction, no CPU today actually does MESI, its simply a concept to introduce to solidify the student's understanding of cache coherency. Its close enough to reality without getting into the tricky CPU-specific details of the real world. > guess we're just handwaving I mean, you have to set those bits back to 0 before using them as a pointer. But the system will literally never use those top 16-bits for anything. So some highly optimized code stores data in those top 16-bits and then zeros them out before using. IIRC, Lisp machines and various interpreters.
- 3JPLW 8y ago
  I don't think you need to explain the intricacies of the MESI protocol — just explaining the fact that caches need to be consistent is quite sufficient. Perhaps throw in why they must be consistent. It then becomes clear that the cores need to communicate (somehow) to maintain this consistency if they're touching data within the same cache line.
  - dragontamer 8y ago
    MESI isn't really that complicated. Cache-lines are either Exclusive owned, Shared, Invalid, or Modified. CPU Cores communicate to each other which lines are owned or unowned, and that's how the caches stay coherent. If a CPU Core wants to change a cache-line owned by another core, they have to wait until the line is closed (set to "Invalid" state) by the other core. I think its easier to explain cache-coherence through MESI, rather than to abstractly just say "Caches are coherent". At least personally, I didn't understand cache coherence until I sat down and really tried to understand MESI. I guess other people learn differently than I do, but I always view cache-coherence through the MESI lens.
- bogomipz 8y ago
  >"Although x86 specific, I'd also add x86-64 has 48-bit physical pointers: the top 16-bits are basically ignored by the current virtual memory system." Could you elaborate on this? Which pointers exactly?
  - dragontamer 8y ago
    All pointers in user-space are 48-bits. All 48-bit pointers are translated by the page-directory virtual memory system into a real physical location. There's an extension to use 55-bits or 56-bits... I forget exactly. But I don't think its actually been implemented yet on any CPU yet. EDIT: It was Intel's 57-bit memory: https://en.wikipedia.org/wiki/Intel_5-level_paging https://en.wikipedia.org/wiki/Intel_5-level_paging . Yeah, I knew it was a weird number. But I guessed wrong earlier.
    - bogomipz 8y ago
      Oh I see what you are saying but that's not really just a pointer or a userspace thing, that 48 bit limit is simply imposed by the x86-64 CPU vendors in no? With 48 bits you can still address 256TB of memory. I guessing that from a practical and financial point of view it probably made little sense for vendors to build a CPU that enabled addressing the full 64 bits. At least for now.
saberience 8y ago
Again, you say these are "must haves." But in the real world of software, none of these would make any difference to most of the software being built today, much of which is being build in higher level languages for web applications/web sites/microservices etc. Let's say someone is building a micro-service in C#.Net. Why would any of this stuff matter to them? The company cares about features and moving forward quickly. It's rather like forcing all your developers to be able to code every type of different sorting algorithm when they are only ever going to call "mylist.Sort()" in reality. This seems like another of those occasions when HN misjudges what the vast reality of practical day to day software creation looks like. Most engineers are not writing low-level code, they are not working on hardware directly, and they don't need to know exactly how RAM works at the transistor level. I'm not saying it's not interesting, but it's not going to change how I write my for-loops and if statements or make calls to BigTable, etc.
- dragontamer 8y ago
  > I'm not saying it's not interesting, but it's not going to change how I write my for-loops and if statements or make calls to BigTable, etc. You might be surprised at how much changing your for loops can be when accessing matrix data. for(int i=0; i<10000; i++){ for(int j=0; j<10000; j++){ blah[j][i] = whatever(); // Column oriented is very slow. } } for(int j=0; j<10000; j++){ for(int i=0; i<10000; i++){ // Very fast: We move row-wise now. With luck, this is SIMD-vectorized by your compiler. blah[j][i] = whatever(); } } Test that out, and you'll see a major performance improvement. ----------- If someone is writing high performance code, the #1 goal is to be able to read your profiler's output. If you can't read what the profiler says (cache hits, TLB hits, memory stalls, etc. etc.) then you can't make sense of the data. The PDF goes deeper than I'd personally go, but there's some concepts here that are absolutely necessary if you actually want to understand what a decent profiler gives you these days.
  - saberience 8y ago
    If I saw that code at my company, I'd ask why someone building a rest api for web-services had to iterate through a 10000*10000 2D array while calling a method of every single cell. This isn't a use case I've seen in my 10 year career thus far. Also, you have to understand that saving 1 or 2 milliseconds isn't important when compared to getting software built faster. For the typical use case, optimizing a for-loop like this for in-memory data isn't going to change the total performance of your program by even 0.5%. This is what so many people just don't understand. For modern web based applications, 99.9% of the time spent is doing IO, either hard-drive, data storage, or across the network. Optimizing those calls is FAR more important, than wasting time trying to save 1 millisecond in a for-loop which is iterating over 100 in-memory objects. This is where the understanding that the practical reality of building software for a real business is very different to theoretical examples drummed up by computer scientists on discussion boards. I see so many engineers trying to make their in-memory code faster by parallizing it, saving (if they're lucky) 1 or 2 milliseconds, but making their code far less maintainable and potentially introducing bugs, while the users wouldn't notice any practical difference in the app. Meanwhile, the app really does feel slow, because some numb-nuts made a call to some api and blocked the ui thread.

by 3JPLW 8y ago

dragontamer 8y ago

Good list. I'd add "Virtual Memory" to that list. In particular, the TLB cache, memory pages (4kB, 2MB "Large Pages", 2GB "Huge Pages). Although x86 specific, I'd also add x86-64 has 48-bit physical pointers: the top 16-bits are basically ignored by the current virtual memory system. I dunno if the whole Page Directory / Directory Tables / etc. etc. needs to be fully explained, but programmers should have an overall good idea what they are. There's lots of things to do with Virtual Memory. And anyone who actually reads profiler data needs to understand what the heck that TLB Cache Hits performance counter means. > * False sharing More specifically the MESI Protocol (although that's an abstraction), and cache lines should be taught. False Sharing comes as an understanding after you understand those other two concepts. A CPU Core holds a cache line in Exclusive state so that it can write to it. A 2nd CPU Core attempts to gain access, but it cannot until the 1st core releases control (by writing data back to memory and setting the line to the Invalid state). The knowledge of the 64-byte cache line is more general than just false sharing: it helps understand why alignment can be an issue (a load/store across a 64-byte cache line would require 2-reads by the memory controller), etc. etc.

jawnv6 8y ago
how is MESI "an abstraction"? why is it the only model proffered instead of MESIF/MOESI? and "the top 16-bits are basically ignored" is a funny way to spell "general protection exception on linear memory reference in non-canonical space" but sure, guess we're just handwaving here
- dragontamer 8y ago
  > how is MESI "an abstraction"? why is it the only model proffered instead of MESIF/MOESI? Because no CPU actually implements MESI. All CPUs implement more complicated stuff, like MESIF / MOESI. Instead of going into MESIF (which only Intel CPUs implement) or MOESI (only older AMD CPUs implement), lets just stick with the textbook MESI. Which is "wrong", but its "correct enough" to explain the concept. That's what I mean by an abstraction, no CPU today actually does MESI, its simply a concept to introduce to solidify the student's understanding of cache coherency. Its close enough to reality without getting into the tricky CPU-specific details of the real world. > guess we're just handwaving I mean, you have to set those bits back to 0 before using them as a pointer. But the system will literally never use those top 16-bits for anything. So some highly optimized code stores data in those top 16-bits and then zeros them out before using. IIRC, Lisp machines and various interpreters.
3JPLW 8y ago
I don't think you need to explain the intricacies of the MESI protocol — just explaining the fact that caches need to be consistent is quite sufficient. Perhaps throw in why they must be consistent. It then becomes clear that the cores need to communicate (somehow) to maintain this consistency if they're touching data within the same cache line.
- dragontamer 8y ago
  MESI isn't really that complicated. Cache-lines are either Exclusive owned, Shared, Invalid, or Modified. CPU Cores communicate to each other which lines are owned or unowned, and that's how the caches stay coherent. If a CPU Core wants to change a cache-line owned by another core, they have to wait until the line is closed (set to "Invalid" state) by the other core. I think its easier to explain cache-coherence through MESI, rather than to abstractly just say "Caches are coherent". At least personally, I didn't understand cache coherence until I sat down and really tried to understand MESI. I guess other people learn differently than I do, but I always view cache-coherence through the MESI lens.
bogomipz 8y ago
>"Although x86 specific, I'd also add x86-64 has 48-bit physical pointers: the top 16-bits are basically ignored by the current virtual memory system." Could you elaborate on this? Which pointers exactly?
- dragontamer 8y ago
  All pointers in user-space are 48-bits. All 48-bit pointers are translated by the page-directory virtual memory system into a real physical location. There's an extension to use 55-bits or 56-bits... I forget exactly. But I don't think its actually been implemented yet on any CPU yet. EDIT: It was Intel's 57-bit memory: https://en.wikipedia.org/wiki/Intel_5-level_paging https://en.wikipedia.org/wiki/Intel_5-level_paging . Yeah, I knew it was a weird number. But I guessed wrong earlier.
  - bogomipz 8y ago
    Oh I see what you are saying but that's not really just a pointer or a userspace thing, that 48 bit limit is simply imposed by the x86-64 CPU vendors in no? With 48 bits you can still address 256TB of memory. I guessing that from a practical and financial point of view it probably made little sense for vendors to build a CPU that enabled addressing the full 64 bits. At least for now.

saberience 8y ago

Again, you say these are "must haves." But in the real world of software, none of these would make any difference to most of the software being built today, much of which is being build in higher level languages for web applications/web sites/microservices etc. Let's say someone is building a micro-service in C#.Net. Why would any of this stuff matter to them? The company cares about features and moving forward quickly. It's rather like forcing all your developers to be able to code every type of different sorting algorithm when they are only ever going to call "mylist.Sort()" in reality. This seems like another of those occasions when HN misjudges what the vast reality of practical day to day software creation looks like. Most engineers are not writing low-level code, they are not working on hardware directly, and they don't need to know exactly how RAM works at the transistor level. I'm not saying it's not interesting, but it's not going to change how I write my for-loops and if statements or make calls to BigTable, etc.

dragontamer 8y ago
> I'm not saying it's not interesting, but it's not going to change how I write my for-loops and if statements or make calls to BigTable, etc. You might be surprised at how much changing your for loops can be when accessing matrix data. for(int i=0; i<10000; i++){ for(int j=0; j<10000; j++){ blah[j][i] = whatever(); // Column oriented is very slow. } } for(int j=0; j<10000; j++){ for(int i=0; i<10000; i++){ // Very fast: We move row-wise now. With luck, this is SIMD-vectorized by your compiler. blah[j][i] = whatever(); } } Test that out, and you'll see a major performance improvement. ----------- If someone is writing high performance code, the #1 goal is to be able to read your profiler's output. If you can't read what the profiler says (cache hits, TLB hits, memory stalls, etc. etc.) then you can't make sense of the data. The PDF goes deeper than I'd personally go, but there's some concepts here that are absolutely necessary if you actually want to understand what a decent profiler gives you these days.
- saberience 8y ago
  If I saw that code at my company, I'd ask why someone building a rest api for web-services had to iterate through a 10000*10000 2D array while calling a method of every single cell. This isn't a use case I've seen in my 10 year career thus far. Also, you have to understand that saving 1 or 2 milliseconds isn't important when compared to getting software built faster. For the typical use case, optimizing a for-loop like this for in-memory data isn't going to change the total performance of your program by even 0.5%. This is what so many people just don't understand. For modern web based applications, 99.9% of the time spent is doing IO, either hard-drive, data storage, or across the network. Optimizing those calls is FAR more important, than wasting time trying to save 1 millisecond in a for-loop which is iterating over 100 in-memory objects. This is where the understanding that the practical reality of building software for a real business is very different to theoretical examples drummed up by computer scientists on discussion boards. I see so many engineers trying to make their in-memory code faster by parallizing it, saving (if they're lucky) 1 or 2 milliseconds, but making their code far less maintainable and potentially introducing bugs, while the users wouldn't notice any practical difference in the app. Meanwhile, the app really does feel slow, because some numb-nuts made a call to some api and blocked the ui thread.