[project @ 2002-06-06 16:02:25 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 Integer
122 ~~~~~~~
123 A good benchmark for beating on big-integer arithmetic
124
125 Lambda
126 ~~~~~~
127 This program shows the cost of the non-eta-expanded lambdas that arise from
128 a state monad.  
129
130 Puzzle
131 ~~~~~~
132 The main function is 'transfer'.  It has some complicated join points, and
133 I found that in my experimental proto 4.09 compiler I had 
134
135         let ds = go xs in
136         let $j = .... ds ... in
137         case e of
138           p1 -> $j
139           p2 -> $j
140           p3 -> ds
141
142 But ds wasn't getting inlined because we couldn't spot that it was actually
143 only being used once.   Keith's analyser should find this!
144
145
146 Also, making concat into a good producer made a large gain.
147
148 My proto 4.09 still allocates more, partly because of more full laziness relative
149 to 4.08; I don't know why that happens
150
151 Extra allocation is happening in 5.02 as well; perhaps for the same reasons.  There is 
152 at least one instance of floating that prevents fusion; namely the enumerated lists
153 in 'transfer'.
154
155 Sphere
156 ~~~~~~
157 A key function is vecsub, which looks like this (after w/w)
158
159 $wvecsub
160   = \ ww :: Double  ww1 :: Double ww2 :: Double
161       ww3 :: Double ww4 :: Double ww5 :: Double ->
162         let { a = case ww of wild { D# x ->
163                   case ww3 of wild1 { D# y ->
164                   let { a1 = -## x y
165                   } in  $wD# a1
166                   } } } in
167         let { a1 = case ww1 of wild { D# x ->
168                    case ww4 of wild1 { D# y ->
169                    let { a2 = -## x y
170                    } in  $wD# a2
171                    } } } in
172         let { a2 = case ww2 of wild { D# x ->
173                    case ww5 of wild1 { D# y ->
174                    let { a3 = -## x y
175                    } in  $wD# a3
176                    } } 
177         } in  (# a, a1, a2 #)
178
179 Currently it gets guidance: IF_ARGS 6 [2 2 2 2 2 2] 25 4
180 It occurs in a context like
181
182         case $wvecsub a b c d e f of  (# p, q, r #) ->
183         case p of                     D# p' ->
184         case q of                     D# q' ->
185         case r of                     D# r' ->
186
187 So it would be much, much better to inline it.  But the result-discounting
188 doesn't "see" that the three results are each taken apart, and that's the
189 problem.
190
191 One question is this: why did minusDouble get inlined? If it didn't then
192 $vecsub would look much smaller:
193
194 $wvecsub
195   = \ ww :: Double  ww1 :: Double ww2 :: Double
196       ww3 :: Double ww4 :: Double ww5 :: Double ->
197         let { a  = minusDouble ww  ww3 } in
198         let { a1 = minusDouble ww1 ww4 } in
199         let { a2 = minusDouble ww2 ww5 } in
200         (# a, a1, a2 #)
201
202 Reason minusDouble gets inlined: because we are trying to get update in place.
203 So I added a flag -funfolding-update-in-place to enable this "optimisation".
204 Omitting the flag gives much better inlining for $wvecsub at least.
205
206
207 Sphere also does 60,000 calls to hPutStr, so I/O plays a major role.  Currently
208 this I/O does a *lot* of allocation, much of it since the adddition of thread-safety.
209
210
211 Treejoin
212 ~~~~~~~~
213 Does a lot of IO.readFile.
214
215 ---------------------------------------
216         Real suite
217 ---------------------------------------
218
219
220         
221 Maillist
222 ~~~~~~~~
223
224 Uses appendFile repeatedly rather than opening the output file once,
225 which leads to numerous file opens/closes.  Allocations will rise with
226 the new I/O subsystem in 5.02 because the I/O buffer will be
227 re-allocated on the heap for each open, whereas previously it would be
228 allocated on the C heap and therefore not show up in the stats.