Add digits-of-e2.faststdout
[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 integrate
17 ~~~~~~~~~
18 integrate1D is strict in its second argument 'u', but it also passes 'u' to
19 function 'f'.  Hence it now does some reboxing, which pushes up allocation
20 slightly.
21
22 gen_regexps
23 ~~~~~~~~~~~
24 I found that there were some very bad loss-of-arity cases in PrelShow.  
25   In particular, we had:
26
27         showl ""       = showChar '"' s
28         showl ('"':xs) = showString "\\\"" . showl xs
29         showl (x:xs)   = showLitChar x . showl xs
30
31   Trouble is, we get
32         showl = \xs -> case xs of
33                           ...
34                           (x:xs) -> let f = showLitChar x
35                                         g = showl xs
36                                     in \s -> f (g s)
37   which is TERRIBLE.  We can't spot that showLitChar has arity 2 because
38   it looks like this:
39
40         ...other eqns...
41         showLitChar c = showString ('\\' : asciiTab!!ord c)
42
43   notice that the (asciiTab!!orc c) is outside the \s, so GHC can't rewrite it to
44
45         showLitChar c =  \s -> showString ('\\' : asciiTab!!ord c) s
46
47   So I've changed PrelShow.showLitChar to use explicit \s.  Even then, showl
48   doesn't work, because GHC can't see that showl xs can be pushed inside the \s.
49   So I've put an explict \s there too.  
50
51         showl ""       s = showChar '"' s
52         showl ('"':xs) s = showString "\\\"" (showl xs s)
53         showl (x:xs)   s = showLitChar x (showl xs s)
54
55   Net result: imaginary/gen_regexps more than halves in allocation!
56
57 queens
58 ~~~~~~
59 If we do
60  a) some inlining before float-out
61  b) fold/build fusion before float-out
62 then queens get 40% more allocation.  Presumably the fusion 
63 prevents sharing.
64
65
66 x2n1
67 ~~~~
68
69 Relies quite heavily on specialisations for Num (Complex Double).  If
70 this test suddenly gets worse by a factor of 2 or so, chances are that
71 specialisation is broken.
72
73 ---------------------------------------
74         Spectral suite
75 ---------------------------------------
76
77 rewrite
78 ~~~~~~~
79 It's important to inline p_ident.
80
81 There's a very delicate CSE in p_expr
82    p_expr = seQ q_op [p_term1, p_op, p_term2] ## p_term3
83
84 (where all the pterm1,2,3 are really just p_term).  
85
86 This expands into
87    p_expr s = case p_term1 s of
88                 Nothing -> p_term3 s
89                 Just (v,s') -> case p_op s' of ...
90                                  Nothing -> p_term3 s
91
92 Notice that if the bit before (##) fails, we call p_term3 s, and if
93 CSE notices we can re-use the result of the first call.  But that
94 depends on how much inlining takes place.  In particular, the follow-up
95 calls p_term3 can get hidden inside join points, which don't "see" the first
96 call.
97
98
99
100 cse
101 ~~~
102 The functions 'go' and 'go1', called from draw, get arity 1, but they
103 should get arity 2. We need a better arity analysis, a la Gill. 'go' looks
104 like this:
105     go_r1og =
106       \ (ds_aGI :: [GHC.Base.Char]) ->
107         case ds_aGI of wild_aGJ {
108           [] -> z_r1oe;
109           : y_aGN ys_aGO ->
110         let {
111           xs7_s1i8 :: GHC.Prim.Int# -> [GHC.Base.Char]
112           [Str: DmdType]
113           xs7_s1i8 = go_r1og ys_aGO
114         } in 
115           \ (m_XWf :: GHC.Prim.Int#) ->
116             case GHC.Prim.<=# m_XWf 1 of wild1_aSI {
117               GHC.Base.False ->
118                 GHC.Base.: @ GHC.Base.Char y_aGN (xs7_s1i8 (GHC.Prim.-# m_XWf 1));
119               GHC.Base.True -> GHC.Base.: @ GHC.Base.Char y_aGN lvl13_r1n0
120             }
121         }
122 Notice the 'let' which stops the lambda moving out.
123
124
125 eliza
126 ~~~~~
127 In June 2002, GHC 5.04 emitted four successive
128     NOTE: Simplifier still going after 4 iterations; bailing out.
129 messages.  I suspect that the simplifier is looping somehow.
130
131 fibheaps
132 ~~~~~~~~
133 If you don't inline getChildren, allocation rises by 25%
134
135 hartel/event
136 ~~~~~~~~~~~~
137 There's a functions called f_nand and f_d, which generates tons of
138 code if you inline them too vigorously.  And this can happen because
139 of a massive result discount.
140
141 Moreover if f_d gets inlined too much, you get lots of local lvl_xx
142 things which make some closures have lots of free variables, which pushes
143 up allocation.
144
145 expert
146 ~~~~~~
147 In spectral/expert/Search.ask there's a statically visible CSE. Catching this 
148 depends almost entirely on chance, which is a pity.
149
150 reptile
151 ~~~~~~~
152 Performance dominated by (++) and Show.itos'
153
154 fish
155 ~~~~
156 The performance of fish depends crucially on inlining scale_vec2.
157 It turns out to be right on the edge of GHC's normal threshold size, so
158 small changes to the compiler can knock it to and fro.
159
160 [Sept 08]  The new instance-declaration story makes show slightly worse.
161 Look at Main.showl in the simplified core.  You'll see this:
162
163   a79_aRZ :: GHC.Types.Int
164              -> (GHC.Types.Int, GHC.Types.Int, GHC.Types.Int, GHC.Types.Int)
165              -> GHC.Show.ShowS
166   [Str: DmdType]
167   a79_aRZ =
168     GHC.Show.showsPrec9 @ Int @ Int @ Int @ Int
169           GHC.Show.$f16 GHC.Show.$f16 GHC.Show.$f16 GHC.Show.$f16
170
171   Rec {
172   showl_sWK :: [Main.Line_segment] -> String -> String
173   [Arity 2
174    Str: DmdType SL]
175   showl_sWK =
176     \ (ds_dQJ :: [Main.Line_segment]) (s_alB :: GHC.Base.String) ->
177       case ds_dQJ of wild_X1d [ALWAYS Just A] {
178         [] -> GHC.Types.: @ GHC.Types.Char lvl_sYT s_alB;
179         : x_alD [ALWAYS Just L] xs_alF [ALWAYS Just L] ->
180           GHC.Base.++
181             @ GHC.Types.Char
182             a_s12R
183             (a79_aRZ a_s1uS x_alD (showl_sWK xs_alF s_alB))
184       }
185   end Rec }
186
187 Note the non-inlined call to GHC.Show.showsPrec9, which looks like this:
188   showsPrec9 :: forall a b c d. (Show a, Show b, Show c, Show d) =>
189                 GHC.Types.Int -> (a, b, c, d) -> GHC.Show.ShowS
190     {- Arity: 4 Strictness: LLLL
191        Unfolding: (\ @ a b c d
192                      $dShow :: GHC.Show.Show a
193                      $dShow1 :: GHC.Show.Show b
194                      $dShow2 :: GHC.Show.Show c
195                      $dShow3 :: GHC.Show.Show d ->
196                    let {
197                      shows1 :: d -> GHC.Show.ShowS = GHC.Show.shows @ d $dShow3
198                    } in
199                    let {
200                      shows2 :: c -> GHC.Show.ShowS = GHC.Show.shows @ c $dShow2
201                    } in
202                    let {
203                      shows3 :: b -> GHC.Show.ShowS = GHC.Show.shows @ b $dShow1
204                    } in
205                    let {
206                      shows4 :: a -> GHC.Show.ShowS = GHC.Show.shows @ a $dShow
207                    } in
208                    \ ds :: GHC.Types.Int ds1 :: (a, b, c, d) s :: GHC.Base.String ->
209                    case @ GHC.Base.String ds1 of wild { (a79, b, c, d) ->
210                    GHC.Show.show_tuple
211                      (GHC.Types.:
212                         @ GHC.Show.ShowS
213                         (shows4 a79)
214                         (GHC.Types.:
215                            @ GHC.Show.ShowS
216                            (shows3 b)
217                            (GHC.Types.:
218                               @ GHC.Show.ShowS
219                               (shows2 c)
220                               (GHC.Types.:
221                                  @ GHC.Show.ShowS
222                                  (shows1 d)
223                                  (GHC.Types.[] @ GHC.Show.ShowS)))))
224                      s }) -}
225
226 We would do better to inpline showsPrec9 but it looks too big.  Before
227 it was inlined regardless by the instance-decl stuff.  So perf drops slightly.
228
229
230 integer
231 ~~~~~~~
232 A good benchmark for beating on big-integer arithmetic.
233 In this function:
234
235   integerbench :: (Integer -> Integer -> a)
236                -> Integer -> Integer -> Integer
237                -> Integer -> Integer -> Integer
238                -> IO ()
239   integerbench op astart astep alim bstart bstep blim = do
240     seqlist ([ a `op` b
241            | a <- [ astart,astart+astep..alim ]
242            , b <- [ bstart,astart+bstep..blim ]])
243     return ()
244
245 if you do a bit of inlining and rule firing before floating, we'll fuse
246 the comprehension with the [bstart, astart+bstep..blim], whereas if you
247 float first you'll share the [bstart...] list. The latter does 11% less
248 allocation, but more case analysis etc.
249
250 knights
251 ~~~~~~~
252 * In knights/KnightHeuristic, we don't find that possibleMoves is strict
253   (with important knock-on effects) unless we apply rules before floating
254   out the literal list [A,B,C...].
255
256 * Similarly, in f_se (F_Cmp ...) in listcompr (but a smaller effect)
257
258 * If we don't inline $wmove, we get an allocation increase of 17%
259
260
261 lambda
262 ~~~~~~
263 This program shows the cost of the non-eta-expanded lambdas that arise from
264 a state monad.  
265
266 mandel2
267 ~~~~~~~
268 check_perim's several calls to point_colour lead to opportunities for CSE
269 which may be more or less well taken.
270
271 mandel
272 ~~~~~~
273 Relies heavily on having a specialised version of Complex.magnitude
274 (:: Complex Double -> Double) available.
275
276 Mandel.mandelset has a go-loop inside an enumDeltaToIntegerFB, out of which
277 4.08.2 managed to float a constant expression, but HEAD did not.  I think
278 this is because the pre-let-floating simplification did too little inlining;
279 in particular, it did not inline windowToViewport
280
281
282 multiplier
283 ~~~~~~~~~~
284 In spectral/multiplier, we have 
285     xor = lift21 forceBit f
286       where f :: Bit -> Bit -> Bit
287             f 0 0 = 0
288             f 0 1 = 1
289             f 1 0 = 1
290             f 1 1 = 0
291   Trouble is, f is CPR'd, and that means that instead of returning
292   the constants I# 0, I# 1, it returns 0,1 and then boxes them.
293   So allocation goes up.  I don't see a way around this.
294
295
296 hartel/partsof
297 ~~~~~~~~~~~~~~
298 spectral/hartel/parstof ends up saying
299         case (unpackCString "x") of { c:cs -> ... }
300   quite a bit.   We should spot these and behave accordingly.
301
302
303 power
304 ~~~~~
305 With GHC 4.08, for some reason the arithmetic defaults to Double.  The
306 right thing is to default to Rational, which accounts for the big increase
307 in runtime after 4.08
308
309
310 puzzle
311 ~~~~~~
312 The main function is 'transfer'.  It has some complicated join points, and
313 a big issue is the full laziness can float out many small MFEs that then 
314 make much bigger closures.  It's quite delicate: small changes can make
315 big differences, and I spent far too long gazing at it.
316
317 I found that in my experimental proto 4.09 compiler I had 
318
319         let ds = go xs in
320         let $j = .... ds ... in
321         case e of
322           p1 -> $j
323           p2 -> $j
324           p3 -> ds
325
326 But ds wasn't getting inlined because we couldn't spot that it was actually
327 only being used once.   Keith's analyser should find this!
328
329
330 Also, making concat into a good producer made a large gain.
331
332 My proto 4.09 still allocates more, partly because of more full laziness relative
333 to 4.08; I don't know why that happens
334
335 Extra allocation is happening in 5.02 as well; perhaps for the same reasons.  There is 
336 at least one instance of floating that prevents fusion; namely the enumerated lists
337 in 'transfer'.
338
339 sphere
340 ~~~~~~
341 A key function is vecsub, which looks like this (after w/w)
342
343 $wvecsub
344   = \ ww :: Double  ww1 :: Double ww2 :: Double
345       ww3 :: Double ww4 :: Double ww5 :: Double ->
346         let { a = case ww of wild { D# x ->
347                   case ww3 of wild1 { D# y ->
348                   let { a1 = -## x y
349                   } in  $wD# a1
350                   } } } in
351         let { a1 = case ww1 of wild { D# x ->
352                    case ww4 of wild1 { D# y ->
353                    let { a2 = -## x y
354                    } in  $wD# a2
355                    } } } in
356         let { a2 = case ww2 of wild { D# x ->
357                    case ww5 of wild1 { D# y ->
358                    let { a3 = -## x y
359                    } in  $wD# a3
360                    } } 
361         } in  (# a, a1, a2 #)
362
363 Currently it gets guidance: IF_ARGS 6 [2 2 2 2 2 2] 25 4
364 It occurs in a context like
365
366         case $wvecsub a b c d e f of  (# p, q, r #) ->
367         case p of                     D# p' ->
368         case q of                     D# q' ->
369         case r of                     D# r' ->
370
371 So it would be much, much better to inline it.  But the result-discounting
372 doesn't "see" that the three results are each taken apart, and that's the
373 problem.
374
375 One question is this: why did minusDouble get inlined? If it didn't then
376 $vecsub would look much smaller:
377
378 $wvecsub
379   = \ ww :: Double  ww1 :: Double ww2 :: Double
380       ww3 :: Double ww4 :: Double ww5 :: Double ->
381         let { a  = minusDouble ww  ww3 } in
382         let { a1 = minusDouble ww1 ww4 } in
383         let { a2 = minusDouble ww2 ww5 } in
384         (# a, a1, a2 #)
385
386 Reason minusDouble gets inlined: because we are trying to get update in place.
387 So I added a flag -funfolding-update-in-place to enable this "optimisation".
388 Omitting the flag gives much better inlining for $wvecsub at least.
389
390
391 Sphere also does 60,000 calls to hPutStr, so I/O plays a major role.  Currently
392 this I/O does a *lot* of allocation, much of it since the addition of thread-safety.
393
394
395 treejoin
396 ~~~~~~~~
397 Does a lot of IO.readFile.  In GHC.IO.Encoding.UTF8 the demand
398 analyser sees a strict function with type
399  a_s1gj :: GHC.IO.Buffer.Buffer GHC.Word.Word8
400         -> GHC.IO.Buffer.Buffer GHC.Types.Char
401         -> GHC.Prim.State# GHC.Prim.RealWorld
402         -> (# GHC.Prim.State# GHC.Prim.RealWorld,
403               (GHC.IO.Encoding.Types.CodingProgress,
404                GHC.IO.Buffer.Buffer GHC.Word.Word8,
405                GHC.IO.Buffer.Buffer GHC.Types.Char) #)
406 Unboxing both Buffer arguments makes a HUGE difference (halves
407 allocation); but that makes the worker function have 12 arguments.  A
408 good reason for unboxing even if the worker gets a lot of args.
409
410 sorting
411 ~~~~~~~
412 Same issue with GHC.IO.Encoding.UTF8 as treejoin
413
414
415 ---------------------------------------
416         Real suite
417 ---------------------------------------
418
419 cacheprof
420 ~~~~~~~~~
421 Sucessive runs with the same data can yield different allocation
422 totals, for some reason.
423 Reported at https://ghc.haskell.org/trac/ghc/ticket/8611
424
425 gg
426 ~~
427 Same issue with GHC.IO.Encoding.UTF8 as treejoin
428
429 Maillist
430 ~~~~~~~~
431 Uses appendFile repeatedly rather than opening the output file once,
432 which leads to numerous file opens/closes.  Allocations will rise with
433 the new I/O subsystem in 5.02 because the I/O buffer will be
434 re-allocated on the heap for each open, whereas previously it would be
435 allocated on the C heap and therefore not show up in the stats.
436
437 ---------------------------------------
438         Shootout suite
439 ---------------------------------------
440
441 binary-tree
442 ~~~~~~~~~~~
443
444 In May 2016, a series of seemingly unrelated commits changed the runtime
445 performance of this up and down by ~3%. Maybe a performance cliff. Mailinglist
446 thread:
447 https://mail.haskell.org/pipermail/ghc-devs/2017-March/013886.html