Re: [Caml-list] compiler bug?

[skaller <skaller@users.sourceforge.net>]

On Thu, 2006-05-18 at 22:17 -0400, Brian Hurt wrote:

> >>> 	reduce revrev[t] (x:list[t]): rev (rev x) => x;

> I'm just wondering how often such optimizations are worthwhile. 

Me too. I don't know. However the above type of optimisation
is only a hint at what can be done. It's what I could implement
easily in a few hours, after noting in generated code there
really were cases of double list reversals.

>  From what 
> I've read, basic register allocation and peephole optimizations gain you 
> 2x the performance- after that, it's a fight for percentage points.

Most people seem to think eliminating array bounds checks is
worthwhile. 

Haskell certainly thinks deforestation and closure
elimination to be useful. These are high level optimisations
which I expect to have much more impact in most cases
than register fiddling. (They'd better .. GHC is still
a snail solving some very simple problems)

Indeed, the current Felix optimiser was obtained by noting
the woeful code generated for things like the Shootout
multiple loop test, and adding enough heuristics to
eliminate closures so the code reduced to the same
kind of basic C code a C programmer would write.

Of course I hope gcc -O3 etc will do the low level optimisations
for me, but it has to start with decent C code for that
to work.

> Especially considering that humans tend to be a lot better at recognizing 
> opportunities for high-level optimizations than computers are.  For 
> example, a human would be much more likely to notice a double list 
> reversal when the two reversals are in seperate modules, or otherwise 
> obscured from the compiler.  Even more so, the programmer may decide that 
> maybe a list isn't the right datastructure for this data- a decision I 
> wouldn't trust to a compiler.

I agree. Also note applying even reductions of the form above is
extremely expensive in compile time (matching every subexpression
looking for double list reversals cannot be fast :)

However, the point is that there is scope for much improvement
with high level optimisations. 

In particular, one hopes they can be hinted at in a way that
not only makes faster code .. but does so without compromising
correctness or other safety features.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net