  We design and implement a fully concurrent dynamic hash table for GPUs with
comparable performance to the state of the art static hash tables. We propose a
warp-cooperative work sharing strategy that reduces branch divergence and
provides an efficient alternative to the traditional way of per-thread (or
per-warp) work assignment and processing. By using this strategy, we build a
dynamic non-blocking concurrent linked list, the slab list, that supports
asynchronous, concurrent updates (insertions and deletions) as well as search
queries. We use the slab list to implement a dynamic hash table with chaining
(the slab hash). On an NVIDIA Tesla K40c GPU, the slab hash performs updates
with up to 512 M updates/s and processes search queries with up to 937 M
queries/s. We also design a warp-synchronous dynamic memory allocator,
SlabAlloc, that suits the high performance needs of the slab hash. SlabAlloc
dynamically allocates memory at a rate of 600 M allocations/s, which is up to
37x faster than alternative methods in similar scenarios.
