3 ms·

It is not about being allowed at all. The compiler does not understand the required high level result almost always. There are some attempts to patch typical g

It is not about being allowed at all. The compiler does not understand the required high level result almost always. There are some attempts to patch typical general algorithms (e.g. tree searches and implementations) with faster equivalents. They typically fail as devising such structure safely from low level code is a really hard problem.

bollu 8y ago
As a follow up, there are ways to detect high level patterns (such as matmul). Polly, LLVM's polyhedral loop optimiser does this [for matmul](https://polly.llvm.org/docs/Performance.html https://polly.llvm.org/docs/Performance.html). We plan on generalising this to support more operations.
chriswarbo 8y ago
> It is not about being allowed at all. > They typically fail as devising such structure safely from low level code is a really hard problem. I took the phrase "being allowed to" as meaning "it is known to be safe to", in which case you seem to be agreeing with the parent (i.e. it's usually not allowed AKA it's usually not known to be safe).
jcranmer 8y ago
There's always been a sort of pie-in-the-sky goal of "let people just say what the algorithm does, and let the compiler figure out the best way to implement that algorithm" with the idea being that the programmer doesn't have to concern himself/herself with details about the hardware that bear on the implementation. The main problem with that idea is that you have to find some language to describe the design, which often ends up being an implementation, and when you look at the invariants that must be maintained for correctness, it's difficult to deviate from that implementation substantially. Floating point arithmetic, which is the core of most numerical algorithms, is not associative (it is commutative). If someone asks you to sum up a list going from left to right, it is not legal to transform that into a sum that goes from right to left. And unfortunately, in a mathematical sense, associativity is the property that's often the most useful. So, in practice, the most useful cases to do this kind of heavy-mathematics optimization on are the ones where it's not legal in the first place. Even beyond that, many of these kinds of algorithms are already implemented in a core library that's been around for decades and has been highly-tuned for any architecture you want to run on, so the actual prospect for seeing real gains with a compiler are rather small.
- Darmani 8y ago
  > The main problem with that idea is that you have to find some language to describe the design, which often ends up being an implementation, and when you look at the invariants that must be maintained for correctness, it's difficult to deviate from that implementation substantially. Can we please stop repeating this line? It was false 50-60 years ago when garbage collection and register allocation was invented. It was false when yacc was built. And it's false today. The gap in detail between specification and implementation is huge. If you can change a function without changing its callers, then your program has some slack between the assumptions placed on that function and its implementation. From low-level performance things like changes to improve cache locality, to high-level ones like scheduling of data pipelines, there's a lot of space for synthesizers and search-based software improvement tools to work with. So, are you curious about program synthesis for floating-point accuracy? Have a look at Herbie.
  - jcranmer 8y ago
    > Can we please stop repeating this line? It was false 50-60 years ago when garbage collection and register allocation was invented. It was false when yacc was built. And it's false today. No, it's still very true today. We have pushed the bounds of what implementation details we are free to ignore, but those bounds are still very much on the order of "you have to program the algorithm I implemented" as opposed to "you have the freedom to choose any algorithm so long as the output obeys these mathematical constraints." Program synthesis techniques have improved and are improving, but they're still only really applicable to kernel-style transformations.
    - Darmani 8y ago
      What's a kernel-style transformation? That term is unfamiliar to me? Are you referring to e.g.: optimizing stencil kernels? You're correct that classical semantics-preserving compiler optimizations are very restricted, when not user guided as in the OP's tool. They do not have any form of specification weaker than the input code. This is why most synthesis tools do take something higher level than code. Then again, some really do have the workflow "figure out existing code's algorithm, and pick a better one." The first thing in this space that comes to mind is verified lifting, being pursued by my collaborators at UW.
DannyBee 8y ago
"The compiler does not understand the required high level result almost always." Depends heavily on the language and code we are talking about. For C++, there are plenty of compilers that can replace C++ standard library calls and usage with faster, more optimal, C++ library calls and usage. That's because it is possible to understand the guarantees needed. That's about as far as you can get in a language like C++. You can do complex idiom recognition (IE recognize handwritten sorts, whatever) but it's usually not worth it. Now obviously, there are languages that express invariants/contracts/etc that make this type of optimization much easier to do. "They typically fail as devising such structure safely from low level code is a really hard problem." Actually, the safety part is easier than the allowed part if you are trying to split them. But usually they are the same thing - the language does not allow it, therefore it is unsafe. It is generally easy and well understood how to analyze and know what set of preconditions any particular transform safe, and even if you can't prove it statically, you can insert runtime checks to make sure the preconditions hold. This generalizes very well. It's just not worth it most of the time. This is why we focus on subsets like loops, and things like polyhedral loop opts, etc, have complex cost models that try to take into account the cost of dynamic checks, etc. (I spent years funding and talking to researchers about this)

