[Haskell-cafe] How far compilers are allowed to go with optimizations?

[Austin Seipp]

This is pretty much a core idea behind Data Parallel Haskell - it
transforms nested data parallel programs into flat ones. That's
crucial to actually making it perform well and is an algorithmic
change to your program. If you can reason about your program, and
perhaps have an effective cost model for reasoning about how it *will*
behave, then I don't see why not.*

Now, on a slight tangent, in practice, I guess it depends on your
target market. C programs don't necessarily expose the details to make
such rich optimizations possible. And Haskell programmers generally
rely on optimizations to make order of magnitude performance
difference in constant factors, although perhaps not in direct big-O
terms (and no, this isn't necessarily bad) - you will rarely see such
a change from various optimizing C compilers. The kinds and scope of
optimization opportunities are simply different. We're also not immune
to violations of intuition because of Compiler Things that have
nothing to do with data structures; even 'functionally equivalent'
programs can have drastically different space characteristics, just
due to sharing changes from CSE, eta reduction, or how the compiler is
feeling on any particular day of the week (I kid, I kid.) But overall,
we really do have vast amounts of robust, general optimization
opportunities - so I don't see why not try and exploit them if
reasonable.

* Note that intuitions about how the compiler performs tasks like
inlining/rewrites/boxing are not necessarily the most theoretically
nice or even sane ways to reason about things. Which is what we do
now. In practice you do need to know about performance characteristics
with pretty much any language and a million other specific things, and
I'm not sure Haskell is necessarily worse off here than anything else.

On Wed, Feb 6, 2013 at 5:45 AM, Jan Stolarek <jan.stolarek at p.lodz.pl> wrote:
> Hi all,
>
> some time ago me and my friend had a discussion about optimizations performed by GHC. We wrote a
> bunch of nested list comprehensions that selected objects based on their properties (e.g. finding
> products with a price higher than 50). Then we rewrote our queries in a more efficient form by
> using tree-based maps as indices over the data. My friend knows how to turn nested list
> comprehensions into queries that use maps and claims this could be automated. He
> argued that it would be fine if compiler did such an optimization automatically, since we can
> guarantee that both versions have exactly the same semantics and if they have the same semantics
> we are free to use faster version. From a functional point of view this is a good point, but
> nevertheless I objected to his opinion, claiming that if compiler performed such a high-level
> optimization - replace underlying data structure with a different one and turn one algorithm into
> a completely different one - programmer wouldn't be able to reason about space behaviour of a
> program. I concluded that such a solution should not be built into a compiler but instead turned
> into an EDSL.
>
> I would like to hear your opinion on this. How far a compiler can go with transforming code? I
> don't want to concentrate on discussing whether such an optimization is possible to implement
> from a technical point of view. What I'm interested in is whether such kind of high-level
> optimization could be accepted.
>
> Janek
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe



-- 
Regards,
Austin