Concerning optimizations

[Yann Le Du]

Hello again,

I hope I'll get some answer to my previous post, but in the neantime I have a question about optimizations.

I've been looking at SAC , the amazing FP array language that has a 30 years mature optimizer, and the same number of users as ATS ;-) The main designer, Sven-Bodo Scholz, told me something that prompts my present post.

I have a very simple kind-of fiboncacci loop inside loop, and some of the computations bear no effect on the result, and if I use : `sac2c`, the SAC compiler, it just CRUSHES `gcc -O3` (factor 100x in running time for the same result).

So I asked Scholz how he managed it :

"If you write some code that computes stuff that does not contribute in any which way to the results, it is nice if the compiler can get rid of it. FP ensures that all effects are explicit. Once the compiler knows all of them it can elide everything else. But in gcc it is very hard to figure out whether there is a hidden side-effect somewhere, therefore, the guys in general do not even bother to try for the simple cases."

But I very often hear this about ATS :

"oh, ATS actually doesn’t optimize anything, except tail calls, produces the c intermediate code, and thus leaves gcc do its job, which is like awesome"

which to me sounds like (I may be wrong) :

"people who optimize before passing the baby to gcc are like dummies”

So why would ATS, which is functional, abandon its performance to gcc if it could do more (side-effects ?) optimizations thanks to being FP ? Is it because optimizing, like SAC, is a 30 years craft best left to future developers of ATS_n>=3 or is there something deeper ?

Is it because ATS is a systems programming language, and thus cannot risk eliding stuff that could be elided in an array language like SAC ?

Cheers,

Yann

[gmhwxi]

Hi Yann,

I will try to answer the questions you raised in an earlier post later.

Regarding optimizations, I find that feeding to gcc the C code generated from ATS source

is a reasonable choice. Yes, one could probably generate significantly more efficient code

by taking advantage of the rich type information inside ATS programs. But doing so is highly

non-trivial; it would require a very big effort.

Yes, the compiler of SAC can do amazing optimizations. But SAC as a programming language

often lacks features that can help construct efficient programs. Let me use a concrete example.

Say that I want to process all the lines in a given file. I could do this by calling fgets in a loop to

read in each line and process it, but this is very inefficient. I could do much better if I use mmap

to map the content of the file to some virtual address space, but this requires a lot more effort.

Naturally, I would expect a library function of some sort for fast processing lines in a file, but what

would be a good interface for such a function? Sometimes, I want to process all these lines sequentially,

and, sometimes, I want to process them in parallel. This is a very thorny issue in programming language

design. One key focus of ATS3 is on providing support for the programmer to write efficient code that

would often require much more effort if done elsewhere.

Cheers,

--Hongwei