4 ms·

Am I reading this right that this process optimizes for program length but not necessarily program performance?

by jl6 6y ago

superjan 6y ago
Yes. I think that this paper’s contribution is not that it pretends to be the final answer, but that this technique is even feasible at all.
DoofusOfDeath 6y ago
(Apologies because I don't have time to read that paper right now, but...) Program length can be evaluated (more or less) without ambiguity, non-determinism, or the need for actual benchmarking. In contrast, program performance (in practice) is hard to accurately predict via model, and on a typical computer system is affected by a lot of hidden initial state and other random variables. So unless you're content to use a simplistic model to grade a program's performance, I would guess that searching over that space would require actual benchmarking, which could significantly slow the search process. (Although various techniques like ceasing evaluation after a program takes longer than the best-so-far might help.)
- jcranmer 6y ago
  If you exclude branches, integer division, and memory instructions, it's easy to perfectly model your program's performance. Even for memory, if you assume it's all L1 cache hits, performance is again perfectly predictable--and if it's not all L1 cache hits, the optimization of the surrounding code basically doesn't matter (not on the level of superoptimization). The state-of-the-art for superoptimization would be Aiken's work (linked elsewhere in the comments). The hardest part here is building the formal specifications of every single instruction, but their group also showed that it's possible to automatically generate these from a small seed set by similar techniques.
  - DoofusOfDeath 6y ago
    > If you exclude branches, integer division, and memory instructions, it's easy to perfectly model your program's performance. Assuming you're right about that, those seem to me like very big caveats. Also, wouldn't thermals-based clock throttling be a factor as well, assuming that we're talking about wall-clock performance instead of clock-cycles performance? I'd be surprised if their impact on program performance is easy to perfectly model.
    - jcranmer 6y ago
      Superoptimization looks mainly at peephole optimizations. This is looking at small fragments of code, where you're trying to shave off one or two cycles. STOKE (which is the superoptimizer I alluded to in my comment) scales to dozens of instructions, and still requires loop-free code (because SMT solvers don't handle loops at all), and I'm not sure it handles branch cases more complicated than nested if-else [1]. The correctness oracles we need for superoptimization requires use of formal methods; basically SMT libraries these days. And modern SMT libraries tend to barely work when you deal with division (and remainder) operations, or if you use floating-point code [2]. So, essentially, the size of the programs that you can apply to this code generally means you can get away with ignoring these issues for such codes. The biggest exception is branch prediction, where a cmov is better than a branch if and only if the condition is unpredictable. > Also, wouldn't thermals-based clock throttling be a factor as well, assuming that we're talking about wall-clock performance instead of clock-cycles performance? Clock cycle performance will largely be monotonic in wall-clock performance, especially at the level of peephole optimization. You're not adjusting the amount of memory traffic, or other microarchitectural state significantly. The difference in energy between using a shift instruction versus a multiply versus an add isn't going to cause enough thermal difference to throttle the fans. In order to really increase energy usage enough to change frequency, you'd have to go from unvectorized code to using largest register width, and that just isn't going to happen in a superoptimizer--your loop and SLP vectorizer will be the one to change that. And once you've triggered the AVX-512-heavy frequency level, you're still going to want to use the variant of that that uses fewer clock cycles anyways. [1] It might work based on enumerating every path via path conditions, which could handle threaded jumps, but means complexity is roughly exponential in the number of conditions. Given that we're not really pushing hundreds of instructions yet, that means that branching has to be very minimal in anything our current engines can work with. [2] The typical approach here I believe is uninterpreted functions, so that SMT is largely only capable of applying the commutativity, associativity, distributivity, and other axioms you put into it.
eslaught 6y ago
This is a very old paper that, like a sibling comment indicated, served mainly to introduce the idea and show proof of concept. If you see my other top-level comment, there are papers that have advanced this idea rather considerably since then. In particular one of the more promising recent implementations is "stochastic" superoptimization where you view it as a search problem instead of brute force search. One of the great things about this is the search doesn't need to be perfectly accurate: e.g., you can evaluate only the 10% most promising programs via benchmarks to determine how fast they are, using a much faster (but less accurate) method of counting instructions for the other 90%.
monocasa 6y ago
It's from an era when program length was strongly correlated with program performance. And when it wasn't it was still a fixed known cost per instruction type, and could be statically computed.
- djmips 6y ago
  I was kind of nodding and agreeing with you but then I remembered a bunch of optimal code from back in those days that was very unwound and super large so it depended on the type of work being done. I guess one could say that purely algorithmic code tended to have size and speed correlated whereas code that was bottlenecked in memory read/write could benefit from being large. Cache wasn't having the big impact like today.

