7 ms·

Decreasing the number of memory accesses

90 points by g0xA52A2A 4y ago

g0xA52A2A 4y ago
Part 2 is also now available https://johnnysswlab.com/decreasing-the-number-of-memory-accesses-the-compilers-secret-life-2-2/ https://johnnysswlab.com/decreasing-the-number-of-memory-acc...
pipo234 4y ago
Nice explanation, doing a step-by-step refactoring in C++. So for memory-bound performance optimization, you indeed see that halving memory accesses doubles throughput in practice, more or less. Curious if this kind of loop fusion would be something you get for free in purely functional language? That is, if you were to write a program (say in Haskell) for min, max plus that same code combined into a single program, would you indeed empirically see double the speed?
progx 4y ago
Loop fusion is something that a compiler / interpreter should do. Compiler need a breeze of AI to detect such code. For developers separated code is easier to read and to maintain.
- mhh__ 4y ago
  Compilers have been doing this for a long time already.
  - planede 4y ago
    I would have expected so, but gcc doesn't seem to do it for the article's example (didn't try other compilers): https://godbolt.org/z/Paq8f5x3d https://godbolt.org/z/Paq8f5x3d
    - adpcm 4y ago
      There existerar some 10+ year old patches to do so, which where never accepted/merged. https://github.com/wichtounet/gcc-loop-fusion/commits/master/loop_fusion_misses.diff https://github.com/wichtounet/gcc-loop-fusion/commits/master...
- mort96 4y ago
  Hmm, I hadn't thought about it before, but I bet ML could be really powerful when it comes to optimizing code. Existing LLMs (which aren't even trained on anything related to optimization!) can already do an incredible job optimizing in a lot of cases. Get an ML model to take a stab at optimizing, have a solid system for validating that two pieces of code are equivalent according to the C abstract machine, throw away the ML-suggested optimizations which change the semantics of the code, keep the ones which keep semantics the same.
  - mhh__ 4y ago
    You can just let the AI pick from a possible set of optimizations, rather than having it suggest the optimizations itself. There are a lot of optimizations that compilers could easily recognize but can't do because they'd be violating the standard. More realistically you can use an AI to generate vaguely realistic PGO data (profile guidance is where the real speed comes from). This has already been done at least by researchers.
    - mort96 4y ago
      > you can use an AI to generate vaguely realistic PGO data (profile guidance is where the real speed comes from) That's not a bad idea, but PGO is pretty limited. I'm thinking about things like rewriting a loop to use vector instructions; something which compilers are absolutely terrible at but ChatGPT is actually pretty good at.
      - mhh__ 4y ago
        PGO is limited if you are chasing throughput on really tight programs that spend most of their time in a small number of loops (preferably with textbooks written about them), but it's really useful if you have a bunch of branchy code that mainly does one thing but has to cater for other things too (compilers come to mind). Enabling PGO when building the D compiler made it almost 50% faster on some parts of the test suite (and fairly reasonable big files at that) - speedup elsewhere was not as dramatic but still a tidy win.
- flohofwoe 4y ago
  I don't agree. There's already way too much compiler magic happening, and the process to nudge/hint the compiler towards doing the right thing is already too opaque and fragile. Optimizations need to be predictable, transparent and robust, also across compiler vendors and compiler versions. What we need instead is "always on" profiling/debugging/inspection tools so that I can see directly and immediately the performance impact of my code changes while I'm typing the code (down to the compiler output as disassembly, annotated with performance warnings like predicted cache misses). Basically the same sort of evolution which gave us warning and error squiggles while typing, but for performance (think godbolt.org, but in realtime and with hot code reloading).
  - mhh__ 4y ago
    I think a reasonable solution is to just make the backend accessible from the frontend i.e. you should be able to declare how aggressive you want the inliner to be as a first class language idiom
- bell-cot 4y ago
  > Loop fusion is also a compiler optimization technique, so in theory the compiler can do it automatically. But this doesn’t happen often and when it does happen, this optimization has a tendency to break easily.
- dspillett 4y ago
  > For developers separated code is easier to read and to maintain. Unless the inner loop is something long or complicated (in which case for reading & maintainability it should maybe be broken down into functions), I generally find the fused version easier for both. For readability: it is immediately obvious that everything is working on exactly the same data, and the same range within that data, and that one section is not expected to have side effects that affect the running of the subsequent ones. For maintainability: there are less possibilities of an edit to one part that should affect all being missed elsewhere.
- JonChesterfield 4y ago
  Compilers don't need AI to do loop fusion. They need a commercially meaningful benchmark to benefit from it or for someone to decide it's an interesting problem to implement.
