optimization and rewrite rules questions
In the recently burried haskell-cafe thread "speed: ghc vs gcc", Bulat pointed out some of the optimizations that GHC doesn't do, such as loop unrolling. I suggested a way of experimenting with loop unrolling, using template haskell to bypass GHC's blindspot (it usually doesn't unfold recursive definitions http://www.haskell.org/pipermail/glasgow-haskell-users/2007-July/012936.html , but if we unfold a loop combinator at compile time, GHC's normal optimizations can take over from there): http://www.haskell.org/pipermail/haskell-cafe/2009-February/056241.html While this is fine as far as it goes (it should really be handled within GHC), and does offer some initial speedup, Bulat pointed out that GCC does further optimizations after unrolling, such as reassociating sums to expose potential for constant folding: http://www.haskell.org/pipermail/haskell-cafe/2009-February/056367.html (since the ghc -ddump-simpl output doesn't show this optimization, I assume that gcc handles it, and the "*ghc*" in that message is a typo, but haven't checked - how would I do that, btw?). In this case, GHC optimizations following the loop unrolling leave a sum like (note the repeated variable interspersed with constants) (GHC.Prim.+# (GHC.Prim.+# ww_s1lN 3) (GHC.Prim.+# (GHC.Prim.+# ww_s1lN 2) (GHC.Prim.+# (GHC.Prim.+# ww_s1lN 1) (GHC.Prim.+# (GHC.Prim.+# ww_s1lN 0) ww_s1lR)))))))) which can be simplified (assuming associativity and commutativity of + here..) after sorting the variable references and constants into separate groups. We currently inherit such optimizations when using -fvia-C, even though GHC sometimes produces C code that GCC can't handle optimally. If I understand correctly, -fvia-C is on its way out - is that correct, and what plans are there for recovering the optimizations previously left to GCC? The next thing I was looking at was rewrite rules, the obvious GHC tool for implementing this kind of rule (var+const1)+(var+const2) ==> 2*var + const3 and I ran into more questions: - can RULES left-hand sides test for variables (I don't want to reassociate sums randomly, that wouldn't terminate; instead, I want to float out subterms that are non-variable, and group repeated variables)? - is there any way to control the rewrite strategy, similar to strategy combinators (if rules are applied all over the place, they introduce new structure not covered by rules; if I could limit the strategy to top-down, or bottom-up, I could at least cover some special cases)? - how would one handle this kind of optimization in GHC in full generality? wait for compiler plugins? are there features of rewrite rules that I'm missing? would it make sense to flag rewrite rules system improvements as a GHC GSoC project, given that GHC will have to pull its weight there when moving away from GCC? Claus
Okay, I've found a combination of incantations that happens to work, but only for this particular example. So this does not solve the original questions, and I'm still interested in suggestions. But it does give a concrete example of what I'd like to be able to do (or better, what GHC should be doing, and GCC apparently does), in the hope that this helps the discussion along. This message a bit lengthy, as I try to summarize the approach, for those here who didn't follow the haskell-cafe thread earlier (so this should be fairly self-contained) and include timings. 1. Old things first, the TH macro for syntactic replication of calls to 'f', each call getting its own counter 'i', and 'x' as the first parameter: ------------------------------------------------------------------ {-# LANGUAGE TemplateHaskell #-} module Apply where import Language.Haskell.TH.Syntax apply i bound | i<bound = [| \f x -> $(apply (i+1) bound) f (f i x) |] | otherwise = [| \f x -> x |] ------------------------------------------------------------------ 2. Next, we use this to define an unrolling 'loop' combinator on 'Int', which counts from 'i' to 'max', applying 'body' to the count 'i' and an accumulator 'acc'. Thanks to 'apply' and TH, we can parameterize this code over the number of unrollings 'N' (N=8 here), without having to write out the syntactic unrolling ourselves (this is the only use of TH here, so unlike earlier approaches, we do not implement loop unrolling by any TH-based syntactic analysis, we just syntactically generate a function that will do the unrolling semantically). 'loop' is marked INLINE, and is in a worker/wrapper form, so that the wrapper will be inlined at the call site, bringing the 'body' parameter into scope for the worker, in order to allow GHC to apply further simplifications to the unfolded 'body' applications. ------------------------------------------------------------------ {-# LANGUAGE CPP #-} {-# LANGUAGE TemplateHaskell #-} {-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -DN=8 -ddump-splices #-} module Loop(loop) where import Apply {-# INLINE loop #-} loop :: Int -> Int -> (Int -> Int -> Int) -> Int -> Int loop i max body acc = loopW i acc where loopW :: Int -> Int -> Int loopW !i !acc | i+N<=max = loopW (i+N) ($(apply (0::Int) N) (\j acc->body (i+j) acc) acc) loopW !i !acc | i<=max = loopW (i+1) (body i acc) | otherwise = acc ------------------------------------------------------------------ 3. Finally, the main program, using 'loop' to calculate a simple sum: ------------------------------------------------------------------ {-# LANGUAGE MagicHash #-} module Main where import Loop import GHC.Prim {-# RULES "re-assoc" [~1] forall v x y z. (x+#y)+#(z+#v) = ((x+#y)+#z)+#v "collect1" [1] forall x y. (x+#y)+#x = (2#*#x)+#y "collect2" [1] forall n x y. ((n*#x)+#y)+#x = ((n+#1#)*#x)+#y "collect3" [1] forall n x y z. ((n*#x)+#y)+#z = (n*#x)+#(y+#z) #-} main = print $ loop 1 (10^9) body 0 body :: Int -> Int -> Int body i acc = i+acc ------------------------------------------------------------------ 4. If we ignore the RULES, we note the following: - GHC nicely unrolls the 'loop' and simplifies the both the calls to 'body' and the overhead introduced by our use of 'apply' out of the way, which gives some first improvements in speed, but -fasm is noticeable slower than -fvia-C, so GCC does further optimizations; - a likely candidate are arithmetic laws (associativity/commutativity of '+'), in order to enable constant folding - of the two purposes of loop unrolling, (a) less admin overhead and more straightforward code, (b) enable further optimizations (just like any other unfolding/inlining, but on recursive code), GHC -fasm, even with help from TH, only achieves the first. The interesting bit of core is the one corresponding to the call to 'apply' (for N=8) in the definition of 'loopW' ('ww1_s18W' is the counter variable, 'ww2_s190' is the accumulator): $wloopW_s19d (GHC.Prim.+# ww1_s18W 8) (GHC.Prim.+# (GHC.Prim.+# ww1_s18W 7) (GHC.Prim.+# (GHC.Prim.+# ww1_s18W 6) (GHC.Prim.+# (GHC.Prim.+# ww1_s18W 5) (GHC.Prim.+# (GHC.Prim.+# ww1_s18W 4) (GHC.Prim.+# (GHC.Prim.+# ww1_s18W 3) (GHC.Prim.+# (GHC.Prim.+# ww1_s18W 2) (GHC.Prim.+# (GHC.Prim.+# ww1_s18W 1) (GHC.Prim.+# (GHC.Prim.+# ww1_s18W 0) ww2_s190)))))))) Note the various constants, interspersed with copies of the counter variable. If we could sort those into two separate groups, we could evaluate the sum of constants, and simplify the repeated additions of the counter variable. Which is the bit which I don't know how to do in general fashion. But here's the non-general hack, using RULES: I 'reassoc' reassociates the '+' applications from a tree to a simple linear list II 'collectN' perform the grouping into counter variable and constants (by dead reckoning rather than proper analysis:-( 'collect1' and 'collect2' collect the counter variables, 'collect3' collects the constants III phase control (rather unintuitive, imho) is used to keep the 'reassoc' and 'collectN' rules from interfering with each other, rule order is used to limit the applicability of 'collect3' to expressions which do not match 'collect2''s left-hand side (I think?) II is where I'd like to be able to distinguish variables, constants, and complex expressions in the left-hand sides of RULES, and I and III are where I'd like control over the rewrite strategy, as in strategy combinators. The resulting core, for the same position as before ('ww1_s193' is the counter variable, 'ww2_s197' is the accumulator): $wloopW_s19k (GHC.Prim.+# ww1_s193 8) (GHC.Prim.+# (GHC.Prim.*# 8 ww1_s193) (GHC.Prim.+# 28 ww2_s197)) Nice. But I'd like to get there without cheating, with generally applicable RULES. How? Claus ================================================= PS. Some numbers for general entertainment (times are best of 5, GHC is ghc-6.11.20090118, GCC is 3.4.2 (mingw-special)): ------------------------------------------------------------------ $ ghc --make -O2 -fasm Main.hs -ddump-simpl -fno-enable-rewrite-rules >loop.simpl [3 of 3] Compiling Main ( Main.hs, Main.o ) Linking Main.exe ... $ time ./Main.exe -243309312 real 0m1.080s user 0m0.015s sys 0m0.031s ------------------------------------------------------------------ $ ghc --make -O2 -fasm Main.hs -ddump-simpl >loop.simpl [3 of 3] Compiling Main ( Main.hs, Main.o ) Linking Main.exe ... $ time ./Main.exe -243309312 real 0m0.569s user 0m0.015s sys 0m0.031s ------------------------------------------------------------------ $ ghc --make -O2 -fvia-C Main.hs -ddump-simpl -fno-enable-rewrite-rules >loop.simpl [3 of 3] Compiling Main ( Main.hs, Main.o ) Linking Main.exe ... $ time ./Main.exe -243309312 real 0m0.641s user 0m0.031s sys 0m0.015s ------------------------------------------------------------------ Oh, and that '-fvia-C' does seem to pass '-O2' to GCC, but that does not imply '-funroll-loops': The compiler does not perform loop unrolling or function inlining when you specify -O2. If we repeat the experiment with the unrolling branch in 'loopW' commented out, we don't seem to get unrolling from GCC either (is this a case of GHC-generated code not being palatable to GCC, or am I doing something wrong?), but -fasm is still slower than -fvia-C: ------------------------------------------------------------------ $ ghc --make -O2 -fvia-C Main.hs -ddump-simpl >loop.simpl [1 of 3] Compiling Apply ( Apply.hs, Apply.o ) [2 of 3] Compiling Loop ( Loop.hs, Loop.o ) [3 of 3] Compiling Main ( Main.hs, Main.o ) Linking Main.exe ... $ time ./Main.exe -243309312 real 0m3.437s user 0m0.015s sys 0m0.015s ------------------------------------------------------------------ $ ghc --make -O2 -fvia-C -optc -funroll-loops Main.hs -ddump-simpl >loop.simpl [1 of 3] Compiling Apply ( Apply.hs, Apply.o ) [2 of 3] Compiling Loop ( Loop.hs, Loop.o ) [3 of 3] Compiling Main ( Main.hs, Main.o ) Linking Main.exe ... $ time ./Main.exe -243309312 real 0m3.428s user 0m0.015s sys 0m0.015s ------------------------------------------------------------------ $ ghc --make -O2 -fasm Main.hs -ddump-simpl >loop.simpl [1 of 3] Compiling Apply ( Apply.hs, Apply.o ) [2 of 3] Compiling Loop ( Loop.hs, Loop.o ) [3 of 3] Compiling Main ( Main.hs, Main.o ) Linking Main.exe ... $ time ./Main.exe -243309312 real 0m4.065s user 0m0.015s sys 0m0.015s ------------------------------------------------------------------ So, unrolling gives the main benefit (4.1 -> 1.1), but arithmetic optimizations are still profitable (1.1 -> 0.6). The latter are somewhat application-specific (if the loop operated on a Map, other RULES would apply), but would seem useful (if they could be made to work) independent of loop unrolling. And -fvia-C still tends to be faster than -fasm.
| II is where I'd like to be able to distinguish variables, constants, | and complex expressions in the left-hand sides of RULES, and | I and III are where I'd like control over the rewrite strategy, as | in strategy combinators. I'm deep in icfp submissions, so no time to reply properly. You can distinguish between literals, variables etc, in GHC's BuiltinRules. These are not hard to write: see prelude/PrelRules. But they are built in, not part of the source program. Maybe that's ok, since you are messing with built-in arithmetic. Another avenue is to elaborate the language of rules somehow to let you say what you want. But I don't know a good *spec* for such a feature, let alone an impl. Another possibility is to write a Core-to-Core optimiser aimed at your target area. Max B's plugins would let you dynamically link that to a distributed GHC. But it's not in the HEAD yet... Simon
| II is where I'd like to be able to distinguish variables, constants, | and complex expressions in the left-hand sides of RULES, and | I and III are where I'd like control over the rewrite strategy, as | in strategy combinators.
I'm deep in icfp submissions, so no time to reply properly.
Okay, not urgent, just general concerns about GHC performance, can wait a few days.
You can distinguish between literals, variables etc, in GHC's BuiltinRules.
Not really sufficient. If the loop body was about Maps instead of Ints, different rules would apply. And the same limitations apply for all uses of RULES, which were meant to provide for user-extensible library-specific optimization by transformation.
Another avenue is to elaborate the language of rules somehow to let you say what you want. But I don't know a good *spec* for such a feature, let alone an impl. Another possibility is to write a Core-to-Core optimiser aimed at your target area. Max B's plugins would let you dynamically link that to a distributed GHC. But it's not in the HEAD yet...
My guess would be to start from standard Strafunski/SYB-style traversals over Core as the "semantic API", utilizing compiler plugins. Then look for better syntax, closer to the existing RULES (for a start, something like quasi-quoting, so that left- and right-hand sides of rules can still be written in concrete syntax, even if they are just Haskell function definitions). Then move all RULES to the new framework (to reduce duplication inside GHC, and to provide a single programmer API) and start adding further optimizations to libraries (I wonder: surely others have encountered these limitations when adding RULES for their libraries?). But that is just a guess - as you imply, someone would have to sit down, design, implement, and test. That is why I asked whether it would make a good GSoC topic for GHC HQ (lots of potential, and building on one of last year's topics). Claus
2009/2/24 Claus Reinke <claus.reinke@talk21.com>:
In the recently burried haskell-cafe thread "speed: ghc vs gcc", Bulat pointed out some of the optimizations that GHC doesn't do, such as loop unrolling. I suggested a way of experimenting with loop unrolling, using template haskell to bypass GHC's blindspot (it usually doesn't unfold recursive definitions http://www.haskell.org/pipermail/glasgow-haskell-users/2007-July/012936.html , but if we unfold a loop combinator at compile time, GHC's normal optimizations can take over from there):
http://www.haskell.org/pipermail/haskell-cafe/2009-February/056241.html
Just a note - there is a solution that doesn't require Template Haskell which I use in my own code. Here is a sketch: fact = fix4 fact_worker {-# INLINE fact_worker #-} fact_worker recurse n | n <= 0 = 1 | otherwise = n * recurse (n - 1) {-# INLINE fix4 #-} fix4 f = f1 where f1 = f f2 f2 = f f3 f3 = f f4 f4 = f f1 There is probably a way to generalise this to arbitrary levels of unrolling by using instances of a typeclass on type level numerals. Cheers, Max
but if we unfold a loop combinator at compile time, GHC's normal optimizations can take over from there):
http://www.haskell.org/pipermail/haskell-cafe/2009-February/056241.html
Just a note - there is a solution that doesn't require Template Haskell which I use in my own code. Here is a sketch:
That is in fact the same solution!-) Just that I stayed close to the example in the original thread, hence a fixpoint-combinator with implicit tail-recursion and built-in counter rather than one with explicit general recursion.
fact = fix4 fact_worker
{-# INLINE fact_worker #-} fact_worker recurse n | n <= 0 = 1 | otherwise = n * recurse (n - 1)
{-# INLINE fix4 #-} fix4 f = f1 where f1 = f f2 f2 = f f3 f3 = f f4 f4 = f f1
There is probably a way to generalise this to arbitrary levels of unrolling by using instances of a typeclass on type level numerals.
Semantically, one could compute the nested application without meta-level help, but that involves another recursive definition, which GHC won't unfold during compilation. So I used TH, just to generate the equivalent to the 'fixN' definition. Since only the fixpoint/loop combinators need to be unfolded statically, one could indeed do it by hand, for a suitable range of unfolding depths, and provide them as a library. Claus
participants (3)
-
Claus Reinke -
Max Bolingbroke -
Simon Peyton-Jones