-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSimpleGPUHashTable.html
More file actions
487 lines (439 loc) · 36.7 KB
/
Copy pathSimpleGPUHashTable.html
File metadata and controls
487 lines (439 loc) · 36.7 KB
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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
<!DOCTYPE html>
<html lang="en" prefix="og: http://ogp.me/ns# fb: https://www.facebook.com/2008/fbml">
<head>
<title>A Simple GPU Hash Table - Nosferalatu</title>
<!-- Using the latest rendering mode for IE -->
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="./SimpleGPUHashTable.html">
<meta name="author" content="David Farrell" />
<meta name="keywords" content="Programming" />
<meta name="description" content="A Simple GPU Hash Table" />
<meta property="og:site_name" content="Nosferalatu" />
<meta property="og:type" content="article"/>
<meta property="og:title" content="A Simple GPU Hash Table"/>
<meta property="og:url" content="./SimpleGPUHashTable.html"/>
<meta property="og:description" content="A Simple GPU Hash Table"/>
<meta property="article:published_time" content="2020-03-08" />
<meta property="article:section" content="Blog" />
<meta property="article:tag" content="Programming" />
<meta property="article:author" content="David Farrell" />
<!-- Bootstrap -->
<link rel="stylesheet" href="./theme/css/bootstrap.yeti.min.css" type="text/css"/>
<link href="./theme/css/font-awesome.min.css" rel="stylesheet">
<link href="./theme/css/pygments/emacs.css" rel="stylesheet">
<link href="./theme/css/typogrify.css" rel="stylesheet">
<link rel="stylesheet" href="./theme/css/style.css" type="text/css"/>
<link href="./static/custom.css" rel="stylesheet">
</head>
<body>
<div class="navbar navbar-default navbar-fixed-top" role="navigation">
<div class="container">
<div class="navbar-header">
<button type="button" class="navbar-toggle" data-toggle="collapse" data-target=".navbar-ex1-collapse">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
<a href="./" class="navbar-brand">
Nosferalatu </a>
</div>
<div class="collapse navbar-collapse navbar-ex1-collapse">
<ul class="nav navbar-nav">
<li><a href="./pages/About.html">
About
</a></li>
<li><a href="./pages/Projects.html">
Projects
</a></li>
<li class="active">
<a href="./category/blog.html">Blog</a>
</li>
</ul>
<ul class="nav navbar-nav navbar-right">
</ul>
</div>
<!-- /.navbar-collapse -->
</div>
</div> <!-- /.navbar -->
<!-- Banner -->
<!-- End Banner -->
<!-- Content Container -->
<div class="container">
<div class="row">
<div class="col-sm-9">
<section id="content">
<article>
<header class="page-header">
<h1>
<a href="./SimpleGPUHashTable.html"
rel="bookmark"
title="Permalink to A Simple GPU Hash Table">
A Simple <span class="caps">GPU</span> Hash Table
</a>
</h1>
</header>
<div class="entry-content">
<div class="panel">
<div class="panel-body">
<footer class="post-info">
<span class="label label-default">Date</span>
<span class="published">
<i class="fa fa-calendar"></i><time datetime="2020-03-08T15:00:00-07:00"> Sun 08 March 2020</time>
</span>
<span class="label label-default">Tags</span>
<a href="./tag/programming.html">Programming</a>
</footer><!-- /.post-info --> </div>
</div>
<p>I released a new project <a href="https://github.com/nosferalatu/SimpleGPUHashTable">A Simple <span class="caps">GPU</span> Hash Table</a> on Github.</p>
<p>It is a simple <span class="caps">GPU</span> hash table capable of hundreds of millions of insertions per second. On my laptop’s <span class="caps">NVIDIA</span> <span class="caps">GTX</span> 1060, the code inserts 64 million randomly generated key/values in about 210 milliseconds, and deletes 32 million of those key/value pairs in about 64 milliseconds.</p>
<p>That’s a rate of around 300 million insertions/second and 500 million deletions/second on a laptop.</p>
<p>It’s written in <span class="caps">CUDA</span>, although the same technique is just as applicable to <span class="caps">HLSL</span> or <span class="caps">GLSL</span>.</p>
<p>The hash table implementation has a few constraints that make it work well on a <span class="caps">GPU</span>:</p>
<ul>
<li>Only 32 bit keys and 32 bit values</li>
<li>The hash table is a fixed size</li>
<li>The hash table size must be a power of two</li>
</ul>
<p>An empty sentinel must be reserved for both keys and values (0xffffffff in the example code).</p>
<h1>Lock Free Hash Table</h1>
<p>The hash table uses open addressing with <a href="https://en.wikipedia.org/wiki/Linear_probing">linear probing</a>, so it’s just an array of keys/values in memory, and has excellent cache performance. This is in contrast to chaining, which involves pointer chasing through a linked list. The hash table is a simple array of KeyValue items:</p>
<div class="highlight"><pre><span></span><span class="k">struct</span> <span class="n">KeyValue</span>
<span class="p">{</span>
<span class="kt">uint32_t</span> <span class="n">key</span><span class="p">;</span>
<span class="kt">uint32_t</span> <span class="n">value</span><span class="p">;</span>
<span class="p">};</span>
</pre></div>
<p>The table uses power-of-two sizes instead of prime numbers because pow2/<span class="caps">AND</span> masking is a fast single instruction and the modulo operator is much slower. This is important for linear probing, because as the table is linearly searched, the slot index must be wrapped at each slot. The cost of a modulo operation at each slot quickly adds up.</p>
<p>The table stores only a key and a value for each item, not the hash of the key. Because the table stores 32-bit keys, computing the hash is fairly quick. The example code uses a Murmur3 hash which is only a few shifts, XORs, and multiplies.</p>
<p>The hash table uses a lock free technique that does not depend on any memory ordering. Even if some writes are out of order with other writes, the hash table is still in a valid state. This will be explained more below. This technique works very well for <span class="caps">GPU</span>’s, which can have thousands of threads running concurrently.</p>
<p>Both the keys and values of the hash table are initialized to empty.</p>
<p>The code can be modified to use 64 bit keys and/or 64 bit values. Keys require atomic reads, writes, and compare-and-swap operations, and values require atomic read and writes operations. Fortunately <span class="caps">CUDA</span> reads/writes of 32 and 64 bit values are atomic as long as they are naturally aligned (see <a href="https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#device-memory-accesses">here</a>), and 64 bit atomic compare-and-swap exist on modern <span class="caps">GPU</span>’s. There is of course some performance cost to using 64 bit key/values.</p>
<h1>Hash Table State</h1>
<p>When thinking about the hash table, consider that there are four possible states that each key/value can be in:</p>
<ul>
<li>Both key and value are empty. This is how the hash table is initialized.</li>
<li>The key has been written, but the value has not yet been written. If another thread reads data at this point, then it will return the value of empty (which is fine; it’s the same result as if the other thread had ran slightly earlier, and this is a concurrent data structure).</li>
<li>Both the key and value have been written.</li>
<li>The value is visible to other threads, but the key is not yet visible. This might happen because the <span class="caps">CUDA</span> programming model assumes a weakly ordered memory model. This is fine, in any event— the key is still empty, even though the value is not.</li>
</ul>
<p>A subtle but important point is that once a key has been written to a slot, it never moves (even when the key is deleted, as discussed below).</p>
<p>The hash table code works even with weakly ordered memory models, where the order of memory reads and writes is unknown. As we look at the code below for hash table insertion, lookups, and deletion, keep in mind that each key/value is in one of these four states.</p>
<h1>Hash Table Insertion</h1>
<p>The <span class="caps">CUDA</span> function that inserts key/value pairs into the hash table looks like this:</p>
<div class="highlight"><pre><span></span><span class="kt">void</span> <span class="nf">gpu_hashtable_insert</span><span class="p">(</span><span class="n">KeyValue</span><span class="o">*</span> <span class="n">hashtable</span><span class="p">,</span> <span class="kt">uint32_t</span> <span class="n">key</span><span class="p">,</span> <span class="kt">uint32_t</span> <span class="n">value</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">uint32_t</span> <span class="n">slot</span> <span class="o">=</span> <span class="n">hash</span><span class="p">(</span><span class="n">key</span><span class="p">);</span>
<span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">uint32_t</span> <span class="n">prev</span> <span class="o">=</span> <span class="n">atomicCAS</span><span class="p">(</span><span class="o">&</span><span class="n">hashtable</span><span class="p">[</span><span class="n">slot</span><span class="p">].</span><span class="n">key</span><span class="p">,</span> <span class="n">kEmpty</span><span class="p">,</span> <span class="n">key</span><span class="p">);</span>
<span class="k">if</span> <span class="p">(</span><span class="n">prev</span> <span class="o">==</span> <span class="n">kEmpty</span> <span class="o">||</span> <span class="n">prev</span> <span class="o">==</span> <span class="n">key</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">hashtable</span><span class="p">[</span><span class="n">slot</span><span class="p">].</span><span class="n">value</span> <span class="o">=</span> <span class="n">value</span><span class="p">;</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">slot</span> <span class="o">=</span> <span class="p">(</span><span class="n">slot</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">&</span> <span class="p">(</span><span class="n">kHashTableCapacity</span><span class="o">-</span><span class="mi">1</span><span class="p">);</span>
<span class="p">}</span>
<span class="p">}</span>
</pre></div>
<p>To insert a key, the code iterates through the hash table array starting at the insertion key’s hash. At each hash table array slot, it does an atomic compare-and-swap, which compares the key at that slot to empty, updates the slot’s key with the insertion key if it matches, and returns the slot’s original key. If that slot’s original key was empty or matches the insertion key, then the code found the correct slot for the insertion key, and sets the slot’s value to the insertion value.</p>
<p>If there are many items with the same key in a single kernel invocation of gpu_hashtable_insert(), then any of those values may be written to the key’s slot. This is still correct; one of the key/value writes in the invocation will succeed, but because all of this is happening in parallel across many threads, it is impossible to know which will be the last to write to memory.</p>
<h1>Hash Table Lookups</h1>
<p>The code to find keys:</p>
<div class="highlight"><pre><span></span><span class="kt">uint32_t</span> <span class="nf">gpu_hashtable_lookup</span><span class="p">(</span><span class="n">KeyValue</span><span class="o">*</span> <span class="n">hashtable</span><span class="p">,</span> <span class="kt">uint32_t</span> <span class="n">key</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">uint32_t</span> <span class="n">slot</span> <span class="o">=</span> <span class="n">hash</span><span class="p">(</span><span class="n">key</span><span class="p">);</span>
<span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">if</span> <span class="p">(</span><span class="n">hashtable</span><span class="p">[</span><span class="n">slot</span><span class="p">].</span><span class="n">key</span> <span class="o">==</span> <span class="n">key</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">return</span> <span class="n">hashtable</span><span class="p">[</span><span class="n">slot</span><span class="p">].</span><span class="n">value</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">if</span> <span class="p">(</span><span class="n">hashtable</span><span class="p">[</span><span class="n">slot</span><span class="p">].</span><span class="n">key</span> <span class="o">==</span> <span class="n">kEmpty</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">return</span> <span class="n">kEmpty</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">slot</span> <span class="o">=</span> <span class="p">(</span><span class="n">slot</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">&</span> <span class="p">(</span><span class="n">kHashTableCapacity</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span>
<span class="p">}</span>
<span class="p">}</span>
</pre></div>
<p>To find the value of a key stored in the hash table, we iterate through the hash table array starting at the lookup key’s hash. At each slot, we test if the key is the one we’re looking for, and if so we return its value. We also test if the key is empty, and terminate the search if so.</p>
<p>If the lookup fails to find the key, then it returns a value of empty.</p>
<p>These lookups can concurrently happen with inserts and deletes. A thread will see each key/value in the table in one of the four states described above.</p>
<h1>Hash Table Deletion</h1>
<p>The code to delete keys:</p>
<div class="highlight"><pre><span></span><span class="kt">void</span> <span class="nf">gpu_hashtable_delete</span><span class="p">(</span><span class="n">KeyValue</span><span class="o">*</span> <span class="n">hashtable</span><span class="p">,</span> <span class="kt">uint32_t</span> <span class="n">key</span><span class="p">,</span> <span class="kt">uint32_t</span> <span class="n">value</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">uint32_t</span> <span class="n">slot</span> <span class="o">=</span> <span class="n">hash</span><span class="p">(</span><span class="n">key</span><span class="p">);</span>
<span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">if</span> <span class="p">(</span><span class="n">hashtable</span><span class="p">[</span><span class="n">slot</span><span class="p">].</span><span class="n">key</span> <span class="o">==</span> <span class="n">key</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">hashtable</span><span class="p">[</span><span class="n">slot</span><span class="p">].</span><span class="n">value</span> <span class="o">=</span> <span class="n">kEmpty</span><span class="p">;</span>
<span class="k">return</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">if</span> <span class="p">(</span><span class="n">hashtable</span><span class="p">[</span><span class="n">slot</span><span class="p">].</span><span class="n">key</span> <span class="o">==</span> <span class="n">kEmpty</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">return</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">slot</span> <span class="o">=</span> <span class="p">(</span><span class="n">slot</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">&</span> <span class="p">(</span><span class="n">kHashTableCapacity</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span>
<span class="p">}</span>
<span class="p">}</span>
</pre></div>
<p>Deleting a key involves something unexpected: we leave the key in the table and mark its value (not the key) as empty. This code is very similar to lookup(), except that if it finds a matching key in the table, it sets its value to empty.</p>
<p>As mentioned earlier, once a key has been written to a slot, it never moves. Even when an item is deleted from the table, the key remains but its value is empty. This means there’s no need to use an atomic operation to write to the slot’s value, because it doesn’t matter if the current value is non-empty or empty— the slot’s value will be updated to empty either way.</p>
<h1>Hash Table Resizing</h1>
<p>Resizing the hash table can be performed by creating a new table of larger size and inserting all non-empty elements of the old table into the new table. I didn’t implement that, as the example code is intended to be simple. Furthermore, this example is in <span class="caps">CUDA</span>, and memory allocations in <span class="caps">CUDA</span> programs are often done by the host code, not within a <span class="caps">CUDA</span> kernel.</p>
<p>Alternatively, <a href="https://web.stanford.edu/class/ee380/Abstracts/070221_LockFreeHash.pdf">A Lock-Free Wait-Free Hash Table</a> describes how to resize this lock free data structure. </p>
<h1>Concurrency</h1>
<p>In the code snippets above, gpu_hashtable_insert()/_lookup()/_delete() process one key/value at a time. In the example code, though, gpu_hashtable_insert()/_lookup()/_delete() process an array of key/value pairs in parallel, where each key/value is processed by one <span class="caps">GPU</span> thread:</p>
<div class="highlight"><pre><span></span><span class="c1">// CPU code to invoke the CUDA kernel on the GPU</span>
<span class="kt">uint32_t</span> <span class="n">threadblocksize</span> <span class="o">=</span> <span class="mi">1024</span><span class="p">;</span>
<span class="kt">uint32_t</span> <span class="n">gridsize</span> <span class="o">=</span> <span class="p">(</span><span class="n">numkvs</span> <span class="o">+</span> <span class="n">threadblocksize</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="n">threadblocksize</span><span class="p">;</span>
<span class="n">gpu_hashtable_insert_kernel</span><span class="o"><<<</span><span class="n">gridsize</span><span class="p">,</span> <span class="n">threadblocksize</span><span class="o">>>></span><span class="p">(</span><span class="n">hashtable</span><span class="p">,</span> <span class="n">kvs</span><span class="p">,</span> <span class="n">numkvs</span><span class="p">);</span>
<span class="c1">// GPU code to process numkvs key/values in parallel</span>
<span class="kt">void</span> <span class="nf">gpu_hashtable_insert_kernel</span><span class="p">(</span><span class="n">KeyValue</span><span class="o">*</span> <span class="n">hashtable</span><span class="p">,</span> <span class="k">const</span> <span class="n">KeyValue</span><span class="o">*</span> <span class="n">kvs</span><span class="p">,</span> <span class="kt">unsigned</span> <span class="kt">int</span> <span class="n">numkvs</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">unsigned</span> <span class="kt">int</span> <span class="n">threadid</span> <span class="o">=</span> <span class="n">blockIdx</span><span class="p">.</span><span class="n">x</span><span class="o">*</span><span class="n">blockDim</span><span class="p">.</span><span class="n">x</span> <span class="o">+</span> <span class="n">threadIdx</span><span class="p">.</span><span class="n">x</span><span class="p">;</span>
<span class="k">if</span> <span class="p">(</span><span class="n">threadid</span> <span class="o"><</span> <span class="n">numkvs</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">gpu_hashtable_insert</span><span class="p">(</span><span class="n">hashtable</span><span class="p">,</span> <span class="n">kvs</span><span class="p">[</span><span class="n">threadid</span><span class="p">].</span><span class="n">key</span><span class="p">,</span> <span class="n">kvs</span><span class="p">[</span><span class="n">threadid</span><span class="p">].</span><span class="n">value</span><span class="p">);</span>
<span class="p">}</span>
<span class="p">}</span>
</pre></div>
<p>The lock free hash table supports concurrent inserts, lookups, and deletes. Because the hash table key/values are always in one of four states, and keys don’t move around, the hash table guarantees correctness even when mixing different kinds of operations.</p>
<p>However, when processing a batch of inserts/deletes in parallel in a kernel, and a kernel’s input array of key/values contains duplicate keys, then it’s unpredictable which of those key/values will “win” and be the last one written to the hash table. For example, imagine that an insertion kernel is called with an input array of key/values is <code>A/0 B/1 A/2 C/3 A/4</code>. When the kernel finishes, the key/values <code>B/1</code> and <code>C/3</code> are guaranteed to be in the table, but any one of <code>A/0</code>, <code>A/2</code>, or <code>A/4</code> will be in the table. Depending on the application, this may or may not be an issue— it might be known that the input array has no duplicate keys, or it might not matter which value is the last to be written.</p>
<p>If this is an issue for an application, then it needs to separate the duplicate key/values into different <span class="caps">CUDA</span> kernel calls. In <span class="caps">CUDA</span>, all operations within a kernel invocation always finish before the next kernel invocation (at least, within a single stream; kernels in different streams execute in parallel). In the above example, if one kernel is called with <code>A/0 B/1 A/2 C/3</code>, and then another kernel is called with <code>A/4</code>, then the key <code>A</code> will have the value <code>4</code>.</p>
<p>Another consideration is whether the lookup() and delete() functions should use a plain or volatile pointer to the hash table key/value array. The <a href="https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#volatile-qualifier"><span class="caps">CUDA</span> documentation for volatile</a> states that “The compiler is free to optimize reads and writes to global or shared memory … These optimizations can be disabled using the volatile keyword: … any reference to this variable compiles to an actual memory read or write instruction.” Using volatile is not necessary for correctness; if a thread uses a cached value from an earlier read, it will be using slightly out of date information, but it will still be using information from a valid state of the hash table at some point in that kernel’s invocation. If an application wants to be sure to use the most up to date information, then it can use a volatile pointer, but there is a slight performance hit (in my tests, deleting 32 million elements went from 500 million deletes / second to 450 Mdeletes/sec).</p>
<h1>Performance</h1>
<p>In a test that inserts 64 million items and deletes 32 million of them, there’s no contest between std::unordered_map and the <span class="caps">GPU</span> hash table:</p>
<p><img alt="performance comparison" src="./images/stdunorderedmap_vs_simplegpuhashtable.png"></p>
<p>The std::unordered_map took 70691 milliseconds to insert and delete the items, and then freeing the unordered_map (freeing an unordered_map with millions of items consumes a significant amount of time because unordered_map does many memory allocations internally). To be fair, std:unordered_map is operating on a very different set of constraints. It is a single <span class="caps">CPU</span> thread, it supports key/values of any size, and it works well with high load factors and has steady performance after many deletions.</p>
<p>The <span class="caps">GPU</span> hash table and interop time took 984 milliseconds. That includes time for allocating and deleting the hash table (which is a single memory allocation of 1 <span class="caps">GB</span>, which takes some time in <span class="caps">CUDA</span>), inserting and deleting the items, and iterating through all items. Also included are all memory copies to/from the <span class="caps">GPU</span>.</p>
<p>The <span class="caps">GPU</span> hash table took 271 milliseconds. That includes just the <span class="caps">GPU</span> time to insert and delete the items, and not the time for memory copies or iterating over the resulting table. If the <span class="caps">GPU</span> table is long lived, or the hash table exists entirely on the <span class="caps">GPU</span> (for example, to build a hash table on the <span class="caps">GPU</span> that is used by other <span class="caps">GPU</span> code, not the <span class="caps">CPU</span>), then this is the relevant time.</p>
<p>The <span class="caps">GPU</span> hash table achieves high performance thanks to the large bandwidth and massive parallelism of <span class="caps">GPU</span>’s.</p>
<h1>Drawbacks</h1>
<p>There are a couple of issues with this hash table design that should be kept in mind:</p>
<ul>
<li>Linear probing suffers from clustering, so that keys are often very far from their ideal slots in the table</li>
<li>Keys are not removed from the table by the delete function, and clutter the table over time</li>
</ul>
<p>As a result, performance of the hash table can degrade over time, especially with long-lived hash tables that have had many inserts and deletes. One way to mitigate these issues is to rehash the table into a new table with a sufficiently low load factor and filtering out deleted keys during the rehash.</p>
<p>To illustrate these issues, I used the hash table example code to create a hash table with a capacity of 128 million elements, and inserted 4 million elements into the table in a loop until the table had 124 million elements (a load factor around 0.96). Here’s the timing of the kernel that inserted 4 million elements; every row is a <span class="caps">CUDA</span> kernel call that inserts 4 million new items into the same hash table:</p>
<table>
<thead>
<tr>
<th>Load factor </th>
<th>Time to insert 4194304 items</th>
</tr>
</thead>
<tbody>
<tr>
<td>0.00</td>
<td>11.608448 ms (361.314798 million keys/second)</td>
</tr>
<tr>
<td>0.03</td>
<td>11.751424 ms (356.918799 million keys/second)</td>
</tr>
<tr>
<td>0.06</td>
<td>11.942592 ms (351.205515 million keys/second)</td>
</tr>
<tr>
<td>0.09</td>
<td>12.081120 ms (347.178429 million keys/second)</td>
</tr>
<tr>
<td>0.12</td>
<td>12.242560 ms (342.600233 million keys/second)</td>
</tr>
<tr>
<td>0.16</td>
<td>12.396448 ms (338.347235 million keys/second)</td>
</tr>
<tr>
<td>0.19</td>
<td>12.533024 ms (334.660176 million keys/second)</td>
</tr>
<tr>
<td>0.22</td>
<td>12.703328 ms (330.173626 million keys/second)</td>
</tr>
<tr>
<td>0.25</td>
<td>12.884512 ms (325.530693 million keys/second)</td>
</tr>
<tr>
<td>0.28</td>
<td>13.033472 ms (321.810182 million keys/second)</td>
</tr>
<tr>
<td>0.31</td>
<td>13.239296 ms (316.807174 million keys/second)</td>
</tr>
<tr>
<td>0.34</td>
<td>13.392448 ms (313.184256 million keys/second)</td>
</tr>
<tr>
<td>0.37</td>
<td>13.624000 ms (307.861434 million keys/second)</td>
</tr>
<tr>
<td>0.41</td>
<td>13.875520 ms (302.280855 million keys/second)</td>
</tr>
<tr>
<td>0.44</td>
<td>14.126528 ms (296.909756 million keys/second)</td>
</tr>
<tr>
<td>0.47</td>
<td>14.399328 ms (291.284699 million keys/second)</td>
</tr>
<tr>
<td>0.50</td>
<td>14.690304 ms (285.515123 million keys/second)</td>
</tr>
<tr>
<td>0.53</td>
<td>15.039136 ms (278.892623 million keys/second)</td>
</tr>
<tr>
<td>0.56</td>
<td>15.478656 ms (270.973402 million keys/second)</td>
</tr>
<tr>
<td>0.59</td>
<td>15.985664 ms (262.379092 million keys/second)</td>
</tr>
<tr>
<td>0.62</td>
<td>16.668673 ms (251.627968 million keys/second)</td>
</tr>
<tr>
<td>0.66</td>
<td>17.587200 ms (238.486174 million keys/second)</td>
</tr>
<tr>
<td>0.69</td>
<td>18.690048 ms (224.413765 million keys/second)</td>
</tr>
<tr>
<td>0.72</td>
<td>20.278816 ms (206.831789 million keys/second)</td>
</tr>
<tr>
<td>0.75</td>
<td>22.545408 ms (186.038058 million keys/second)</td>
</tr>
<tr>
<td>0.78</td>
<td>26.053312 ms (160.989275 million keys/second)</td>
</tr>
<tr>
<td>0.81</td>
<td>31.895008 ms (131.503463 million keys/second)</td>
</tr>
<tr>
<td>0.84</td>
<td>42.103294 ms (99.619378 million keys/second)</td>
</tr>
<tr>
<td>0.87</td>
<td>61.849056 ms (67.815164 million keys/second)</td>
</tr>
<tr>
<td>0.90</td>
<td>105.695999 ms (39.682713 million keys/second)</td>
</tr>
<tr>
<td>0.94</td>
<td>240.204636 ms (17.461378 million keys/second)</td>
</tr>
</tbody>
</table>
<p>Clearly, performance degrades as the load factor increases. This is not a desirable property of a hash table for most applications. If the application is inserting items into a hash table and then throwing it away (for example, to count the words in a book), this might not be a problem. But if the application has a long-lived hash table (for example, an image editing application that stores the non-empty parts of the image in a table, and where the user causes many inserts and deletes in the table), this could be a real issue.</p>
<p>I measured the probe lengths of the hash table after 64 million inserts (so at a load factor of 0.50). The average probe length was 0.4774, so most keys were either in their best slot or just one slot away. The maximum probe length was 60.</p>
<p>I then measured the probe lengths of the table after 124 million inserts (a load factor of 0.97), and found that the average probe length was 10.1757, and the maximum probe length was <em>6474</em> (!!). Linear probing’s performance is not great with high load factors.</p>
<p>The best way to use this hash table is to keep load factors low. However, that trades off memory for performance. Fortunately, with 32 bit keys and values, that might be a reasonable choice for an application. In the example above, if we wanted a load factor of 0.25 with a hash table capacity of 128 million items, then we could insert no more than 32 million items, wasting the other 96 million items— times 8 bytes for each key/value, that’s 768 <span class="caps">MB</span> of wasted space.</p>
<p>Note that this is wasted space in <span class="caps">GPU</span> <span class="caps">VRAM</span>, which is a more precious commodity than the system memory. While most modern desktop <span class="caps">GPU</span>’s running <span class="caps">CUDA</span> have at least 4 <span class="caps">GB</span> of <span class="caps">VRAM</span> (and at the time of writing, an <span class="caps">NVIDIA</span> 2080 Ti has 11 <span class="caps">GB</span>), it’s still not ideal to waste so much memory.</p>
<p>I will be writing more about other ways to build <span class="caps">GPU</span> hash tables that do not suffer long probe lengths like linear probing and ways to reuse deleted slots in the table.</p>
<h1>Measuring Probe Length</h1>
<p>To determine the probe length of a key, we can subtract the key’s hash (its ideal index in the table) from the key’s actual index in the table:</p>
<div class="highlight"><pre><span></span><span class="c1">// get_key_index() -> index of key in hash table</span>
<span class="kt">uint32_t</span> <span class="n">probelength</span> <span class="o">=</span> <span class="p">(</span><span class="n">get_key_index</span><span class="p">(</span><span class="n">key</span><span class="p">)</span> <span class="o">-</span> <span class="n">hash</span><span class="p">(</span><span class="n">key</span><span class="p">))</span> <span class="o">&</span> <span class="p">(</span><span class="n">hashtablecapacity</span><span class="o">-</span><span class="mi">1</span><span class="p">);</span>
</pre></div>
<p>Because of the magic of two’s complement numbers, and the fact that the hash table capacity is a power-of-two, this works even when the key’s index has wrapped around the beginning of the table. Consider a key that hashes to 1 but has been inserted at slot 3; then for a hash table of capacity 4, we have <code>(3 - 1) & 3</code>, which equals 2.</p>
<h1>Conclusion</h1>
<p>Contact me at <a href="http://twitter.com/nosferalatu">Nosferalatu on Twitter</a> or open a new issue at <a href="https://github.com/nosferalatu/SimpleGPUHashTable">the example code’s Github repo</a> with any questions or comments.</p>
<p>This code is based on the excellent work at:</p>
<ul>
<li><a href="https://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table/">The World’s Simplest Lock-Free Hash Table</a></li>
<li><a href="https://web.stanford.edu/class/ee380/Abstracts/070221_LockFreeHash.pdf">A Lock-Free Wait-Free Hash Table</a></li>
</ul>
<p>In the future, I will be writing more about <span class="caps">GPU</span> hash table implementations and analyzing their performance. I’ve been looking at chaining, Robin Hood hashing, and cuckoo hashing using atomic operations for <span class="caps">GPU</span>-friendly data structures.</p>
</div>
<!-- /.entry-content -->
</article>
</section>
</div>
<div class="col-sm-3" id="sidebar">
<aside>
<!-- Sidebar -->
<section class="well well-sm">
<ul class="list-group list-group-flush">
<!-- Sidebar/Social -->
<li class="list-group-item">
<h4><i class="fa fa-home fa-lg"></i><span class="icon-label">Social</span></h4>
<ul class="list-group" id="social">
<li class="list-group-item"><a href="http://twitter.com/nosferalatu"><i class="fa fa-twitter-square fa-lg"></i> twitter</a></li>
<li class="list-group-item"><a href="http://github.com/nosferalatu"><i class="fa fa-github-square fa-lg"></i> github</a></li>
</ul>
</li>
<!-- End Sidebar/Social -->
</ul>
</section>
<!-- End Sidebar --> </aside>
</div>
</div>
</div>
<!-- End Content Container -->
<footer>
<div class="container">
<hr>
<div class="row">
<div class="col-xs-10">© 2025 David Farrell
· Powered by <a href="https://github.com/getpelican/pelican-themes/tree/master/pelican-bootstrap3" target="_blank">pelican-bootstrap3</a>,
<a href="http://docs.getpelican.com/" target="_blank">Pelican</a>,
<a href="http://getbootstrap.com" target="_blank">Bootstrap</a> <p><small>Content licensed under <a href="https://creativecommons.org/licenses/by/4.0/">CC-BY-4.0</a></small></p>
</div>
<div class="col-xs-2"><p class="pull-right"><i class="fa fa-arrow-up"></i> <a href="#">Back to top</a></p></div>
</div>
</div>
</footer>
<script src="./theme/js/jquery.min.js"></script>
<!-- Include all compiled plugins (below), or include individual files as needed -->
<script src="./theme/js/bootstrap.min.js"></script>
<!-- Enable responsive features in IE8 with Respond.js (https://github.com/scottjehl/Respond) -->
<script src="./theme/js/respond.min.js"></script>
<!-- Google Analytics -->
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-155088985-1']);
_gaq.push(['_trackPageview']);
(function () {
var ga = document.createElement('script');
ga.type = 'text/javascript';
ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0];
s.parentNode.insertBefore(ga, s);
})();
</script>
<!-- End Google Analytics Code -->
</body>
</html>