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