CUDA Data-Parallel Primitives Library
Hash tables are useful for efficiently storing and retrieving sparse data sets. Unlike dense representations, the size of a hash table is generally proportional to the number of elements stored in it rather than the size of the space of possible elements. Hash tables should also have a small cost to insert items and a small cost to retrieve items. CUDPP hash tables have these properties.
CUDPP includes three different hash table types:
|CUDPP_BASIC_HASH_TABLE||Stores a single value per key. The input is expected to be a set of key-value pairs, where the keys are all unique.|
|CUDPP_COMPACTING_HASH_TABLE||Assigns each key a unique identifier and allows O(1) translation between the key and the unique IDs. Input is a set of keys that may, or may not, be repeated.|
|CUDPP_MULTIVALUE_HASH_TABLE||Allows you to store multiple values for each key. Multiple values for the same key are represented by different key-value pairs in the input.|
CUDPP supports four major routines for hash tables: creating a hash table (cudppHashTable), inserting items (typically key/value pairs) into a hash table (cudppHashInsert), retrieving values from a hash table given their keys (cudppHashRetrieve), and destroying the hash table (cudppDestroyHashTable). Each of these routines works with each of the 3 types of hash tables above.
A typical use of a hash table might look like this (see the sample application cudpp_hash_testrig for a complete example):
CUDPP's hash table library relies on a good random number generator to ensure good hash function generation. CUDPP uses the Mersenne Twister implementation provided by Makoto Matsumoto, available here (and included in the CUDPP distribution). You may try using your system's rand() function and srand() functions, but keep in mind that Windows' generator produces numbers in a very small range.
The compacting hash table and multivalue hash table implementation use CUDPP's scan and sort functionality.
The maximum size of the hash table implementations are primarily limited by the size of available memory. The figures below indicate the size of the hash table as a function of:
Other than some 32-bit values (like an error flag and the number of items in the stash), the only memory allocation is for the actual hash table itself:
101 is the size of the stash (in uint32s). We multiply by 2 because we store both keys and values.
In the multivalue hash table, memory is held until the hash table is deleted; it was set up this way to prevent mucking up the timings with memory management.
Each key is capped at UINT_MAX values. Although the code doesn't do it, you could in theory creatively re-use some of the memory or move allocations around to avoid having to hold onto more scratch space than you really need. The CUDPP scan memory, for example, is allocated when the hash table is initialized but only used when it's being built.