jamal-kumar 4y ago
little to no malloc and taking full advantage of what you can get away with without it is one of those tricks every programmer should know it's how we managed to get away with doing anything at all when our PCs had like 16-32 MEGABYTES of ram in them - or less, those are generous amounts it's why those computers can still play video
- LoganDark 4y ago
  > it's why those computers can still play video Meanwhile, new computers that are thousands or tens of thousands of times faster cannot play the same video.
twawaaay 4y ago
Honestly, for a single threaded processing potentially the largest improvement come from: * Exploiting cache locality (related data in same cache line, operations hit the data before it leaves cache, etc.) * Exploiting cache prefetching (understanding how to lay out your data and operations so that CPU prefetches data from memory into cache BEFORE it is needed) * Ensuring high density of data being accessed (make sure you only access what you need and the cache lines you access contain only data you need and not random other things that are not involved in the operation) ... at least in my own experience. These can be so powerful that may make a dumb algorithm perform like an absolute superstar. A lot of developers overthink algorithms. They try to create something that is super efficient on paper forgetting that the algorithm is not being executed on paper but by a real CPU. Sometimes it is better to sacrifice "paper efficiency" and just ensure cache locality, prefetching, data density and the result is speedup so large it more than covers for a little bit of inefficiency.
- hamilyon2 4y ago
  The article is about the same thing essentially? Decreasing number of memory accesses is the same thing as exploiting cache locality. Registers are the just more local more high-speed level of cache. Given on modern superscalar CPUs registers are virtual anyway.
  - twawaaay 4y ago
    > The article is about the same thing essentially? Decreasing number of memory accesses is the same thing as exploiting cache locality. No, it is not. For example, you can have an application that is doing a lot of memory accesses, but the working set is controlled to fit the cache except for couple of things that need to be fetched into the cache but you make sure those things fit predictable pattern that the CPU prefetcher can recognise and supply in advance of you needing it. Now, having less memory accesses usually helps, but it is kinda newb way of looking at the problem. What if you have to make a lot of accesses because your application is memory heavy (say it is a database)? Does it mean there is nothing you can do to improve it? Of course there are things you can do to improve it -- but you need a bit more in depth knowledge.
londons_explore 4y ago
I really want compilers to be able to make these changes. It seems that today, very few compilers are willing/able to mess with data structures and rearrange them. I'd like to see compilers that can at a minimum rearrange arrays of structures into structures of arrays depending on likely data access patterns of the different members of the structure. I'd also like to see compilers 'factoring out' things like vtables or structure members when they identify that they are constants or never read/written.
- flohofwoe 4y ago
  Compilers really shouldn't do this under the hood, it adds more complexity to the compiler, which makes it also more likely that things break in unexpected ways. Instead these should be explicit programming language features (like defining a regular struct but then slice this struct into an SoA). The rest should be handled by debugging and profiling tools which need to be much better integrated into the programming workflow than what is common today.
  - AgentOrange1234 4y ago
    Huh. But putting the complexity into the compiler once, instead of into every application where we would need to manually fuse loops, etc., seems like a huge win for net complexity and readability? (I’m sympathetic to the concern of things breaking in unexpected ways.)
    - flohofwoe 4y ago
      You can design the language to make such transforms more transparent without resorting to special 'compiler optimization magic'. For instance Zig has a MultiArrayList container in its stdlib which slices its generic item type into one array for each struct item. This isn't a special compiler feature, but a regular usage of Zig's comptime stuff: https://github.com/ziglang/zig/blob/master/lib/std/multi_array_list.zig https://github.com/ziglang/zig/blob/master/lib/std/multi_arr...
      - 4y ago
another2another 4y ago
I feel the first example for ranges is a bit contrived, most people would end up with something more like: void get_ids_adult_users(const std::vector<user_t>& allUsers, std::vector<int>& adultUsers) { for (const user_t& user: allUsers) { if (user.age >= 18) { adultUsers.push_back(user.age); } } } probably after calling reserve() on the adultUsers vector to avoid resizing.
xjay 4y ago
Other optimization awareness resources: > This series of five manuals describes everything you need to know about optimizing code for x86 and x86-64 family microprocessors, including optimization advices for C++ and assembly language, details about the microarchitecture and instruction timings of most Intel, AMD and VIA processors, and details about different compilers and calling conventions. > Operating systems covered: DOS, Windows, Linux, BSD, Mac OS X Intel based, 32 and 64 bits. https://agner.org/optimize/#manuals https://agner.org/optimize/#manuals
cl0ckt0wer 4y ago
Link isn't loading for me: https://archive.ph/pCYYf https://archive.ph/pCYYf