Am I reading this right that this process optimizes for program length but not necessarily program performance?

by jl6 6y ago

Am I reading this right that this process optimizes for program length but not necessarily program performance?

Yes. I think that this paper’s contribution is not that it pretends to be the final answer, but that this technique is even feasible at all.

DoofusOfDeath 6y ago

(Apologies because I don't have time to read that paper right now, but...) Program length can be evaluated (more or less) without ambiguity, non-determinism, or the need for actual benchmarking. In contrast, program performance (in practice) is hard to accurately predict via model, and on a typical computer system is affected by a lot of hidden initial state and other random variables. So unless you're content to use a simplistic model to grade a program's performance, I would guess that searching over that space would require actual benchmarking, which could significantly slow the search process. (Although various techniques like ceasing evaluation after a program takes longer than the best-so-far might help.)

jcranmer 6y ago
If you exclude branches, integer division, and memory instructions, it's easy to perfectly model your program's performance. Even for memory, if you assume it's all L1 cache hits, performance is again perfectly predictable--and if it's not all L1 cache hits, the optimization of the surrounding code basically doesn't matter (not on the level of superoptimization). The state-of-the-art for superoptimization would be Aiken's work (linked elsewhere in the comments). The hardest part here is building the formal specifications of every single instruction, but their group also showed that it's possible to automatically generate these from a small seed set by similar techniques.
- DoofusOfDeath 6y ago
  > If you exclude branches, integer division, and memory instructions, it's easy to perfectly model your program's performance. Assuming you're right about that, those seem to me like very big caveats. Also, wouldn't thermals-based clock throttling be a factor as well, assuming that we're talking about wall-clock performance instead of clock-cycles performance? I'd be surprised if their impact on program performance is easy to perfectly model.
  - jcranmer 6y ago
    Superoptimization looks mainly at peephole optimizations. This is looking at small fragments of code, where you're trying to shave off one or two cycles. STOKE (which is the superoptimizer I alluded to in my comment) scales to dozens of instructions, and still requires loop-free code (because SMT solvers don't handle loops at all), and I'm not sure it handles branch cases more complicated than nested if-else [1]. The correctness oracles we need for superoptimization requires use of formal methods; basically SMT libraries these days. And modern SMT libraries tend to barely work when you deal with division (and remainder) operations, or if you use floating-point code [2]. So, essentially, the size of the programs that you can apply to this code generally means you can get away with ignoring these issues for such codes. The biggest exception is branch prediction, where a cmov is better than a branch if and only if the condition is unpredictable. > Also, wouldn't thermals-based clock throttling be a factor as well, assuming that we're talking about wall-clock performance instead of clock-cycles performance? Clock cycle performance will largely be monotonic in wall-clock performance, especially at the level of peephole optimization. You're not adjusting the amount of memory traffic, or other microarchitectural state significantly. The difference in energy between using a shift instruction versus a multiply versus an add isn't going to cause enough thermal difference to throttle the fans. In order to really increase energy usage enough to change frequency, you'd have to go from unvectorized code to using largest register width, and that just isn't going to happen in a superoptimizer--your loop and SLP vectorizer will be the one to change that. And once you've triggered the AVX-512-heavy frequency level, you're still going to want to use the variant of that that uses fewer clock cycles anyways. [1] It might work based on enumerating every path via path conditions, which could handle threaded jumps, but means complexity is roughly exponential in the number of conditions. Given that we're not really pushing hundreds of instructions yet, that means that branching has to be very minimal in anything our current engines can work with. [2] The typical approach here I believe is uninterpreted functions, so that SMT is largely only capable of applying the commutativity, associativity, distributivity, and other axioms you put into it.

eslaught 6y ago

This is a very old paper that, like a sibling comment indicated, served mainly to introduce the idea and show proof of concept. If you see my other top-level comment, there are papers that have advanced this idea rather considerably since then. In particular one of the more promising recent implementations is "stochastic" superoptimization where you view it as a search problem instead of brute force search. One of the great things about this is the search doesn't need to be perfectly accurate: e.g., you can evaluate only the 10% most promising programs via benchmarks to determine how fast they are, using a much faster (but less accurate) method of counting instructions for the other 90%.

monocasa 6y ago

It's from an era when program length was strongly correlated with program performance. And when it wasn't it was still a fixed known cost per instruction type, and could be statically computed.

djmips 6y ago
I was kind of nodding and agreeing with you but then I remembered a bunch of optimal code from back in those days that was very unwound and super large so it depended on the type of work being done. I guess one could say that purely algorithmic code tended to have size and speed correlated whereas code that was bottlenecked in memory read/write could benefit from being large. Cache wasn't having the big impact like today.