5 ms·

Two studies in compiler optimisations

128 points by hmpc 6mo ago

Joker_vD 6mo ago
> our optimisation relies on having r < count, but if count is zero this condition cannot be met. [Since taking the remainder of a division by zero is undefined behaviour, the compiler would be well within its rights to assume that count != 0 and proceed with the transformation.] Interestingly, even if you define division by zero to produce the remainder equal to the dividend, this optimization (replacing "(r + 1) % count" with "r + 1 == count ? 0 : r + 1") would still be legal.
- zer00eyz 6mo ago
  > r + 1 == count ? 0 : r + 1 It'is legal! But looks like a few more steps when compiled.
- Findecanor 6mo ago
  BTW. On ARM and RISC-V, integer remainder from division by zero does indeed result in the dividend (and no trap), unless the compiler is doing something unusual.
taliesinb 6mo ago
Interesting. It all seems very brittle, though. And that something has gone very wrong with our ecosystem of tools, languages, and processes when it becomes advisable to massage source until specific passes in a specific version LLVM don't mess things up for other passes. Not picking on the OA in the slightest; just thinking in terms of holistic system design. If you know what you want to happen, and you are smart enough to introspect the behavior of the tool and decide that it didnt happen, you are more than smart enough to just write it correctly in the first place. Perhaps that is unrealistic, perhaps there is a hidden iceberg of necessary but convolutive optimizations no human could realistically or legibly write. But ok, where do you really need to engage in this kind of optimization golf? Inlined functions? Ok, what about this targeted language feature for a future-day Zig: 1. Write an ordinary zig function 2. Write inline assembly version of that function 3. Write a "comptime assert" that first compiles to second, which only "runs" for the relevant arch. 4. What should that assert mean? That the compiler just uses your assembly version instead, but _also_ uses existing compiler machinery or an external theorem prover to verify they "behave the same up to X", for customizable values of X That has the right feel, maybe. You are "pinning" specific, vetted, optimizations without compromising the intent, readability, or correctness of your code. And easy iteration is possible, because a failing comptime assert will just dump the assembly; you can even start with an empty manual impl.
- adrianN 6mo ago
  Having a way to assert that the compiler does what you expect can be helpful in large projects with many contributors of different skill level. Having something fail when a random change breaks autovectorization can save a lot of time profiling. When a compiler upgrade changes codegen I would also prefer an assertion telling me about it so that I can run relevant benchmarks to see whether it’s an improvement or not. Relying on whole-system benchmarks is difficult due to noise.
  - chriswarbo 6mo ago
    Haskell has a package to make testing this sort of thing easier https://hackage.haskell.org/package/inspection-testing https://hackage.haskell.org/package/inspection-testing
