<p>Actually, <a href="https://en.wikipedia.org/wiki/Optimizing_compiler" rel="nofollow">optimizing compiler</a>s do that kind of things. I am for
example thinking of the work of <a href="http://www.cs.ox.ac.uk/jeremy.gibbons/wg21/paige.html" rel="nofollow">Robert Paige</a> at NYU. The problem is of
course to identify situations where a given type of transformation may be useful.
That require identifying computational structures, and knowing some of
the algebraic properties of the data being manipulated.</p>

<p>A classical example, very simple, is the <a href="https://en.wikipedia.org/wiki/Program_optimization#Strength_reduction" rel="nofollow">strength-reduction</a> in
loops, where you replace a product by a sum. It usually does not change
much the complexity (see more below), but can effectively speed up your algorithm, at
the cost of one extra variable. This is a special case of finite
differencing techniques.</p>

<p>I think you should find example in the litterature on high-level
optimization, which is quite different from peep-hole optimization in
the code generation process. See the two wikipedia article for various types of code optimization.</p>

<p>Regarding the identification of such situations, they can sometimes be
found by formal analysis of program. It can also help to make them
more apparent by using very high-level abstractions in the programming
process.</p>

<p>Many such transformations improve the program without changing the
complexity. But it much depends on what complexity you are considering
and what is a unit operation.</p>

<p>For example if you consider <a href="https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Arithmetic_functions" rel="nofollow">arithmetics of unbounded integers</a>,
addition has linear cost, while multiplication has a higher cost
(quadratic in the naive case). Using reduction in strength in loops
will reduce complexity.</p>

<p>I unfortunately do not remember more spectacular cases.</p>

<p>There is also some significant litterature on <a href="https://en.wikipedia.org/wiki/Program_transformation" rel="nofollow">program transformations</a>, with a variety of techniques that started in the 1970ies. Some transformations may not bring much by themselves, but may enable other transformations. Pattern matching in equational algebras is one way of identifying possible tranformations that has been considered. This may be one reason why very high level abstractions can help the process.</p>

CC BY-SA 3.0
2014-03-07T10:03:33.997Z
2014-03-07T10:03:33.997Z
babou
<p>I've recently implemented a physics system where each object has to interact with eachother. It consisted of, pretty much, the following algorithm:</p>

<pre><code>for obj_a in world
    for obj_b in world
        obj_a.collide(obj_b)
</code></pre>

<p>This is O(N^2) and obviously scales very badly. I know, though, that distant objects don't collide, so I partitioned the space. The algorithm became:</p>

<pre><code>for obj_a in world
    for obj_b in space_partition_of(obj_a)
        obj_a.collide(obj_b)
</code></pre>

<p>Considering the second loop iterates only over objects close to A, it brings the complexity down to almost O(N) and is ridiculously faster.</p>

<p>That made me think: <strong>it does not matter which language I implemented the first algorithm, it would always be sluggish</strong>. There is not a single compiler in the world that would fix my mistake, as much as obvious it seems for a human programmer. My question is: what is there stopping us to create a compiler that <strong>replaces the algorithms and data-structures used for the optimal ones</strong>? Is it impossible in a turing complete language? Would it be possible in a non-turing-complete language such as Idris?</p>

