[project @ 2002-04-01 13:58:09 by simonpj]
[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 Mandel
65 ~~~~~~
66 Relies heavily on having a specialised version of Complex.magnitude
67 (:: Complex Double -> Double) available.
68
69 Multiplier
70 ~~~~~~~~~~
71 In spectral/multiplier, we have 
72     xor = lift21 forceBit f
73       where f :: Bit -> Bit -> Bit
74             f 0 0 = 0
75             f 0 1 = 1
76             f 1 0 = 1
77             f 1 1 = 0
78   Trouble is, f is CPR'd, and that means that instead of returning
79   the constants I# 0, I# 1, it returns 0,1 and then boxes them.
80   So allocation goes up.  I don't see a way around this.
81
82
83 Mandel
84 ~~~~~~
85 Mandel.mandelset has a go-loop inside an enumDeltaToIntegerFB, out of which
86 4.08.2 managed to float a constant expression, but HEAD did not.  I think
87 this is because the pre-let-floating simplification did too little inlining;
88 in particular, it did not inline windowToViewport
89
90
91
92 Parstof
93 ~~~~~~~
94 spectral/hartel/parstof ends up saying
95         case (unpackCString "x") of { c:cs -> ... }
96   quite a bit.   We should spot these and behave accordingly.
97
98
99 Knights
100 ~~~~~~~
101 In knights/KnightHeuristic, we don't find that possibleMoves is strict
102 (with important knock-on effects) unless we apply rules before floating
103 out the literal list [A,B,C...].
104 Similarly, in f_se (F_Cmp ...) in listcompr (but a smaller effect)
105
106
107 Expert
108 ~~~~~~
109 In spectral/expert/Search.ask there's a statically visible CSE. Catching this 
110 depends almost entirely on chance, which is a pity.
111
112
113
114 Fish
115 ~~~~
116 The performance of fish depends crucially on inlining scale_vec2.
117 It turns out to be right on the edge of GHC's normal threshold size, so
118 small changes to the compiler can knock it to and fro.
119
120
121 Puzzle
122 ~~~~~~
123 The main function is 'transfer'.  It has some complicated join points, and
124 I found that in my experimental proto 4.09 compiler I had 
125
126         let ds = go xs in
127         let $j = .... ds ... in
128         case e of
129           p1 -> $j
130           p2 -> $j
131           p3 -> ds
132
133 But ds wasn't getting inlined because we couldn't spot that it was actually
134 only being used once.   Keith's analyser should find this!
135
136
137 Also, making concat into a good producer made a large gain.
138
139 My proto 4.09 still allocates more, partly because of more full laziness relative
140 to 4.08; I don't know why that happens
141
142 Extra allocation is happening in 5.02 as well; perhaps for the same reasons.  There is 
143 at least one instance of floating that prevents fusion; namely the enumerated lists
144 in 'transfer'.
145
146 Sphere
147 ~~~~~~
148 A key function is vecsub, which looks like this (after w/w)
149
150 $wvecsub
151   = \ ww :: Double  ww1 :: Double ww2 :: Double
152       ww3 :: Double ww4 :: Double ww5 :: Double ->
153         let { a = case ww of wild { D# x ->
154                   case ww3 of wild1 { D# y ->
155                   let { a1 = -## x y
156                   } in  $wD# a1
157                   } } } in
158         let { a1 = case ww1 of wild { D# x ->
159                    case ww4 of wild1 { D# y ->
160                    let { a2 = -## x y
161                    } in  $wD# a2
162                    } } } in
163         let { a2 = case ww2 of wild { D# x ->
164                    case ww5 of wild1 { D# y ->
165                    let { a3 = -## x y
166                    } in  $wD# a3
167                    } } 
168         } in  (# a, a1, a2 #)
169
170 Currently it gets guidance: IF_ARGS 6 [2 2 2 2 2 2] 25 4
171 It occurs in a context like
172
173         case $wvecsub a b c d e f of  (# p, q, r #) ->
174         case p of                     D# p' ->
175         case q of                     D# q' ->
176         case r of                     D# r' ->
177
178 So it would be much, much better to inline it.  But the result-discounting
179 doesn't "see" that the three results are each taken apart, and that's the
180 problem.
181
182 One question is this: why did minusDouble get inlined? If it didn't then
183 $vecsub would look much smaller:
184
185 $wvecsub
186   = \ ww :: Double  ww1 :: Double ww2 :: Double
187       ww3 :: Double ww4 :: Double ww5 :: Double ->
188         let { a  = minusDouble ww  ww3 } in
189         let { a1 = minusDouble ww1 ww4 } in
190         let { a2 = minusDouble ww2 ww5 } in
191         (# a, a1, a2 #)
192
193 Reason minusDouble gets inlined: because we are trying to get update in place.
194 So I added a flag -funfolding-update-in-place to enable this "optimisation".
195 Omitting the flag gives much better inlining for $wvecsub at least.
196
197
198 Sphere also does 60,000 calls to hPutStr, so I/O plays a major role.  Currently
199 this I/O does a *lot* of allocation, much of it since the adddition of thread-safety.
200
201
202 Treejoin
203 ~~~~~~~~
204 Does a lot of IO.readFile.
205
206 ---------------------------------------
207         Real suite
208 ---------------------------------------
209
210
211         
212 Maillist
213 ~~~~~~~~
214
215 Uses appendFile repeatedly rather than opening the output file once,
216 which leads to numerous file opens/closes.  Allocations will rise with
217 the new I/O subsystem in 5.02 because the I/O buffer will be
218 re-allocated on the heap for each open, whereas previously it would be
219 allocated on the C heap and therefore not show up in the stats.