1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
<head>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1">
<title>The GHC Commentary - Cunning Prelude Code</title>
</head>
<body BGCOLOR="FFFFFF">
<h1>The GHC Commentary - Cunning Prelude Code</h1>
<p>
GHC's uses a many optimsations and GHC specific techniques (unboxed
values, RULES pragmas, and so on) to make the heavily used Prelude code
as fast as possible.
<hr>
<h4>Par, seq, and lazy</h4>
In GHC.Conc you will dinf
<blockquote><pre>
pseq a b = a `seq` lazy b
</pre></blockquote>
What's this "lazy" thing. Well, <tt>pseq</tt> is a <tt>seq</tt> for a parallel setting.
We really mean "evaluate a, then b". But if the strictness analyser sees that pseq is strict
in b, then b might be evaluated <em>before</em> a, which is all wrong.
<p>
Solution: wrap the 'b' in a call to <tt>GHC.Base.lazy</tt>. This function is just the identity function,
except that it's put into the built-in environment in MkId.lhs. That is, the MkId.lhs defn over-rides the
inlining and strictness information that comes in from GHC.Base.hi. And that makes <tt>lazy</tt> look
lazy, and have no inlining. So the strictness analyser gets no traction.
<p>
In the worker/wrapper phase, after strictness analysis, <tt>lazy</tt> is "manually" inlined (see WorkWrap.lhs),
so we get all the efficiency back.
<p>
This supersedes an earlier scheme involving an even grosser hack in which par# and seq# returned an
Int#. Now there is no seq# operator at all.
<hr>
<h4>fold/build</h4>
<p>
There is a lot of magic in <a
href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/lib/std/PrelBase.lhs"><code>PrelBase.lhs</code></a> -
among other things, the <a
href="http://haskell.cs.yale.edu/ghc/docs/latest/set/rewrite-rules.html">RULES
pragmas</a> implementing the <a
href="http://research.microsoft.com/Users/simonpj/Papers/deforestation-short-cut.ps.Z">fold/build</a>
optimisation. The code for <code>map</code> is
a good example for how it all works. In the prelude code for version
5.03 it reads as follows:
<blockquote><pre>
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
-- Note eta expanded
mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
{-# INLINE [0] mapFB #-}
mapFB c f x ys = c (f x) ys
{-# RULES
"map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
"mapList" [1] forall f. foldr (mapFB (:) f) [] = map f
"mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
#-}</pre>
</blockquote>
<p>
Up to (but not including) phase 1, we use the <code>"map"</code> rule to
rewrite all saturated applications of <code>map</code> with its
build/fold form, hoping for fusion to happen. In phase 1 and 0, we
switch off that rule, inline build, and switch on the
<code>"mapList"</code> rule, which rewrites the foldr/mapFB thing back
into plain map.
<p>
It's important that these two rules aren't both active at once
(along with build's unfolding) else we'd get an infinite loop
in the rules. Hence the activation control using explicit phase numbers.
<p>
The "mapFB" rule optimises compositions of map.
<p>
The mechanism as described above is new in 5.03 since January 2002,
where the <code>[~</code><i>N</i><code>]</code> syntax for phase number
annotations at rules was introduced. Before that the whole arrangement
was more complicated, as the corresponding prelude code for version
4.08.1 shows:
<blockquote><pre>
map :: (a -> b) -> [a] -> [b]
map = mapList
-- Note eta expanded
mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
mapFB c f x ys = c (f x) ys
mapList :: (a -> b) -> [a] -> [b]
mapList _ [] = []
mapList f (x:xs) = f x : mapList f xs
{-# RULES
"map" forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
"mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
"mapList" forall f. foldr (mapFB (:) f) [] = mapList f
#-}</pre>
</blockquote>
<p>
This code is structured as it is, because the "map" rule first
<em>breaks</em> the map <em>open,</em> which exposes it to the various
foldr/build rules, and if no foldr/build rule matches, the "mapList"
rule <em>closes</em> it again in a later phase of optimisation - after
build was inlined. As a consequence, the whole thing depends a bit on
the timing of the various optimsations (the map might be closed again
before any of the foldr/build rules fires). To make the timing
deterministic, <code>build</code> gets a <code>{-# INLINE 2 build
#-}</code> pragma, which delays <code>build</code>'s inlining, and thus,
the closing of the map. [NB: Phase numbering was forward at that time.]
<p><small>
<!-- hhmts start -->
Last modified: Mon Feb 11 20:00:49 EST 2002
<!-- hhmts end -->
</small>
</body>
</html>
|