- foltik 6mo ago
  It feels like a leaky abstraction, and similarly implies there should be some way to drop down a layer and work directly with what’s beneath. Something in between C and non-portable assembly. Asserting retroactively that compilers produce the correct assemvbly feels like just plain giving up on everything in between. Surely the best we can do isn’t a bunch of flaky weirdly interacting optimizations, UB footguns everywhere, things changing when updating the toolchain, etc?
  - Archit3ch 6mo ago
    > Something in between C and non-portable assembly. Writing your own LLVM passes?
  - thefaux 6mo ago
    I have written a compiler for a language at more or less this abstraction level. It provides access to 16 general purpose registers and a set of virtual instructions that operate on these registers. I program on an intel mac so the virtual instructions all map directly to x86_64 instructions, but it would be very straightforward to write an arm backend that may compose multiple arm instructions for the equivalent x86_64 behavior. I also could support virtual registers for platforms with fewer than 16 registers. Having this compiler, which is extremely fast (it is self hosted and self compiles its own 9750K line source file in 15ms on my 2019 macbook pro and I've seen throughout ranging from 500K to 10M lines per second for other programs), I have little interest in ever using LLVM again. I would rather just write optimal code than pray that LLVM does a good job for me. For equivalent programs, I find LLVM can be anywhere from 50-10000x slower than my compiler and doesn't necessarily produce better code. I can produce examples of LLVM code becoming significantly worse at -O2 than at -O0. The only real utility LLVM offers me at this point is that I could use it to figure out what an optimal solution to a small subprogram might be by compiling a small c program and inspecting the output. Then I can just directly write the optimal solution instead of being perpetually bogged down by llvm's bloat as well as also being exposed to unexpected regressions in the optimizer and/or having to learn its strange incantations to get desired performance.
openclaw01 6mo ago
[dead]
villgax 6mo ago
Do not check OP's art on a work machine lol
ralferoo 6mo ago
> Here, the simplification analysis uses the conditional hidden in the assert() macro to figure out that we only execute the urem instruction if cur < count (see the isImpliedByDomCondition() method). This can have the unexpected consequence of making builds with assertions enabled faster in some cases; we can restore performance by replacing disabled assertions with assume attributes, which have no runtime impact. It surprises me that the compiler doesn't still take the inference from the assert and just disable emitting the code to perform the check. Over the last 15 years I've worked on many codebases that are written with unnecessary asserts, partly as documentation, but maybe because people assumed it helped the compiler. I've also worked on many codebases (and written code like this on my own projects) where the code looks like: assert(condition); if (condition) { ... } because I still want that safety check in release builds, and want the exception in debug builds but absolutely not ever in release builds.
- jcalvinowens 6mo ago
  > It surprises me that the compiler doesn't still take the inference from the assert and just disable emitting the code to perform the check. The compiler isn't as clever as I think you're envisioning: assert() only works that way because it exits the control flow if the statement isn't true.
  - ralferoo 6mo ago
    My point is that even though the assert() is optimised out, the compiler could still assume that the condition is valid.
    - jcalvinowens 6mo ago
      How? The assert() has no special significance to the compiler at all, it's just code. Usually it's just an empty macro for non-debug builds. I guess you could define your assert() use [[assume]] in C++ for non-debug builds... but that seems like a very bad idea to me. Just leave the asserts in prod. They almost certainly don't have measurable overhead. The few that do can be dealt with separately. The Linux kernel has thousands of asserts which are always checked at runtime (BUG_ON).
derodero24 6mo ago
[flagged]
Serhii-Set 6mo ago
[flagged]
devnotes77 6mo ago
[dead]

128 points by hmpc 6mo ago

> our optimisation relies on having r < count, but if count is zero this condition cannot be met. [Since taking the remainder of a division by zero is undefined behaviour, the compiler would be well within its rights to assume that count != 0 and proceed with the transformation.] Interestingly, even if you define division by zero to produce the remainder equal to the dividend, this optimization (replacing "(r + 1) % count" with "r + 1 == count ? 0 : r + 1") would still be legal.

zer00eyz 6mo ago
> r + 1 == count ? 0 : r + 1 It'is legal! But looks like a few more steps when compiled.
Findecanor 6mo ago
BTW. On ARM and RISC-V, integer remainder from division by zero does indeed result in the dividend (and no trap), unless the compiler is doing something unusual.

taliesinb 6mo ago

Interesting. It all seems very brittle, though. And that something has gone very wrong with our ecosystem of tools, languages, and processes when it becomes advisable to massage source until specific passes in a specific version LLVM don't mess things up for other passes. Not picking on the OA in the slightest; just thinking in terms of holistic system design. If you know what you want to happen, and you are smart enough to introspect the behavior of the tool and decide that it didnt happen, you are more than smart enough to just write it correctly in the first place. Perhaps that is unrealistic, perhaps there is a hidden iceberg of necessary but convolutive optimizations no human could realistically or legibly write. But ok, where do you really need to engage in this kind of optimization golf? Inlined functions? Ok, what about this targeted language feature for a future-day Zig: 1. Write an ordinary zig function 2. Write inline assembly version of that function 3. Write a "comptime assert" that first compiles to second, which only "runs" for the relevant arch. 4. What should that assert mean? That the compiler just uses your assembly version instead, but _also_ uses existing compiler machinery or an external theorem prover to verify they "behave the same up to X", for customizable values of X That has the right feel, maybe. You are "pinning" specific, vetted, optimizations without compromising the intent, readability, or correctness of your code. And easy iteration is possible, because a failing comptime assert will just dump the assembly; you can even start with an empty manual impl.

adrianN 6mo ago
Having a way to assert that the compiler does what you expect can be helpful in large projects with many contributors of different skill level. Having something fail when a random change breaks autovectorization can save a lot of time profiling. When a compiler upgrade changes codegen I would also prefer an assertion telling me about it so that I can run relevant benchmarks to see whether it’s an improvement or not. Relying on whole-system benchmarks is difficult due to noise.
- chriswarbo 6mo ago
  Haskell has a package to make testing this sort of thing easier https://hackage.haskell.org/package/inspection-testing https://hackage.haskell.org/package/inspection-testing
foltik 6mo ago
It feels like a leaky abstraction, and similarly implies there should be some way to drop down a layer and work directly with what’s beneath. Something in between C and non-portable assembly. Asserting retroactively that compilers produce the correct assemvbly feels like just plain giving up on everything in between. Surely the best we can do isn’t a bunch of flaky weirdly interacting optimizations, UB footguns everywhere, things changing when updating the toolchain, etc?
- Archit3ch 6mo ago
  > Something in between C and non-portable assembly. Writing your own LLVM passes?
- thefaux 6mo ago
  I have written a compiler for a language at more or less this abstraction level. It provides access to 16 general purpose registers and a set of virtual instructions that operate on these registers. I program on an intel mac so the virtual instructions all map directly to x86_64 instructions, but it would be very straightforward to write an arm backend that may compose multiple arm instructions for the equivalent x86_64 behavior. I also could support virtual registers for platforms with fewer than 16 registers. Having this compiler, which is extremely fast (it is self hosted and self compiles its own 9750K line source file in 15ms on my 2019 macbook pro and I've seen throughout ranging from 500K to 10M lines per second for other programs), I have little interest in ever using LLVM again. I would rather just write optimal code than pray that LLVM does a good job for me. For equivalent programs, I find LLVM can be anywhere from 50-10000x slower than my compiler and doesn't necessarily produce better code. I can produce examples of LLVM code becoming significantly worse at -O2 than at -O0. The only real utility LLVM offers me at this point is that I could use it to figure out what an optimal solution to a small subprogram might be by compiling a small c program and inspecting the output. Then I can just directly write the optimal solution instead of being perpetually bogged down by llvm's bloat as well as also being exposed to unexpected regressions in the optimizer and/or having to learn its strange incantations to get desired performance.

openclaw01 6mo ago

[dead]

villgax 6mo ago

Do not check OP's art on a work machine lol

ralferoo 6mo ago

> Here, the simplification analysis uses the conditional hidden in the assert() macro to figure out that we only execute the urem instruction if cur < count (see the isImpliedByDomCondition() method). This can have the unexpected consequence of making builds with assertions enabled faster in some cases; we can restore performance by replacing disabled assertions with assume attributes, which have no runtime impact. It surprises me that the compiler doesn't still take the inference from the assert and just disable emitting the code to perform the check. Over the last 15 years I've worked on many codebases that are written with unnecessary asserts, partly as documentation, but maybe because people assumed it helped the compiler. I've also worked on many codebases (and written code like this on my own projects) where the code looks like: assert(condition); if (condition) { ... } because I still want that safety check in release builds, and want the exception in debug builds but absolutely not ever in release builds.

jcalvinowens 6mo ago
> It surprises me that the compiler doesn't still take the inference from the assert and just disable emitting the code to perform the check. The compiler isn't as clever as I think you're envisioning: assert() only works that way because it exits the control flow if the statement isn't true.
- ralferoo 6mo ago
  My point is that even though the assert() is optimised out, the compiler could still assume that the condition is valid.
  - jcalvinowens 6mo ago
    How? The assert() has no special significance to the compiler at all, it's just code. Usually it's just an empty macro for non-debug builds. I guess you could define your assert() use [[assume]] in C++ for non-debug builds... but that seems like a very bad idea to me. Just leave the asserts in prod. They almost certainly don't have measurable overhead. The few that do can be dealt with separately. The Linux kernel has thousands of asserts which are always checked at runtime (BUG_ON).

derodero24 6mo ago

[flagged]

Serhii-Set 6mo ago

[flagged]

devnotes77 6mo ago

[dead]