RE: [Haskell-cafe] Properties of optimizer rule application?
On Wed, 16 Jan 2008, Simon Peyton-Jones wrote:
> GHC has one main mechanism for controlling the application of rules,
> namely simplifier "phases". You can say "apply this rule only after
> phase N" or "apply this rule only before phase N". Similarly for INLINE
> pragmas. The manual describes this in detail.
Indeed. But since it does not mention the number of phases, nor the number
of iterations per phase, nor what actually is performed per iteration,
this appeared to me to be an internal issue of GHC which should not be
relied on.
> I urge against relying on "top-down" or "bottom-up" guarantees, because
> they are fragile: if you miss a single opportunity to apply rule A, then
> rule B may kick in; but a later inlining or other simplification might
> make rule A applicable. Phases are the way to go.
I see.
> That said, GHC has much too rigid a notion of phases at the moment.
> There are precisely 3, namely 2 then 1 then 0, and that does not give enough
> control.
What about the 'gentle' phase in the dump ?
> Really we should let you give arbitrary names to phases, express
> constraints (A must be before B), and run a constraint solver to map
> phase names to a linear ordering.
Sounds like a topological sort. Reminds me on precedence control of infix
operators.
It seems to me that you have something more sophisticated already in mind.
What you sketch would allow application specific code to defer
optimization rules from the standard libraries. E.g. I could write rules
for lists that are designed for my application and that can be applied
without interference from Data.List. When no more of my rules can be
applied, then Data.List rules can fuse the rest.
It's interesting how to integrate this in the Haskell language. When you
want to state "phase A before phase B" you may have to refer to phases
defined in other modules. You have to be able to import them from other
modules, and you cannot use the regular 'import' syntax, since phase
identifiers are not part of Haskell language. Maybe you must enclose those
imports in pragmas, too. You need new module dependency checking, since
more dependencies can be introduced when optimization is switched on or
you have to restrict phase import to modules that are imported anyway.
{-# RULES
import qualified Data.List as List
#-}
> There's scope for an intern project here.
I could take the opportunity.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Properties of optimizer rule application?
GHC has one main mechanism for controlling the application of rules, namely
simplifier "phases". You can say "apply this rule only after phase N" or
"apply this rule only before phase N". Similarly for INLINE pragmas. The
manual describes this in detail.
I urge against relying on "top-down" or "bottom-up" guarantees, because they
are fragile: if you miss a single opportunity to apply rule A, then rule B may
kick in; but a later inlining or other simplification might make rule A
applicable. Phases are the way to go.
That said, GHC has much too rigid a notion of phases at the moment. There are
precisely 3, namely 2 then 1 then 0, and that does not give enough control.
Really we should let you give arbitrary names to phases, express constraints (A
must be before B), and run a constraint solver to map phase names to a linear
ordering. The current system is horribly non-modular.
There's scope for an intern project here.
Simon
| -Original Message-
| From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Henning
Thielemann
| Sent: 16 January 2008 09:57
| To: Haskell Cafe
| Subject: [Haskell-cafe] Properties of optimizer rule application?
|
|
| Reading various papers and the Wiki about GHC optimizer rules I got the
| impression that there are not much properties I can rely on and I wonder
| how I can write a reliable fusion framework with this constraint.
| I read about the strategy to replace functions early by fusable
| implementations and replace them back to fast low-level implementation if
| fusion was not possible. However, can I rely on the back-translation if I
| have no warranty that the corresponding rule is applied? Is there some
| warranty that rules are applied as long as applicable rules are available
| or is the optimizer free to decide that it worked enough for today?
| I see several phases with a fixed number of iterations in the output of
| -ddump-simpl-iterations. Is there some idea behind these phases or is the
| structure and number rather arbitrary? If there is only a fixed number of
| simplifier runs, how can I rely on complete fusion of arbitrary large
| expressions?
| At some place I read that the order of application of rules is arbitrary.
| I like to have some warranty that more special rules are applied before
| more general rules. That is, if rule X is applicable whereever Y is
| applicable then Y shall be tried before X. This is currently not assured,
| right?
| Another text passage tells that the simplification is inside-out
| expressions. Such a direction would make the design of rules definitely
| easier. Having both directions, maybe alternating in the runs of the
| simplifier, would be also nice. I could then design transforms of the
| kind:
|toFastStructure . slowA . slowB . slowC . slowWithNoFastCounterpart
|fastA . toFastStructure . slowB . slowC . slowWithNoFastCounterpart
|fastA . fastB . toFastStructure . slowC . slowWithNoFastCounterpart
|fastA . fastB . fastC . toFastStructure . slowWithNoFastCounterpart
|fastA . fastBC . toFastStructure . slowWithNoFastCounterpart
|fastABC . toFastStructure . slowWithNoFastCounterpart
|
| On the one hand the inner of functions may not be available to fusion, if
| the INLINE pragma is omitted. As far as I know inlining may take place
| also without the INLINE pragma, but I have no warranty. Can I rely on
| functions being inlined with INLINE pragma? Somewhere I read that
| functions are not inlined if there is still an applicable rule that uses
| the function on the left-hand side. Altogether I'm uncertain how inlining
| is interleaved with rule application. It was said, that rules are just
| alternative function definitions. In this sense a function definition with
| INLINE is a more aggressively used simplifier rule, right?
| On the other hand if I set the INLINE pragma then the inner of the
| function is not fused. If this would be the case, I could guide the
| optimizer to fuse several sub-expressions before others. Say,
| doubleMap f g = map f . map g
| could be fused to
| doubleMap f g = map (f . g)
| and then this fused version can be fused further in the context of the
| caller. The current situation seems to be that {-# INLINE doubleMap #-}
| switches off local fusion and allows global fusion, whereas omitting the
| INLINE pragma switches on local fusion and disallows global fusion. How
| can I have both of them?
| ___
| Haskell-Cafe mailing list
| Haskell-Cafe@haskell.org
| http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Properties of optimizer rule application?
Reading various papers and the Wiki about GHC optimizer rules I got the
impression that there are not much properties I can rely on and I wonder
how I can write a reliable fusion framework with this constraint.
I read about the strategy to replace functions early by fusable
implementations and replace them back to fast low-level implementation if
fusion was not possible. However, can I rely on the back-translation if I
have no warranty that the corresponding rule is applied? Is there some
warranty that rules are applied as long as applicable rules are available
or is the optimizer free to decide that it worked enough for today?
I see several phases with a fixed number of iterations in the output of
-ddump-simpl-iterations. Is there some idea behind these phases or is the
structure and number rather arbitrary? If there is only a fixed number of
simplifier runs, how can I rely on complete fusion of arbitrary large
expressions?
At some place I read that the order of application of rules is arbitrary.
I like to have some warranty that more special rules are applied before
more general rules. That is, if rule X is applicable whereever Y is
applicable then Y shall be tried before X. This is currently not assured,
right?
Another text passage tells that the simplification is inside-out
expressions. Such a direction would make the design of rules definitely
easier. Having both directions, maybe alternating in the runs of the
simplifier, would be also nice. I could then design transforms of the
kind:
toFastStructure . slowA . slowB . slowC . slowWithNoFastCounterpart
fastA . toFastStructure . slowB . slowC . slowWithNoFastCounterpart
fastA . fastB . toFastStructure . slowC . slowWithNoFastCounterpart
fastA . fastB . fastC . toFastStructure . slowWithNoFastCounterpart
fastA . fastBC . toFastStructure . slowWithNoFastCounterpart
fastABC . toFastStructure . slowWithNoFastCounterpart
On the one hand the inner of functions may not be available to fusion, if
the INLINE pragma is omitted. As far as I know inlining may take place
also without the INLINE pragma, but I have no warranty. Can I rely on
functions being inlined with INLINE pragma? Somewhere I read that
functions are not inlined if there is still an applicable rule that uses
the function on the left-hand side. Altogether I'm uncertain how inlining
is interleaved with rule application. It was said, that rules are just
alternative function definitions. In this sense a function definition with
INLINE is a more aggressively used simplifier rule, right?
On the other hand if I set the INLINE pragma then the inner of the
function is not fused. If this would be the case, I could guide the
optimizer to fuse several sub-expressions before others. Say,
doubleMap f g = map f . map g
could be fused to
doubleMap f g = map (f . g)
and then this fused version can be fused further in the context of the
caller. The current situation seems to be that {-# INLINE doubleMap #-}
switches off local fusion and allows global fusion, whereas omitting the
INLINE pragma switches on local fusion and disallows global fusion. How
can I have both of them?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
