4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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.... $\endgroup$ – vzn Mar 7 '14 at 4:15
  • $\begingroup$ @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. $\endgroup$ – babou Mar 7 '14 at 14:09
  • $\begingroup$ some early ideas on a (very ambitious/longterm/deep) research program called "SAT induction", more details in Theoretical Computer Science Chat $\endgroup$ – vzn Mar 7 '14 at 15:51
  • $\begingroup$ @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. $\endgroup$ – babou Mar 7 '14 at 18:04
  • $\begingroup$ @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 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. $\endgroup$ – vzn Mar 7 '14 at 18:28
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.