[project @ 2001-11-27 12:18:11 by simonmar]
[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 Parstof
84 ~~~~~~~
85 spectral/hartel/parstof ends up saying
86         case (unpackCString "x") of { c:cs -> ... }
87   quite a bit.   We should spot these and behave accordingly.
88
89
90 Knights
91 ~~~~~~~
92 In knights/KnightHeuristic, we don't find that possibleMoves is strict
93 (with important knock-on effects) unless we apply rules before floating
94 out the literal list [A,B,C...].
95 Similarly, in f_se (F_Cmp ...) in listcompr (but a smaller effect)
96
97
98 Expert
99 ~~~~~~
100 In spectral/expert/Search.ask there's a statically visible CSE. Catching this 
101 depends almost entirely on chance, which is a pity.
102
103
104
105 Fish
106 ~~~~
107 The performance of fish depends crucially on inlining scale_vec2.
108 It turns out to be right on the edge of GHC's normal threshold size, so
109 small changes to the compiler can knock it to and fro.
110
111
112 Puzzle
113 ~~~~~~
114 The main function is 'transfer'.  It has some complicated join points, and
115 I found that in my experimental proto 4.09 compiler I had 
116
117         let ds = go xs in
118         let $j = .... ds ... in
119         case e of
120           p1 -> $j
121           p2 -> $j
122           p3 -> ds
123
124 But ds wasn't getting inlined because we couldn't spot that it was actually
125 only being used once.   Keith's analyser should find this!
126
127
128 Also, making concat into a good producer made a large gain.
129
130 My proto 4.09 still allocates more, partly because of more full laziness relative
131 to 4.08; I don't know why that happens
132
133 Extra allocation is happening in 5.02 as well; perhaps for the same reasons.  There is 
134 at least one instance of floating that prevents fusion; namely the enumerated lists
135 in 'transfer'.
136
137 Sphere
138 ~~~~~~
139 A key function is vecsub, which looks like this (after w/w)
140
141 $wvecsub
142   = \ ww :: Double  ww1 :: Double ww2 :: Double
143       ww3 :: Double ww4 :: Double ww5 :: Double ->
144         let { a = case ww of wild { D# x ->
145                   case ww3 of wild1 { D# y ->
146                   let { a1 = -## x y
147                   } in  $wD# a1
148                   } } } in
149         let { a1 = case ww1 of wild { D# x ->
150                    case ww4 of wild1 { D# y ->
151                    let { a2 = -## x y
152                    } in  $wD# a2
153                    } } } in
154         let { a2 = case ww2 of wild { D# x ->
155                    case ww5 of wild1 { D# y ->
156                    let { a3 = -## x y
157                    } in  $wD# a3
158                    } } 
159         } in  (# a, a1, a2 #)
160
161 Currently it gets guidance: IF_ARGS 6 [2 2 2 2 2 2] 25 4
162 It occurs in a context like
163
164         case $wvecsub a b c d e f of  (# p, q, r #) ->
165         case p of                     D# p' ->
166         case q of                     D# q' ->
167         case r of                     D# r' ->
168
169 So it would be much, much better to inline it.  But the result-discounting
170 doesn't "see" that the three results are each taken apart, and that's the
171 problem.
172
173 One question is this: why did minusDouble get inlined? If it didn't then
174 $vecsub would look much smaller:
175
176 $wvecsub
177   = \ ww :: Double  ww1 :: Double ww2 :: Double
178       ww3 :: Double ww4 :: Double ww5 :: Double ->
179         let { a  = minusDouble ww  ww3 } in
180         let { a1 = minusDouble ww1 ww4 } in
181         let { a2 = minusDouble ww2 ww5 } in
182         (# a, a1, a2 #)
183
184 Reason minusDouble gets inlined: because we are trying to get update in place.
185 So I added a flag -funfolding-update-in-place to enable this "optimisation".
186 Omitting the flag gives much better inlining for $wvecsub at least.
187
188
189 Sphere also does 60,000 calls to hPutStr, so I/O plays a major role.  Currently
190 this I/O does a *lot* of allocation, much of it since the adddition of thread-safety.
191
192
193 Treejoin
194 ~~~~~~~~
195 Does a lot of IO.readFile.
196
197 ---------------------------------------
198         Real suite
199 ---------------------------------------
200
201
202