90 points by g0xA52A2A 4y ago

Part 2 is also now available https://johnnysswlab.com/decreasing-the-number-of-memory-accesses-the-compilers-secret-life-2-2/ https://johnnysswlab.com/decreasing-the-number-of-memory-acc...

pipo234 4y ago

Nice explanation, doing a step-by-step refactoring in C++. So for memory-bound performance optimization, you indeed see that halving memory accesses doubles throughput in practice, more or less. Curious if this kind of loop fusion would be something you get for free in purely functional language? That is, if you were to write a program (say in Haskell) for min, max plus that same code combined into a single program, would you indeed empirically see double the speed?

progx 4y ago

Loop fusion is something that a compiler / interpreter should do. Compiler need a breeze of AI to detect such code. For developers separated code is easier to read and to maintain.

mhh__ 4y ago
Compilers have been doing this for a long time already.
- planede 4y ago
  I would have expected so, but gcc doesn't seem to do it for the article's example (didn't try other compilers): https://godbolt.org/z/Paq8f5x3d https://godbolt.org/z/Paq8f5x3d
  - adpcm 4y ago
    There existerar some 10+ year old patches to do so, which where never accepted/merged. https://github.com/wichtounet/gcc-loop-fusion/commits/master/loop_fusion_misses.diff https://github.com/wichtounet/gcc-loop-fusion/commits/master...
mort96 4y ago
Hmm, I hadn't thought about it before, but I bet ML could be really powerful when it comes to optimizing code. Existing LLMs (which aren't even trained on anything related to optimization!) can already do an incredible job optimizing in a lot of cases. Get an ML model to take a stab at optimizing, have a solid system for validating that two pieces of code are equivalent according to the C abstract machine, throw away the ML-suggested optimizations which change the semantics of the code, keep the ones which keep semantics the same.
- mhh__ 4y ago
  You can just let the AI pick from a possible set of optimizations, rather than having it suggest the optimizations itself. There are a lot of optimizations that compilers could easily recognize but can't do because they'd be violating the standard. More realistically you can use an AI to generate vaguely realistic PGO data (profile guidance is where the real speed comes from). This has already been done at least by researchers.
  - mort96 4y ago
    > you can use an AI to generate vaguely realistic PGO data (profile guidance is where the real speed comes from) That's not a bad idea, but PGO is pretty limited. I'm thinking about things like rewriting a loop to use vector instructions; something which compilers are absolutely terrible at but ChatGPT is actually pretty good at.
    - mhh__ 4y ago
      PGO is limited if you are chasing throughput on really tight programs that spend most of their time in a small number of loops (preferably with textbooks written about them), but it's really useful if you have a bunch of branchy code that mainly does one thing but has to cater for other things too (compilers come to mind). Enabling PGO when building the D compiler made it almost 50% faster on some parts of the test suite (and fairly reasonable big files at that) - speedup elsewhere was not as dramatic but still a tidy win.
flohofwoe 4y ago
I don't agree. There's already way too much compiler magic happening, and the process to nudge/hint the compiler towards doing the right thing is already too opaque and fragile. Optimizations need to be predictable, transparent and robust, also across compiler vendors and compiler versions. What we need instead is "always on" profiling/debugging/inspection tools so that I can see directly and immediately the performance impact of my code changes while I'm typing the code (down to the compiler output as disassembly, annotated with performance warnings like predicted cache misses). Basically the same sort of evolution which gave us warning and error squiggles while typing, but for performance (think godbolt.org, but in realtime and with hot code reloading).
- mhh__ 4y ago
  I think a reasonable solution is to just make the backend accessible from the frontend i.e. you should be able to declare how aggressive you want the inliner to be as a first class language idiom
bell-cot 4y ago
> Loop fusion is also a compiler optimization technique, so in theory the compiler can do it automatically. But this doesn’t happen often and when it does happen, this optimization has a tendency to break easily.
dspillett 4y ago
> For developers separated code is easier to read and to maintain. Unless the inner loop is something long or complicated (in which case for reading & maintainability it should maybe be broken down into functions), I generally find the fused version easier for both. For readability: it is immediately obvious that everything is working on exactly the same data, and the same range within that data, and that one section is not expected to have side effects that affect the running of the subsequent ones. For maintainability: there are less possibilities of an edit to one part that should affect all being missed elsewhere.
JonChesterfield 4y ago
Compilers don't need AI to do loop fusion. They need a commercially meaningful benchmark to benefit from it or for someone to decide it's an interesting problem to implement.

jamal-kumar 4y ago

