-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathwaymark.html
195 lines (157 loc) · 8 KB
/
waymark.html
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
189
190
191
192
193
194
195
<!DOCTYPE html>
<html>
<head>
<meta charset='utf-8'>
<meta name='duration' content='10' />
<link href="https://github.global.ssl.fastly.net/assets/github-b2cdde95fa7bc534f9a9fcba7cf4ab009f2a589e.css" media="all" rel="stylesheet" type="text/css" />
<link href="https://github.global.ssl.fastly.net/assets/github2-ee8765cd653592918845477123b0e6f2dc3bc00a.css" media="all" rel="stylesheet" type="text/css" />
<script crossorigin="anonymous" src="https://github.global.ssl.fastly.net/assets/frameworks-cb2007f18d6a634de839bdfc694bbbe1fac1e624.js" type="text/javascript"></script>
<script async="async" crossorigin="anonymous" src="https://github.global.ssl.fastly.net/assets/github-8569770199d7c3e78f612511392c027e9a5ccc0d.js" type="text/javascript"></script>
<title>EuroLLVM 2014 — Edinburgh (April 7-8)</title>
<meta name='author' content='Gabor Greif' />
<meta name='keywords' content='LLVM,waymarking,conference,2014,Edinburgh' />
<meta name='generator' content='make'>
<meta name='copyright'
content='Copyright © 2014 Gabor Greif' />
<meta name='dcterms.rightsHolder' content='Gabor Greif' />
<meta name='dcterms.dateCopyrighted' content='2014' />
<meta name='dcterms.rights' content='Statement of copyright' />
<link rel='stylesheet' type='text/css' media='screen, projection, print'
href='https://www.w3.org/Talks/Tools/Slidy2/styles/slidy.css' />
<script src='https://www.w3.org/Talks/Tools/Slidy2/scripts/slidy.js'
charset='utf-8' type='text/javascript'></script>
<style type='text/css'>
div.slide h1 {
font-size: 2.5em;
}
</style>
</head>
<body>
<div class='slide markdown-body'><h1>
<a name="eurollvm-2014--edinburgh" class="anchor" href="#eurollvm-2014--edinburgh"></a>EuroLLVM 2014 — Edinburgh</h1>
<p>3-bit Waymarking</p>
<p>(a.k.a. Son of <code>Use</code>-Diet)</p>
<p>Gabor Greif<br><em>Weekend LLVM-hobbyist</em></p>
<p><a href="https://camo.githubusercontent.com/e402aab66b95d3229ed7ebe91f061355d1fd46aa/687474703a2f2f6c6c766d2e6f72672f6465766d74672f323031342d30342f4575726f4c4c564d323031342e6a7067" target="_blank"><img src="https://camo.githubusercontent.com/e402aab66b95d3229ed7ebe91f061355d1fd46aa/687474703a2f2f6c6c766d2e6f72672f6465766d74672f323031342d30342f4575726f4c4c564d323031342e6a7067" alt="Banner" data-canonical-src="http://llvm.org/devmtg/2014-04/EuroLLVM2014.jpg" style="max-width:100%;"></a></p>
</div>
<div class='slide markdown-body'><h1>
<a name="the-situation-before-2008" class="anchor" href="#the-situation-before-2008"></a>The Situation Before 2008</h1>
<p><code>Use</code> has 4 pointers</p>
<p><a href="https://rawgithub.com/ggreif/EuroLLVM-Waymarking/master/pre2008.svg" target="_blank"><img src="https://rawgithub.com/ggreif/EuroLLVM-Waymarking/master/pre2008.svg" alt="Before 2008" style="max-width:100%;"></a></p>
</div>
<div class='slide markdown-body'><h1>
<a name="use-diet" class="anchor" href="#use-diet"></a><code>Use</code>-Diet</h1>
<ul>
<li>drop pointer to <code>User</code>
</li>
<li>allocate <code>Use</code>s before <code>User</code> in memory</li>
<li>make <code>Prev</code> pointer tagged (2-bits, since always 4-byte aligned)</li>
<li>seen 12% space savings on big C++ programs</li>
<li>landed in the LLVM codebase: May 2008</li>
</ul><p><a href="https://rawgithub.com/ggreif/EuroLLVM-Waymarking/master/new.svg" target="_blank"><img src="https://rawgithub.com/ggreif/EuroLLVM-Waymarking/master/new.svg" alt="New Scheme" style="max-width:100%;"></a></p>
</div>
<div class='slide markdown-body'><h1>
<a name="how-it-works" class="anchor" href="#how-it-works"></a>How it Works</h1>
<p>Employ a <em>framed serial code</em> in consecutive <code>Use</code>s</p>
<ul>
<li>
<code>S</code> → full stop</li>
<li>
<code>s</code> → stop</li>
<li>
<code>0</code>, <code>1</code> → binary digits</li>
</ul><p>Read off binary digits to obtain distance to <code>User</code></p>
</div>
<div class='slide markdown-body'><h1>
<a name="interlude" class="anchor" href="#interlude"></a>Interlude</h1>
<p>:-)</p>
</div>
<div class='slide markdown-body'><h1>
<a name="the-sacrifice" class="anchor" href="#the-sacrifice"></a>The Sacrifice</h1>
<p>2.5% runtime increase</p>
<p>(but it was worth it!)</p>
</div>
<div class='slide markdown-body'><h1>
<a name="solution" class="anchor" href="#solution"></a>Solution</h1>
<p class='incremental'>When two feet permit just so much speed, then you have to upgrade to three feet!</p>
<p class='incremental'><a href="https://github.com/ggreif/EuroLLVM-Waymarking/raw/master/sawed-cockroach.jpg" target="_blank"><img src="https://github.com/ggreif/EuroLLVM-Waymarking/raw/master/sawed-cockroach.jpg" alt="Photo cockroach sawed into half" style="max-width:40%;"></a></p>
<p class='incremental'>I really did not mean to do something cruel as this!</p>
<p class='incremental'>But no earthly life-form provides this feature, so...</p>
</div>
<div class='slide markdown-body'><h1>
<a name="solution-contd" class="anchor" href="#solution-contd"></a>Solution (contd.)</h1>
<p class='incremental'>Clearly I was in need of some alien technology!</p>
<p class='incremental'>…then I took a page from the book of space exploration and found this gem:</p>
<p class='incremental'><a href="https://github.com/ggreif/EuroLLVM-Waymarking/raw/master/mars-steps.jpg" target="_blank"><img src="https://github.com/ggreif/EuroLLVM-Waymarking/raw/master/mars-steps.jpg" alt="Footprints on Mars" style="max-width:60%;"></a></p>
<p class='incremental'>Alien tricks from Mars! :-)</p>
</div>
<div class='slide markdown-body'><h1>
<a name="son-of-use-diet-3-bits-encoding" class="anchor" href="#son-of-use-diet-3-bits-encoding"></a>Son of <code>Use</code>-Diet: 3-bits Encoding</h1>
<p>On today's predominantly 64-bit platforms, pointers are 8-byte aligned</p>
<p>We have 8 distinct tags for disposal</p>
<ul>
<li>double digits: <code>00</code>, <code>01</code>, <code>10</code>, <code>11</code>
</li>
<li>3 stop tags: <code>q</code>, <code>r</code>, <code>s</code> (always in this order)</li>
<li>full stop: <code>S</code>
</li>
</ul><p>Originally modelled in Haskell (+<code>QuickCheck</code>)</p>
<p>Now in LLVM repo (on a branch), with automatic algorithm selection</p>
</div>
<div class='slide markdown-body'><h1>
<a name="benefits" class="anchor" href="#benefits"></a>Benefits</h1>
<ul>
<li>stop tags allow longer hops while hunting down the framed digits</li>
<li>any stop tag encodes the distance to the framed payload</li>
<li>harvesting 2-bits at a time</li>
</ul></div>
<div class='slide markdown-body'><h1>
<a name="comparison" class="anchor" href="#comparison"></a>Comparison</h1>
<table>
<thead><tr>
<th align="right">tag-bits</th>
<th align="right">frames</th>
</tr></thead>
<tbody>
<tr>
<td align="right">2</td>
<td align="right"><code>…1s100000s11010s10100s1111s1010s110s11s1S</code></td>
</tr>
<tr>
<td align="right">accesses</td>
<td align="right"><code>…87CBA9876BA9876A987659876587654654343221</code></td>
</tr>
<tr>
<td align="right">3</td>
<td align="right"><code>…rs203qrs131qrs113qrs101qrs30qrs13qrs3rsS</code></td>
</tr>
<tr>
<td align="right">accesses</td>
<td align="right"><code>…5566655566655566655555544455444443332221</code></td>
</tr>
<tr>
<td align="right">Δ</td>
<td align="right"><code>…3265443205443204332104332132210211011000</code></td>
</tr>
</tbody>
</table></div>
<div class='slide markdown-body'><h1>
<a name="further-opportunities" class="anchor" href="#further-opportunities"></a>Further Opportunities</h1>
<ul>
<li>unroll tag initialisation loops</li>
<li>distance relative to stopped frame (microoptimization)</li>
<li>
<code>rol</code> (rotate) instructions with condition flags</li>
<li>examining resultant assembly (on all archs!)</li>
</ul></div>
<div class='slide markdown-body'><h1>
<a name="questions---or-just-ask-me-later" class="anchor" href="#questions---or-just-ask-me-later"></a>Questions? — or just ask me later</h1>
<p>Credits:</p>
<ul>
<li>NASA (image)</li>
<li>Wikipedia (image)</li>
<li>W3C Slidy</li>
</ul>
</div>
</body>
</html>