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