7 ms·

Automatic Algorithms Optimization via Fast Matrix Exponentiation (2015)

104 points by zawerf 8y ago

taeric 8y ago
It is funny to see the repeated squares algorithm every time it is rediscovered. Knuth, unsurprisingly, had one of his earlier papers involving it. He presented it as related to addition chains and shows that just repeated squaring is not always superior. I'm curious what all came of this effort, seeing it is marked 2015. It is also fun to see benchmarks of this method used in executing fib.
- zawerf 8y ago
  It's not just the repeated squares algorithm though. The novel part about this post is the application of it. For most languages, if you write a for loop, the compiler is not smart enough to generate anything that runs in sublinear time. It might do some loop unrolling, reordering, or just skip running the whole loop altogether if it's dead code. But this is the first time I have seen something that can rewrite a loop to run in a different runtime complexity (specifically logarithmic time). He relies on rewriting python byte code but there's no reason why let's say a C compiler can't automatically identify a loop that can be rewritten as a linear recurrence relation and thus has a matrix exponentiation form.
  - phkahler 8y ago
    ... this is the first time I have seen something that can rewrite a loop to run in a different runtime complexity... Same here, but I really want to know how often this helps in real programs.
  - jcranmer 8y ago
    Clang will optimize basic loops away: https://godbolt.org/g/GMjKZm https://godbolt.org/g/GMjKZm
  - taeric 8y ago
    This isn't new, though. Just doesn't come up as often as folks would like. Consider benchmarks that get reduced to constant. Happens literally all the time. This particular change is neat, and is ultimately keyed on seeing optimizations from really old math. Which is the only thing I was wanting to add.
deleted 8y ago
[deleted]
Darmani 8y ago
This was a hot-topic 10-15 years ago. Then, over a few years, we went from "there has been little work applying computer algebra methods to program analysis and optimization" to "everything under the sun has already been done." It's been about 3 years since I looked at this stuff, and I'm having trouble remembering the names of the people in this area (lots of Europeans). Most of the action is in finding ever-larger fragments of programming languages they can solve. The one in this article handles what are called "arithmetic programs;" a bunch of people have worked on handling restricted shades of recursive programs.
DannyBee 8y ago
So, compilers can do this, and do do this, depending on the language and it's guarantees. GCC and LLVM use a chain of recurrence algebra and form for symbolic analysis that could easily represent this (or be extended to). But they probably won't bother any time soon. To understand why requires a little more detail first: The statement "However, compilers do not replace the computational algorithm, written by a human, by a more asymptotically efficient one." is mostly wrong. They generally do where they are allowed. They just aren't often allowed, or it's not worth it. There are languages that are playing with this even more heavily. But whether it's a good idea, eh. In numerics in particular, people often pick their algorithms very carefully for stability/etc reasons. For more generic things like sorts, a lot of this gets hidden in standard libraries anyway. For things nobody could really complain about, the compilers do idiom recognition of things like memcpys, string compares, etc and replace them. In any case, the problem is not recognizing and replacing the algorithm or idiom. The problem is deciding when doing so actually serves your users well. Going back up, when we first implemented scalar evolutions in GCC, we supported everything you can think of - closed form polynomial functions, matrices, mixers. In the end though, we were spending a lot of time handling cases that were very rare, mostly optimal as written anyway (so not useful for the optimizer), but still required exponential time solving/etc to do anything with. So a lot of that code was removed. Could you handle matrix exponentiation because it's fast? Sure. But it's unlikely to be worth it.
- AstralStorm 8y ago
  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.
ychen306 8y ago
Unfortunately it only works for toy examples. > cpmoptimize.recompiler.RecompilationError: Can't optimize loop: Unsupported instruction (LOAD_ATTR, 'b') at line 12 in fib, file "test.py"
deleted 8y ago
[deleted]

104 points by zawerf 8y ago

It is funny to see the repeated squares algorithm every time it is rediscovered. Knuth, unsurprisingly, had one of his earlier papers involving it. He presented it as related to addition chains and shows that just repeated squaring is not always superior. I'm curious what all came of this effort, seeing it is marked 2015. It is also fun to see benchmarks of this method used in executing fib.

zawerf 8y ago
It's not just the repeated squares algorithm though. The novel part about this post is the application of it. For most languages, if you write a for loop, the compiler is not smart enough to generate anything that runs in sublinear time. It might do some loop unrolling, reordering, or just skip running the whole loop altogether if it's dead code. But this is the first time I have seen something that can rewrite a loop to run in a different runtime complexity (specifically logarithmic time). He relies on rewriting python byte code but there's no reason why let's say a C compiler can't automatically identify a loop that can be rewritten as a linear recurrence relation and thus has a matrix exponentiation form.
- phkahler 8y ago
  ... this is the first time I have seen something that can rewrite a loop to run in a different runtime complexity... Same here, but I really want to know how often this helps in real programs.
- jcranmer 8y ago
  Clang will optimize basic loops away: https://godbolt.org/g/GMjKZm https://godbolt.org/g/GMjKZm
- taeric 8y ago
  This isn't new, though. Just doesn't come up as often as folks would like. Consider benchmarks that get reduced to constant. Happens literally all the time. This particular change is neat, and is ultimately keyed on seeing optimizations from really old math. Which is the only thing I was wanting to add.

deleted 8y ago

[deleted]

Darmani 8y ago

This was a hot-topic 10-15 years ago. Then, over a few years, we went from "there has been little work applying computer algebra methods to program analysis and optimization" to "everything under the sun has already been done." It's been about 3 years since I looked at this stuff, and I'm having trouble remembering the names of the people in this area (lots of Europeans). Most of the action is in finding ever-larger fragments of programming languages they can solve. The one in this article handles what are called "arithmetic programs;" a bunch of people have worked on handling restricted shades of recursive programs.

DannyBee 8y ago

So, compilers can do this, and do do this, depending on the language and it's guarantees. GCC and LLVM use a chain of recurrence algebra and form for symbolic analysis that could easily represent this (or be extended to). But they probably won't bother any time soon. To understand why requires a little more detail first: The statement "However, compilers do not replace the computational algorithm, written by a human, by a more asymptotically efficient one." is mostly wrong. They generally do where they are allowed. They just aren't often allowed, or it's not worth it. There are languages that are playing with this even more heavily. But whether it's a good idea, eh. In numerics in particular, people often pick their algorithms very carefully for stability/etc reasons. For more generic things like sorts, a lot of this gets hidden in standard libraries anyway. For things nobody could really complain about, the compilers do idiom recognition of things like memcpys, string compares, etc and replace them. In any case, the problem is not recognizing and replacing the algorithm or idiom. The problem is deciding when doing so actually serves your users well. Going back up, when we first implemented scalar evolutions in GCC, we supported everything you can think of - closed form polynomial functions, matrices, mixers. In the end though, we were spending a lot of time handling cases that were very rare, mostly optimal as written anyway (so not useful for the optimizer), but still required exponential time solving/etc to do anything with. So a lot of that code was removed. Could you handle matrix exponentiation because it's fast? Sure. But it's unlikely to be worth it.

AstralStorm 8y ago
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.

ychen306 8y ago

Unfortunately it only works for toy examples. > cpmoptimize.recompiler.RecompilationError: Can't optimize loop: Unsupported instruction (LOAD_ATTR, 'b') at line 12 in fib, file "test.py"

deleted 8y ago

[deleted]