Some simple examples for demonstrating some aspects of optimization with GHC

root / slides / slides.md

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
% Introduction to Low Level Haskell Optimization
% Dan Doel (dan.doel@gmail.com)
% September 17, 2014

# How to Optimize

## How to Optimize

> - Make sure you're using `-O(2)`
> - Profile
> - Use the best algorithm
> - Implement it in the most efficient way

# Getting Intermediate Compiler Information

## Getting Intermediate Compiler Information

GHC user guide section 4.19: `-ddump-*`

. . .

    -ddump-simpl

. . .

    -ddump-stg

. . .

    -ddump-cmm
    -ddump-asm
    -ddump-llvm

. . .

    -ddump-to-file

# STG Syntax

## STG Syntax: Basic
    literal := 0 | 1 | ...
    atom := var | literal
    atoms := {atom, ..., atom}
    vars := {var, ..., var}
    prim := +# | *# | ...

## STG Syntax: Bindings
    bindings := binding ; ... ; binding
    binding := var = lambdaForm
    lambdaForm := vars \pi vars -> expr
    pi := u | n

## STG Syntax: Expressions
    expr := let bindings in expr
          | letrec bindings in expr
          | case expr of var { alts }
          | var atoms
          | constructor atoms
          | prim atoms
          | literal

    alts := aalts | palts
    aalts := aalt ; ... ; aalt ; default
    palts := palt ; ... ; palt ; default
    aalt := constr vars -> expr
    palt := literal -> expr
    default := _DEFAULT_ -> expr

# Operation

## Operation: application is tail call

    f {x, y, z}

. . .

    : {x, xs}

## Operation: `case` uses stack

    case e of v {
       ...
    }

## Operation: `case` always evaluates

    seq = {} \n {x, y} -> case x of _ { _DEFAULT_ -> y }

## Operation: `let` is allocation

    let {
      v1 = {w, x} \n {y, z} -> ... ;
      v2 = {w} \n {y} -> ...
    } in ...

## Operation: calling a constructor is allocation

    f = {} \n {i} -> case +# i 1 of j { _DEFAULT_ -> I# j }

## Operation: unboxed types

    Int#, Word#, Double#, Float#, Char#, (# a, b #), ...

. . .

> - Important for avoiding allocation

# Examples

## Example: map (version 1)

    map f [    ] = []
    map f (y:ys) = f y : map f ys

. . .

    map = {} \n {f, xs} ->
      case xs of _ {
        [] {} -> [] {} ;
        : {y,ys} -> let {
          fy = {f,y} \u {} -> f {y} ;
          mfys = {f,ys} \u {} -> map {f,ys}
        } in : {fy, mfys}
      }

## Example: map (version 2)

    map f = go where go [    ] = []
                     go (y:ys) = f y : go ys

. . .

    map = {} \n {f} ->
       letrec {
         go = {f, go} \n {xs} ->
           case xs of _ {
             [] {} -> [] {} ;
             : {y,ys} -> let {
               fy = {f,y} \u {} -> f {y} ;
               goys = {go,ys} \u -> go {ys}
             } in : {fy, goys}
           }
       } in go

# Tools

## Tools

- Bang patterns

. . .

        {-# LANGUAGE BangPatterns #-}

        foo !x y = ...

. . .

- Pragmas

. . .

        {-# INLINE foo #-}

. . .

        {-# SPECIALIZE foo :: Int -> Int #-}

. . .

        {-# INLINABLE foo #-}


# Resources

## Resources

- GHC user guide
    * haskell.org/ghc/docs/latest/html/users_guide/index.html

- STG Paper
    * research.microsoft.com/apps/pubs/default.aspx?id=67083

- GHC core syntax highlighting for vim
    * hub.darcs.net/dolio/vim-ghc-core

- These slides and examples
    * hub.darcs.net/dolio/optimization-talk-demo