Add notes about rewrite
[nofib.git] / Simon-nofib-notes
1         --------------------------------------------
2                 Notes on nofib programs
3         --------------------------------------------
4
5 Every time I do performance tuning on GHC I re-discover wrinkles in
6 particular nofib programs.   I intend to record these wrinkles herein.
7
8
9 NOTE: With 4.09 we introduced Unicode.  That means that (C# x) always allocates,
10 whereas it didn't before.  So allocations go up a bit.
11
12 ---------------------------------------
13         Imaginary suite
14 ---------------------------------------
15
16
17 gen_regexps
18 ~~~~~~~~~~~
19 I found that there were some very bad loss-of-arity cases in PrelShow.  
20   In particular, we had:
21
22         showl ""       = showChar '"' s
23         showl ('"':xs) = showString "\\\"" . showl xs
24         showl (x:xs)   = showLitChar x . showl xs
25
26   Trouble is, we get
27         showl = \xs -> case xs of
28                           ...
29                           (x:xs) -> let f = showLitChar x
30                                         g = showl xs
31                                     in \s -> f (g x)
32   which is TERRIBLE.  We can't spot that showLitChar has arity 2 because
33   it looks like this:
34
35         ...other eqns...
36         showLitChar c = showString ('\\' : asciiTab!!ord c)
37
38   notice that the (asciiTab!!orc c) is outside the \s, so GHC can't rewrite it to
39
40         showLitChar c =  \s -> showString ('\\' : asciiTab!!ord c) s
41
42   So I've changed PrelShow.showLitChar to use explicit \s.  Even then, showl
43   doesn't work, because GHC can't see that showl xs can be pushed inside the \s.
44   So I've put an explict \s there too.  
45
46         showl ""       s = showChar '"' s
47         showl ('"':xs) s = showString "\\\"" (showl xs s)
48         showl (x:xs)   s = showLitChar x (showl xs s)
49
50   Net result: imaginary/gen_regexps more than halves in allocation!
51
52
53 x2n1
54 ~~~~
55
56 Relies quite heavily on specialisations for Num (Complex Double).  If
57 this test suddenly gets worse by a factor of 2 or so, chances are that
58 specialisation is broken.
59
60 ---------------------------------------
61         Spectral suite
62 ---------------------------------------
63
64 rewrite
65 ~~~~~~~
66 It's important to inline p_ident.
67
68 There's a very delicate CSE in p_expr
69    p_expr = seQ q_op [p_term1, p_op, p_term2] ## p_term3
70
71 (where all the pterm1,2,3 are really just p_term).  
72
73 This expands into
74    p_expr s = case p_term1 s of
75                 Nothing -> p_term3 s
76                 Just (v,s') -> case p_op s' of ...
77                                  Nothing -> p_term3 s
78
79 Notice that if the bit before (##) fails, we call p_term3 s, and if
80 CSE notices we can re-use the result of the first call.  But that
81 depends on how much inlining takes place.  In particular, the follow-up
82 calls p_term3 can get hidden inside join points, which don't "see" the first
83 call.
84
85
86
87 cse
88 ~~~
89 The functions 'go' and 'go1', called from draw, get arity 1, but they
90 should get arity 2. We need a better arity analysis, a la Gill. 'go' looks
91 like this:
92     go_r1og =
93       \ (ds_aGI :: [GHC.Base.Char]) ->
94         case ds_aGI of wild_aGJ {
95           [] -> z_r1oe;
96           : y_aGN ys_aGO ->
97         let {
98           xs7_s1i8 :: GHC.Prim.Int# -> [GHC.Base.Char]
99           [Str: DmdType]
100           xs7_s1i8 = go_r1og ys_aGO
101         } in 
102           \ (m_XWf :: GHC.Prim.Int#) ->
103             case GHC.Prim.<=# m_XWf 1 of wild1_aSI {
104               GHC.Base.False ->
105                 GHC.Base.: @ GHC.Base.Char y_aGN (xs7_s1i8 (GHC.Prim.-# m_XWf 1));
106               GHC.Base.True -> GHC.Base.: @ GHC.Base.Char y_aGN lvl13_r1n0
107             }
108         }
109 Notice the 'let' which stops the lambda moving out.
110
111
112 Eliza
113 ~~~~~
114 In June 2002, GHC 5.04 emitted four successive
115     NOTE: Simplifier still going after 4 iterations; bailing out.
116 messages.  I suspect that the simplifer is looping somehow.
117
118
119 Expert
120 ~~~~~~
121 In spectral/expert/Search.ask there's a statically visible CSE. Catching this 
122 depends almost entirely on chance, which is a pity.
123
124
125 Fish
126 ~~~~
127 The performance of fish depends crucially on inlining scale_vec2.
128 It turns out to be right on the edge of GHC's normal threshold size, so
129 small changes to the compiler can knock it to and fro.
130
131
132 Integer
133 ~~~~~~~
134 A good benchmark for beating on big-integer arithmetic
135
136 Knights
137 ~~~~~~~
138 In knights/KnightHeuristic, we don't find that possibleMoves is strict
139 (with important knock-on effects) unless we apply rules before floating
140 out the literal list [A,B,C...].
141 Similarly, in f_se (F_Cmp ...) in listcompr (but a smaller effect)
142
143
144 Lambda
145 ~~~~~~
146 This program shows the cost of the non-eta-expanded lambdas that arise from
147 a state monad.  
148
149 Mandel
150 ~~~~~~
151 Relies heavily on having a specialised version of Complex.magnitude
152 (:: Complex Double -> Double) available.
153
154 Mandel.mandelset has a go-loop inside an enumDeltaToIntegerFB, out of which
155 4.08.2 managed to float a constant expression, but HEAD did not.  I think
156 this is because the pre-let-floating simplification did too little inlining;
157 in particular, it did not inline windowToViewport
158
159
160 Multiplier
161 ~~~~~~~~~~
162 In spectral/multiplier, we have 
163     xor = lift21 forceBit f
164       where f :: Bit -> Bit -> Bit
165             f 0 0 = 0
166             f 0 1 = 1
167             f 1 0 = 1
168             f 1 1 = 0
169   Trouble is, f is CPR'd, and that means that instead of returning
170   the constants I# 0, I# 1, it returns 0,1 and then boxes them.
171   So allocation goes up.  I don't see a way around this.
172
173
174 Parstof
175 ~~~~~~~
176 spectral/hartel/parstof ends up saying
177         case (unpackCString "x") of { c:cs -> ... }
178   quite a bit.   We should spot these and behave accordingly.
179
180
181 Power
182 ~~~~~
183 With GHC 4.08, for some reason the arithmetic defaults to Double.  The
184 right thing is to default to Rational, which accounts for the big increase
185 in runtime after 4.08
186
187
188 Puzzle
189 ~~~~~~
190 The main function is 'transfer'.  It has some complicated join points, and
191 I found that in my experimental proto 4.09 compiler I had 
192
193         let ds = go xs in
194         let $j = .... ds ... in
195         case e of
196           p1 -> $j
197           p2 -> $j
198           p3 -> ds
199
200 But ds wasn't getting inlined because we couldn't spot that it was actually
201 only being used once.   Keith's analyser should find this!
202
203
204 Also, making concat into a good producer made a large gain.
205
206 My proto 4.09 still allocates more, partly because of more full laziness relative
207 to 4.08; I don't know why that happens
208
209 Extra allocation is happening in 5.02 as well; perhaps for the same reasons.  There is 
210 at least one instance of floating that prevents fusion; namely the enumerated lists
211 in 'transfer'.
212
213 Sphere
214 ~~~~~~
215 A key function is vecsub, which looks like this (after w/w)
216
217 $wvecsub
218   = \ ww :: Double  ww1 :: Double ww2 :: Double
219       ww3 :: Double ww4 :: Double ww5 :: Double ->
220         let { a = case ww of wild { D# x ->
221                   case ww3 of wild1 { D# y ->
222                   let { a1 = -## x y
223                   } in  $wD# a1
224                   } } } in
225         let { a1 = case ww1 of wild { D# x ->
226                    case ww4 of wild1 { D# y ->
227                    let { a2 = -## x y
228                    } in  $wD# a2
229                    } } } in
230         let { a2 = case ww2 of wild { D# x ->
231                    case ww5 of wild1 { D# y ->
232                    let { a3 = -## x y
233                    } in  $wD# a3
234                    } } 
235         } in  (# a, a1, a2 #)
236
237 Currently it gets guidance: IF_ARGS 6 [2 2 2 2 2 2] 25 4
238 It occurs in a context like
239
240         case $wvecsub a b c d e f of  (# p, q, r #) ->
241         case p of                     D# p' ->
242         case q of                     D# q' ->
243         case r of                     D# r' ->
244
245 So it would be much, much better to inline it.  But the result-discounting
246 doesn't "see" that the three results are each taken apart, and that's the
247 problem.
248
249 One question is this: why did minusDouble get inlined? If it didn't then
250 $vecsub would look much smaller:
251
252 $wvecsub
253   = \ ww :: Double  ww1 :: Double ww2 :: Double
254       ww3 :: Double ww4 :: Double ww5 :: Double ->
255         let { a  = minusDouble ww  ww3 } in
256         let { a1 = minusDouble ww1 ww4 } in
257         let { a2 = minusDouble ww2 ww5 } in
258         (# a, a1, a2 #)
259
260 Reason minusDouble gets inlined: because we are trying to get update in place.
261 So I added a flag -funfolding-update-in-place to enable this "optimisation".
262 Omitting the flag gives much better inlining for $wvecsub at least.
263
264
265 Sphere also does 60,000 calls to hPutStr, so I/O plays a major role.  Currently
266 this I/O does a *lot* of allocation, much of it since the adddition of thread-safety.
267
268
269 Treejoin
270 ~~~~~~~~
271 Does a lot of IO.readFile.
272
273 ---------------------------------------
274         Real suite
275 ---------------------------------------
276
277
278         
279 Maillist
280 ~~~~~~~~
281
282 Uses appendFile repeatedly rather than opening the output file once,
283 which leads to numerous file opens/closes.  Allocations will rise with
284 the new I/O subsystem in 5.02 because the I/O buffer will be
285 re-allocated on the heap for each open, whereas previously it would be
286 allocated on the C heap and therefore not show up in the stats.