3 ms·

Except in case of profile-guided optimization (which few people use), the compiler has one massive weakness: it doesn't know the "shape" and distribution of you

by 0xbear 9y ago

Except in case of profile-guided optimization (which few people use), the compiler has one massive weakness: it doesn't know the "shape" and distribution of your data. If it did, it would be able to do quite a bit more, but it mostly does not. I also find that people have way too much faith in omnipotence of compilers. If you care about performance, you _have_ to go down to the assembly level and ensure that the compiler did the right thing, at least in the hotspots. Oftentimes it does not, and you have to change your higher level code to make it cooperate.

taktoa 9y ago
> Except in case of profile-guided optimization (which few people use), the compiler has one massive weakness: it doesn't know the "shape" and distribution of your data. If it did, it would be able to do quite a bit more, but it mostly does not. Well, that's only true because programmers define functions in terms of types that are not sufficiently specific wrt their runtime invariants; in a dependently-typed language you could have an optimizing compiler that makes use of type-level information to do better optimizations. For instance, in a dependently-typed language, you could have a type of integers divisible by 11, and it will have no runtime overhead with respect to a machine integer. Of course, this comes with a cost: if you want to use such specific types, you have to prove to the compiler that the data it is getting really does satisfy the property (and yes, you can do such proofs even with data that is only available at runtime, by simply implementing a runtime check).
ant6n 9y ago
The example line is just operations of registers, without any dependencies until the function return. The compiler should know to interleave these instructions with the code, so that the CPU can issue them alongside other operations. Compilers should view operations more like a dependency graph, laying out operations with an interleaving that maximizes multi-issue, while keeping register pressure in check. In my mind, if the human can significantly change the output of the assembly by moving one line, the compiler optimizations may be turned off.
- tom_mellior 9y ago
  > laying out operations with an interleaving that maximizes multi-issue, while keeping register pressure in check How to actually do that has been an active research topic for 30 years or so. So far, that research hasn't yielded anything that is simple, efficient, and effective enough to be included in general-purpose compilers. Last time I looked at LLVM's backend, it used to schedule for minimal register pressure because spills are more expensive in general, and because out-of-order execution will undo your careful scheduling anyway. It also has a second scheduler after register allocation, but at that point it's hard to move stuff, especially on x86. On this particular code, manual scheduling paid off, partly because humans, unlike compilers, can simply try different variants and keep the best. Think of it as survivorship bias. Edit: BTW, if you actually compile the code from Github and compare the generated assembly to a version where the computation of next is moved to the end, you'll see that moving it to the end causes GCC to allocate a stack frame (on x86-64), which it doesn't do in the manually optimized one.

by 0xbear 9y ago

taktoa 9y ago

> Except in case of profile-guided optimization (which few people use), the compiler has one massive weakness: it doesn't know the "shape" and distribution of your data. If it did, it would be able to do quite a bit more, but it mostly does not. Well, that's only true because programmers define functions in terms of types that are not sufficiently specific wrt their runtime invariants; in a dependently-typed language you could have an optimizing compiler that makes use of type-level information to do better optimizations. For instance, in a dependently-typed language, you could have a type of integers divisible by 11, and it will have no runtime overhead with respect to a machine integer. Of course, this comes with a cost: if you want to use such specific types, you have to prove to the compiler that the data it is getting really does satisfy the property (and yes, you can do such proofs even with data that is only available at runtime, by simply implementing a runtime check).

ant6n 9y ago

The example line is just operations of registers, without any dependencies until the function return. The compiler should know to interleave these instructions with the code, so that the CPU can issue them alongside other operations. Compilers should view operations more like a dependency graph, laying out operations with an interleaving that maximizes multi-issue, while keeping register pressure in check. In my mind, if the human can significantly change the output of the assembly by moving one line, the compiler optimizations may be turned off.

tom_mellior 9y ago
> laying out operations with an interleaving that maximizes multi-issue, while keeping register pressure in check How to actually do that has been an active research topic for 30 years or so. So far, that research hasn't yielded anything that is simple, efficient, and effective enough to be included in general-purpose compilers. Last time I looked at LLVM's backend, it used to schedule for minimal register pressure because spills are more expensive in general, and because out-of-order execution will undo your careful scheduling anyway. It also has a second scheduler after register allocation, but at that point it's hard to move stuff, especially on x86. On this particular code, manual scheduling paid off, partly because humans, unlike compilers, can simply try different variants and keep the best. Think of it as survivorship bias. Edit: BTW, if you actually compile the code from Github and compare the generated assembly to a version where the computation of next is moved to the end, you'll see that moving it to the end causes GCC to allocate a stack frame (on x86-64), which it doesn't do in the manually optimized one.