8 ms·

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 r

by 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.
      - mort96 4y ago
        50% is probably a pretty extreme case for PGO, but when rewriting code to use vector instructions instead of scalar often has a speedup between 2x and 4x. Both approaches are interesting is all I'm saying.
- JonChesterfield 4y ago
  > have a solid system for validating that two pieces of code are equivalent according to the C abstract machine What ideas do you have for doing that in anything under exponential time?
  - mort96 4y ago
    I don't have any, I haven't thought about it enough. However, the reason I think it might be interesting is that checking if something is a correct solution is often easier than coming up with a correct solution for a lot of classes of problems (assuming P!=NP and all that). And maybe you can't make a polynomial time verifier which works in the general case, but maybe you can make a useful one which handles a lot of cases.
    - c-cube 4y ago
      I'm pretty sure that program equivalence is undecidable, ie you literally can't write this validation pass at all. There's a C compiler (compcert) that is formally verified to preserve the semantic of its input C code down to assembly, but it takes a lot of human developed proofs in Coq to get there.
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.

by 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.
    - mort96 4y ago
      50% is probably a pretty extreme case for PGO, but when rewriting code to use vector instructions instead of scalar often has a speedup between 2x and 4x. Both approaches are interesting is all I'm saying.
JonChesterfield 4y ago
> have a solid system for validating that two pieces of code are equivalent according to the C abstract machine What ideas do you have for doing that in anything under exponential time?
- mort96 4y ago
  I don't have any, I haven't thought about it enough. However, the reason I think it might be interesting is that checking if something is a correct solution is often easier than coming up with a correct solution for a lot of classes of problems (assuming P!=NP and all that). And maybe you can't make a polynomial time verifier which works in the general case, but maybe you can make a useful one which handles a lot of cases.
  - c-cube 4y ago
    I'm pretty sure that program equivalence is undecidable, ie you literally can't write this validation pass at all. There's a C compiler (compcert) that is formally verified to preserve the semantic of its input C code down to assembly, but it takes a lot of human developed proofs in Coq to get there.

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.