bollu 8y ago

As a follow up, there are ways to detect high level patterns (such as matmul). Polly, LLVM's polyhedral loop optimiser does this [for matmul](https://polly.llvm.org/docs/Performance.html https://polly.llvm.org/docs/Performance.html). We plan on generalising this to support more operations.

chriswarbo 8y ago

> It is not about being allowed at all. > They typically fail as devising such structure safely from low level code is a really hard problem. I took the phrase "being allowed to" as meaning "it is known to be safe to", in which case you seem to be agreeing with the parent (i.e. it's usually not allowed AKA it's usually not known to be safe).

jcranmer 8y ago

There's always been a sort of pie-in-the-sky goal of "let people just say what the algorithm does, and let the compiler figure out the best way to implement that algorithm" with the idea being that the programmer doesn't have to concern himself/herself with details about the hardware that bear on the implementation. The main problem with that idea is that you have to find some language to describe the design, which often ends up being an implementation, and when you look at the invariants that must be maintained for correctness, it's difficult to deviate from that implementation substantially. Floating point arithmetic, which is the core of most numerical algorithms, is not associative (it is commutative). If someone asks you to sum up a list going from left to right, it is not legal to transform that into a sum that goes from right to left. And unfortunately, in a mathematical sense, associativity is the property that's often the most useful. So, in practice, the most useful cases to do this kind of heavy-mathematics optimization on are the ones where it's not legal in the first place. Even beyond that, many of these kinds of algorithms are already implemented in a core library that's been around for decades and has been highly-tuned for any architecture you want to run on, so the actual prospect for seeing real gains with a compiler are rather small.

Darmani 8y ago
> The main problem with that idea is that you have to find some language to describe the design, which often ends up being an implementation, and when you look at the invariants that must be maintained for correctness, it's difficult to deviate from that implementation substantially. Can we please stop repeating this line? It was false 50-60 years ago when garbage collection and register allocation was invented. It was false when yacc was built. And it's false today. The gap in detail between specification and implementation is huge. If you can change a function without changing its callers, then your program has some slack between the assumptions placed on that function and its implementation. From low-level performance things like changes to improve cache locality, to high-level ones like scheduling of data pipelines, there's a lot of space for synthesizers and search-based software improvement tools to work with. So, are you curious about program synthesis for floating-point accuracy? Have a look at Herbie.
- jcranmer 8y ago
  > Can we please stop repeating this line? It was false 50-60 years ago when garbage collection and register allocation was invented. It was false when yacc was built. And it's false today. No, it's still very true today. We have pushed the bounds of what implementation details we are free to ignore, but those bounds are still very much on the order of "you have to program the algorithm I implemented" as opposed to "you have the freedom to choose any algorithm so long as the output obeys these mathematical constraints." Program synthesis techniques have improved and are improving, but they're still only really applicable to kernel-style transformations.
  - Darmani 8y ago
    What's a kernel-style transformation? That term is unfamiliar to me? Are you referring to e.g.: optimizing stencil kernels? You're correct that classical semantics-preserving compiler optimizations are very restricted, when not user guided as in the OP's tool. They do not have any form of specification weaker than the input code. This is why most synthesis tools do take something higher level than code. Then again, some really do have the workflow "figure out existing code's algorithm, and pick a better one." The first thing in this space that comes to mind is verified lifting, being pursued by my collaborators at UW.

DannyBee 8y ago

"The compiler does not understand the required high level result almost always." Depends heavily on the language and code we are talking about. For C++, there are plenty of compilers that can replace C++ standard library calls and usage with faster, more optimal, C++ library calls and usage. That's because it is possible to understand the guarantees needed. That's about as far as you can get in a language like C++. You can do complex idiom recognition (IE recognize handwritten sorts, whatever) but it's usually not worth it. Now obviously, there are languages that express invariants/contracts/etc that make this type of optimization much easier to do. "They typically fail as devising such structure safely from low level code is a really hard problem." Actually, the safety part is easier than the allowed part if you are trying to split them. But usually they are the same thing - the language does not allow it, therefore it is unsafe. It is generally easy and well understood how to analyze and know what set of preconditions any particular transform safe, and even if you can't prove it statically, you can insert runtime checks to make sure the preconditions hold. This generalizes very well. It's just not worth it most of the time. This is why we focus on subsets like loops, and things like polyhedral loop opts, etc, have complex cost models that try to take into account the cost of dynamic checks, etc. (I spent years funding and talking to researchers about this)