Is it possible to create an algorithm-aware optimizer?

Question

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?

Answer 1

Actually, optimizing compilers do that kind of things. I am for example thinking of the work of Robert Paige 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 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, 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, 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.