[project @ 2000-09-14 14:12:38 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 ---------------------------------------
54         Spectral suite
55 ---------------------------------------
56
57 Multiplier
58 ~~~~~~~~~~
59 In spectral/multiplier, we have 
60     xor = lift21 forceBit f
61       where f :: Bit -> Bit -> Bit
62             f 0 0 = 0
63             f 0 1 = 1
64             f 1 0 = 1
65             f 1 1 = 0
66   Trouble is, f is CPR'd, and that means that instead of returning
67   the constants I# 0, I# 1, it returns 0,1 and then boxes them.
68   So allocation goes up.  I don't see a way around this.
69
70
71 Parstof
72 ~~~~~~~
73 spectral/hartel/parstof ends up saying
74         case (unpackCString "x") of { c:cs -> ... }
75   quite a bit.   We should spot these and behave accordingly.
76
77
78 Knights
79 ~~~~~~~
80 In knights/KnightHeuristic, we don't find that possibleMoves is strict
81 (with important knock-on effects) unless we apply rules before floating
82 out the literal list [A,B,C...].
83 Similarly, in f_se (F_Cmp ...) in listcompr (but a smaller effect)
84
85
86 Expert
87 ~~~~~~
88 In spectral/expert/Search.ask there's a statically visible CSE. Catching this 
89 depends almost entirely on chance, which is a pity.
90
91
92
93 Fish
94 ~~~~
95 The performance of fish depends crucially on inlining scale_vec2.
96 It turns out to be right on the edge of GHC's normal threshold size, so
97 small changes to the compiler can knock it to and fro.
98
99
100 Puzzle
101 ~~~~~~
102 The main function is 'transfer'.  It has some complicated join points, and
103 I found that in my experimental proto 4.09 compiler I had 
104
105         let ds = go xs in
106         let $j = .... ds ... in
107         case e of
108           p1 -> $j
109           p2 -> $j
110           p3 -> ds
111
112 But ds wasn't getting inlined because we couldn't spot that it was actually
113 only being used once.   Keith's analyser should find this!
114
115
116 Also, making concat into a good producer made a large gain.
117
118 My proto 4.09 still allocates more, partly because of more full laziness relative
119 to 4.08; I don't know why that happens
120
121
122 Sphere
123 ~~~~~~
124 A key function is vecsub, which looks like this (after w/w)
125
126 $wvecsub
127   = \ ww :: Double  ww1 :: Double ww2 :: Double
128       ww3 :: Double ww4 :: Double ww5 :: Double ->
129         let { a = case ww of wild { D# x ->
130                   case ww3 of wild1 { D# y ->
131                   let { a1 = -## x y
132                   } in  $wD# a1
133                   } } } in
134         let { a1 = case ww1 of wild { D# x ->
135                    case ww4 of wild1 { D# y ->
136                    let { a2 = -## x y
137                    } in  $wD# a2
138                    } } } in
139         let { a2 = case ww2 of wild { D# x ->
140                    case ww5 of wild1 { D# y ->
141                    let { a3 = -## x y
142                    } in  $wD# a3
143                    } } 
144         } in  (# a, a1, a2 #)
145
146 Currently it gets guidance: IF_ARGS 6 [2 2 2 2 2 2] 25 4
147 It occurs in a context like
148
149         case $wvecsub a b c d e f of  (# p, q, r #) ->
150         case p of                     D# p' ->
151         case q of                     D# q' ->
152         case r of                     D# r' ->
153
154 So it would be much, much better to inline it.  But the result-discounting
155 doesn't "see" that the three results are each taken apart, and that's the
156 problem.
157
158 One question is this: why did minusDouble get inlined? If it didn't then
159 $vecsub would look much smaller:
160
161 $wvecsub
162   = \ ww :: Double  ww1 :: Double ww2 :: Double
163       ww3 :: Double ww4 :: Double ww5 :: Double ->
164         let { a  = minusDouble ww  ww3 } in
165         let { a1 = minusDouble ww1 ww4 } in
166         let { a2 = minusDouble ww2 ww5 } in
167         (# a, a1, a2 #)
168
169 Reason minusDouble gets inlined: because we are trying to get update in place.
170 So I added a flag -funfolding-update-in-place to enable this "optimisation".
171 Omitting the flag gives much better inlining for $wvecsub at least.
172
173
174 Sphere also does 60,000 calls to hPutStr, so I/O plays a major role.  Currently
175 this I/O does a *lot* of allocation, much of it since the adddition of thread-safety.
176
177
178 ---------------------------------------
179         Real suite
180 ---------------------------------------
181
182
183