little to no malloc and taking full advantage of what you can get away with without it is one of those tricks every programmer should know it's how we managed to get away with doing anything at all when our PCs had like 16-32 MEGABYTES of ram in them - or less, those are generous amounts it's why those computers can still play video

LoganDark 4y ago
> it's why those computers can still play video Meanwhile, new computers that are thousands or tens of thousands of times faster cannot play the same video.

twawaaay 4y ago

Honestly, for a single threaded processing potentially the largest improvement come from: * Exploiting cache locality (related data in same cache line, operations hit the data before it leaves cache, etc.) * Exploiting cache prefetching (understanding how to lay out your data and operations so that CPU prefetches data from memory into cache BEFORE it is needed) * Ensuring high density of data being accessed (make sure you only access what you need and the cache lines you access contain only data you need and not random other things that are not involved in the operation) ... at least in my own experience. These can be so powerful that may make a dumb algorithm perform like an absolute superstar. A lot of developers overthink algorithms. They try to create something that is super efficient on paper forgetting that the algorithm is not being executed on paper but by a real CPU. Sometimes it is better to sacrifice "paper efficiency" and just ensure cache locality, prefetching, data density and the result is speedup so large it more than covers for a little bit of inefficiency.

hamilyon2 4y ago
The article is about the same thing essentially? Decreasing number of memory accesses is the same thing as exploiting cache locality. Registers are the just more local more high-speed level of cache. Given on modern superscalar CPUs registers are virtual anyway.
- twawaaay 4y ago
  > The article is about the same thing essentially? Decreasing number of memory accesses is the same thing as exploiting cache locality. No, it is not. For example, you can have an application that is doing a lot of memory accesses, but the working set is controlled to fit the cache except for couple of things that need to be fetched into the cache but you make sure those things fit predictable pattern that the CPU prefetcher can recognise and supply in advance of you needing it. Now, having less memory accesses usually helps, but it is kinda newb way of looking at the problem. What if you have to make a lot of accesses because your application is memory heavy (say it is a database)? Does it mean there is nothing you can do to improve it? Of course there are things you can do to improve it -- but you need a bit more in depth knowledge.

londons_explore 4y ago

I really want compilers to be able to make these changes. It seems that today, very few compilers are willing/able to mess with data structures and rearrange them. I'd like to see compilers that can at a minimum rearrange arrays of structures into structures of arrays depending on likely data access patterns of the different members of the structure. I'd also like to see compilers 'factoring out' things like vtables or structure members when they identify that they are constants or never read/written.

flohofwoe 4y ago
Compilers really shouldn't do this under the hood, it adds more complexity to the compiler, which makes it also more likely that things break in unexpected ways. Instead these should be explicit programming language features (like defining a regular struct but then slice this struct into an SoA). The rest should be handled by debugging and profiling tools which need to be much better integrated into the programming workflow than what is common today.
- AgentOrange1234 4y ago
  Huh. But putting the complexity into the compiler once, instead of into every application where we would need to manually fuse loops, etc., seems like a huge win for net complexity and readability? (I’m sympathetic to the concern of things breaking in unexpected ways.)
  - flohofwoe 4y ago
    You can design the language to make such transforms more transparent without resorting to special 'compiler optimization magic'. For instance Zig has a MultiArrayList container in its stdlib which slices its generic item type into one array for each struct item. This isn't a special compiler feature, but a regular usage of Zig's comptime stuff: https://github.com/ziglang/zig/blob/master/lib/std/multi_array_list.zig https://github.com/ziglang/zig/blob/master/lib/std/multi_arr...
    - 4y ago

another2another 4y ago

I feel the first example for ranges is a bit contrived, most people would end up with something more like: void get_ids_adult_users(const std::vector<user_t>& allUsers, std::vector<int>& adultUsers) { for (const user_t& user: allUsers) { if (user.age >= 18) { adultUsers.push_back(user.age); } } } probably after calling reserve() on the adultUsers vector to avoid resizing.

xjay 4y ago

Other optimization awareness resources: > This series of five manuals describes everything you need to know about optimizing code for x86 and x86-64 family microprocessors, including optimization advices for C++ and assembly language, details about the microarchitecture and instruction timings of most Intel, AMD and VIA processors, and details about different compilers and calling conventions. > Operating systems covered: DOS, Windows, Linux, BSD, Mac OS X Intel based, 32 and 64 bits. https://agner.org/optimize/#manuals https://agner.org/optimize/#manuals

cl0ckt0wer 4y ago

Link isn't loading for me: https://archive.ph/pCYYf https://archive.ph/pCYYf