CC BY-SA 3.0
2014-03-07T04:15:58.993Z
take a look at the recent nobel-prize winning research that optimizes molecular interaction calculations significantly away from a $n^2$ algorithm.... it seems quite noteworthy yet not to be studied by the TCS community much yet... as for your question, the main challenge is _machine learning/induction/automated thm proving_ and also getting anyone to _attempt_ this bold/grandiose research program.... (attacking the undecidable!); TCS community is split roughly between theorists and practitioners and this [somehat artificial] boundary tends to work against these kinds of crosscutting ideas....
vzn
CC BY-SA 3.0
2014-03-07T14:09:26.840Z
@vzn The community is also split between algorithmics and semantics. And
that shows painfully on occasion, even on cstheory.SE. The question
here addresses both.  Compiler writing should be able to combine both.
babou
CC BY-SA 3.0
2014-03-07T15:51:53.383Z
some early ideas on a (very ambitious/longterm/deep) research program called ["SAT induction"](http://vzn1.wordpress.com/2014/02/14/great-moments-in-empiricalexperimental-mathtcs-research-breakthough-sat-induction-idea/), more details in [chat]
vzn
CC BY-SA 3.0
2014-03-07T18:04:53.560Z
@vzn Your first comment (about "attacking the undecidable!") reminded me of
an old story in compiler optimization. It is about a program analysis
technique on which research had given up after one very prominent
scientist had proved it untractable. Until a PhD student decided he
did not agree, and developed a good technique for it that was widely
used. The catch was that the intractability result relied on a rare
special case. I guess this must have happened more than once.
babou
CC BY-SA 3.0
2014-03-07T18:28:31.037Z
@babou it would be great to see a ref for that. probably hard to track down. sounds plausible but there are also mythological stories in the area. yes your observation relates to what are called "barriers" in science/math which are in _some_ aspects social constructs and can be misleading at times, many examples. RJLipton has [written eloquently on this wrt tcs](http://rjlipton.wordpress.com/2012/11/29/barriers-to-pnp-proofs/) comparing it to _game of dodgeball_ (lol) but alas not everyone has gotten the bulletin. all shared sciences lead to collective beliefs verging on dogma at times.
vzn
CC BY-SA 3.0
2014-03-07T18:40:08.867Z
@vzn I will try to find the technical publication (that was long ago) But the details of the story itself are not written.
babou
CC BY-SA 3.0
2014-03-08T17:21:11.950Z
basically this is simply the phenomenon of [undecidability of program optimization](http://cstheory.stackexchange.com/questions/17178/undecidability-of-program-optimization) and [Rice's thm](http://en.wikipedia.org/wiki/Rice's_theorem). havent seen a simple ref/survey that covers this, wonder if there is one somewhere. see also [research on attacking multiple instances of undecidable problems](http://cstheory.stackexchange.com/questions/19358/research-on-systematically-attacking-multiple-instances-of-undecidable-problems)
vzn
<cc.complexity-theory><ds.algorithms><pl.programming-languages><optimization><compilers>
Is it possible to create an algorithm-aware optimizer?
MaiaVictor
# Is it possible to create an algorithm-aware optimizer?

(Asked by: username_0 on 2014-03-07)

I've recently implemented a physics system where each object has to interact with eachother. It consisted of, pretty much, the following algorithm:
for obj_a in world
    for obj_b in world
        obj_a.collide(obj_b)

This is O(N^2) and obviously scales very badly. I know, though, that distant objects don't collide, so I partitioned the space. The algorithm became:
for obj_a in world
    for obj_b in space_partition_of(obj_a)
        obj_a.collide(obj_b)

Considering the second loop iterates only over objects close to A, it brings the complexity down to almost O(N) and is ridiculously faster.
That made me think: it does not matter which language I implemented the first algorithm, it would always be sluggish. There is not a single compiler in the world that would fix my mistake, as much as obvious it seems for a human programmer. My question is: what is there stopping us to create a compiler that replaces the algorithms and data-structures used for the optimal ones? Is it impossible in a turing complete language? Would it be possible in a non-turing-complete language such as Idris?

**Tags:** cc.complexity-theory, ds.algorithms, pl.programming-languages, optimization, compilers
> **Comments:**
> **username_1**: take a look at the recent nobel-prize winning research that optimizes molecular interaction calculations significantly away from a $n^2$ algorithm.... it seems quite noteworthy yet not to be studied by the TCS community much yet... as for your question, the main challenge is _machine learning/induction/automated thm proving_ and also getting anyone to _attempt_ this bold/grandiose research program.... (attacking the undecidable!); TCS community is split roughly between theorists and practitioners and this [somehat artificial] boundary tends to work against these kinds of crosscutting ideas....  
> **username_2**: @vzn The community is also split between algorithmics and semantics. And that shows painfully on occasion, even on cstheory.SE. The question here addresses both.  Compiler writing should be able to combine both.  
> **username_1**: some early ideas on a (very ambitious/longterm/deep) research program called ["SAT induction"](http://vzn1.wordpress.com/2014/02/14/great-moments-in-empiricalexperimental-mathtcs-research-breakthough-sat-induction-idea/), more details in [chat]  
> **username_2**: @vzn Your first comment (about "attacking the undecidable!") reminded me of an old story in compiler optimization. It is about a program analysis technique on which research had given up after one very prominent scientist had proved it untractable. Until a PhD student decided he did not agree, and developed a good technique for it that was widely used. The catch was that the intractability result relied on a rare special case. I guess this must have happened more than once.  
> **username_1**: @babou it would be great to see a ref for that. probably hard to track down. sounds plausible but there are also mythological stories in the area. yes your observation relates to what are called "barriers" in science/math which are in _some_ aspects social constructs and can be misleading at times, many examples. RJLipton has [written eloquently on this wrt tcs](http://rjlipton.wordpress.com/2012/11/29/barriers-to-pnp-proofs/) comparing it to _game of dodgeball_ (lol) but alas not everyone has gotten the bulletin. all shared sciences lead to collective beliefs verging on dogma at times.  
> **username_2**: @vzn I will try to find the technical publication (that was long ago) But the details of the story itself are not written.  
> **username_1**: basically this is simply the phenomenon of [undecidability of program optimization](http://cstheory.stackexchange.com/questions/17178/undecidability-of-program-optimization) and [Rice's thm](http://en.wikipedia.org/wiki/Rice's_theorem). havent seen a simple ref/survey that covers this, wonder if there is one somewhere. see also [research on attacking multiple instances of undecidable problems](http://cstheory.stackexchange.com/questions/19358/research-on-systematically-attacking-multiple-instances-of-undecidable-problems)  

---

## 1 answers

### Answer by username_2 on 2014-03-07. Score: 3

Actually, [optimizing compiler](https://en.wikipedia.org/wiki/Optimizing_compiler)s do that kind of things. I am for
example thinking of the work of [Robert Paige](http://www.cs.ox.ac.uk/jeremy.gibbons/wg21/paige.html) at NYU. The problem is of
course to identify situations where a given type of transformation may be useful.
That require identifying computational structures, and knowing some of
the algebraic properties of the data being manipulated.

A classical example, very simple, is the [strength-reduction](https://en.wikipedia.org/wiki/Program_optimization#Strength_reduction) in
loops, where you replace a product by a sum. It usually does not change
much the complexity (see more below), but can effectively speed up your algorithm, at
the cost of one extra variable. This is a special case of finite
differencing techniques.

I think you should find example in the litterature on high-level
optimization, which is quite different from peep-hole optimization in
the code generation process. See the two wikipedia article for various types of code optimization.

Regarding the identification of such situations, they can sometimes be
found by formal analysis of program. It can also help to make them
more apparent by using very high-level abstractions in the programming
process.

Many such transformations improve the program without changing the
complexity. But it much depends on what complexity you are considering
and what is a unit operation.

For example if you consider [arithmetics of unbounded integers](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Arithmetic_functions),
addition has linear cost, while multiplication has a higher cost
(quadratic in the naive case). Using reduction in strength in loops
will reduce complexity.

I unfortunately do not remember more spectacular cases.

There is also some significant litterature on [program transformations](https://en.wikipedia.org/wiki/Program_transformation), with a variety of techniques that started in the 1970ies. Some transformations may not bring much by themselves, but may enable other transformations. Pattern matching in equational algebras is one way of identifying possible tranformations that has been considered. This may be one reason why very high level abstractions can help the process.


---

