cuckoogpu::XorAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize > Struct Template Reference

Default XOR-based hashing strategy for cuckoo filters. More...

Static Public Member Functions
template<typename H >
static __host__ __device__ uint64_t	hash64 (const H &key)
	Computes a 64-bit hash of the key.
static __host__ __device__ cuda::std::tuple< size_t, size_t, TagType, TagType >	getCandidateBucketsAndFPs (const KeyType &key, size_t numBuckets)
	Performs partial-key cuckoo hashing to find the fingerprint and both bucket indices for a given key.
static __host__ __device__ size_t	getAlternateBucket (size_t bucket, TagType fp, size_t numBuckets)
	Computes the alternate bucket index using XOR.
static size_t	calculateNumBuckets (size_t capacity)
	The number of buckets is enforced to be a power of two in order to allow for efficient modulo on the bucket indices with XOR-based hashing.

Static Public Attributes
static constexpr size_t	fpMask = (1ULL << bitsPerTag) - 1
static constexpr bool	usesChoiceBit = false
static constexpr char	name [] = "XorAltBucketPolicy"

Detailed Description

template<typename KeyType, typename TagType, size_t bitsPerTag, size_t bucketSize>
struct cuckoogpu::XorAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >

Default XOR-based hashing strategy for cuckoo filters.

This uses the traditional partial-key cuckoo hashing with XOR operation to compute alternate bucket indices.

Definition at line 17 of file bucket_policies.cuh.

Member Function Documentation

calculateNumBuckets()

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

static size_t cuckoogpu::XorAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::calculateNumBuckets ( size_t  capacity )

inlinestatic

The number of buckets is enforced to be a power of two in order to allow for efficient modulo on the bucket indices with XOR-based hashing.

Definition at line 82 of file bucket_policies.cuh.

                                                       {
        auto requiredBuckets = std::ceil(static_cast<double>(capacity) / bucketSize);
        return detail::nextPowerOfTwo(requiredBuckets);
    }

Here is the call graph for this function:

getAlternateBucket()

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

static __host__ __device__ size_t cuckoogpu::XorAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::getAlternateBucket ( size_t  bucket, TagType  fp, size_t  numBuckets  )

inlinestatic

Computes the alternate bucket index using XOR.

Parameters

bucket	Current bucket index.
fp	Fingerprint.
numBuckets	Total number of buckets (must be power of 2).

Returns

size_t Alternate bucket index.

Definition at line 74 of file bucket_policies.cuh.

                                                                     {
        return bucket ^ (hash64(fp) & (numBuckets - 1));
    }

Here is the call graph for this function:

Here is the caller graph for this function:

getCandidateBucketsAndFPs()

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

static __host__ __device__ cuda::std::tuple< size_t, size_t, TagType, TagType > cuckoogpu::XorAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::getCandidateBucketsAndFPs ( const KeyType &  key, size_t  numBuckets  )

inlinestatic

Performs partial-key cuckoo hashing to find the fingerprint and both bucket indices for a given key.

We derive the fingerprint and bucket indices from different parts of the key's hash to greatly reduce the number of collisions. The fingerprint value 0 is reserved to indicate an empty slot, so we use 1 if the computed fingerprint is 0.

Parameters

key	Key to hash
numBuckets	Number of buckets in the filter

Returns

A tuple of (bucket1, bucket2, fingerprintForBucket1, fingerprintForBucket2)

Definition at line 48 of file bucket_policies.cuh.

                                                                     {
        const uint64_t h = hash64(key);
 
        // Upper 32 bits for the fingerprint
        const uint32_t h_fp = h >> 32;
        const uint32_t masked = h_fp & fpMask;
 
        const auto fp = TagType(masked == 0 ? 1 : masked);
 
        // Lower 32 bits for the bucket indices
        const uint32_t h_bucket = h & 0xFFFFFFFF;
        const size_t i1 = h_bucket & (numBuckets - 1);
        const size_t i2 = getAlternateBucket(i1, fp, numBuckets);
 
        return {i1, i2, fp, fp};
    }

Here is the call graph for this function:

hash64()

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

template<typename H >

static __host__ __device__ uint64_t cuckoogpu::XorAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::hash64 ( const H &  key )

inlinestatic

Computes a 64-bit hash of the key.

Template Parameters

H	Type of the key.

Parameters

key	The key to hash.

Returns

uint64_t The 64-bit hash value.

Definition at line 31 of file bucket_policies.cuh.

                                                             {
        return xxhash::xxhash64(key);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

fpMask

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

constexpr size_t cuckoogpu::XorAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::fpMask = (1ULL << bitsPerTag) - 1

staticconstexpr

Definition at line 18 of file bucket_policies.cuh.

name

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

constexpr char cuckoogpu::XorAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::name[] = "XorAltBucketPolicy"

staticconstexpr

Definition at line 22 of file bucket_policies.cuh.

usesChoiceBit

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

constexpr bool cuckoogpu::XorAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::usesChoiceBit = false

staticconstexpr

Definition at line 20 of file bucket_policies.cuh.

---

The documentation for this struct was generated from the following file:

• bucket_policies.cuh