cuckoo_hash.cuh

Go to the documentation of this file.

// SPDX-License-Identifier: Apache-2.0
#pragma once
#include <cuda_runtime.h>
#include <cmath>
#include <span>
#include <utility>
#include <random>
#include <fss/prp.cuh>
 
namespace fss::cuckoo_hash {
 
namespace detail {
 
constexpr double Log2(double x) {
    if (x <= 0) return -1e308;
    int e = 0;
    double m = x;
    while (m >= 2.0) {
        m /= 2.0;
        ++e;
    }
    while (m < 1.0) {
        m *= 2.0;
        --e;
    }
    double y = (m - 1.0) / (m + 1.0);
    double y2 = y * y, sum = 0, term = y;
    for (int k = 0; k < 40; ++k) {
        sum += term / (2 * k + 1);
        term *= y2;
    }
    return e + 2.0 * sum / 0.6931471805599453;
}
 
constexpr double Ceil(double x) {
    auto i = static_cast<long long>(x);
    return (x > static_cast<double>(i)) ? static_cast<double>(i + 1) : static_cast<double>(i);
}
 
}  // namespace detail
 
constexpr int ChBucket(int t, int lambda) {
    // Remark 1 applies for t >= 30.
    // For smaller t, the full Lemma 5 formula with Normal CDF factors is needed,
    // but the paper considers t >= 30 to capture nearly all practical use cases.
    assert(t >= 30);
    double td = static_cast<double>(t);
    double e = (static_cast<double>(lambda) + 130.0 + detail::Log2(td)) / 123.5;
    return static_cast<int>(detail::Ceil(e * td));
}
 
template <typename Prp, typename In, int kappa = 3>
    requires Permutable<Prp>
struct PrpHash {
    Prp prp;
 
    std::pair<int, int> Locate(int4 sigma, In x, int k, __uint128_t n, int b_size) {
        __uint128_t val = static_cast<__uint128_t>(x) + n * k;
        __uint128_t domain = n * kappa;
        __uint128_t y = prp.Permu(sigma, val, domain);
 
        auto bs = static_cast<__uint128_t>(b_size);
        int bucket = static_cast<int>(y / bs);
        int index = static_cast<int>(y % bs);
        return {bucket, index};
    }
};
 
template <typename Prp, typename In, int kappa = 3>
    requires Permutable<Prp>
struct Compact {
    Prp prp;
 
    int Run(std::span<const In> as, int m, int4 sigma, __uint128_t n, int b_size, int ch_retry,
        std::span<std::pair<int, int>> table) {
        PrpHash<Prp, In, kappa> hasher{prp};
        int t = static_cast<int>(as.size());
 
        // Initialize table to empty.
        for (int i = 0; i < m; ++i) {
            table[i] = {-1, -1};
        }
 
        std::mt19937 rng(42);
 
        for (int omega = 0; omega < t; ++omega) {
            int cur_idx = omega;
            int cur_k = static_cast<int>(rng() % kappa);
            int evictions = 0;
 
            for (;;) {
                auto [bucket, _index] = hasher.Locate(sigma, as[cur_idx], cur_k, n, b_size);
                // Clamp bucket to [0, m).
                bucket = bucket % m;
 
                if (table[bucket].first == -1) {
                    // Empty slot found.
                    table[bucket] = {cur_idx, cur_k};
                    break;
                }
 
                // Evict the existing entry and take its place.
                int evicted_idx = table[bucket].first;
                int evicted_k = table[bucket].second;
                table[bucket] = {cur_idx, cur_k};
 
                // The evicted element becomes the current element with a new random hash.
                cur_idx = evicted_idx;
                cur_k = static_cast<int>(rng() % kappa);
 
                ++evictions;
                if (evictions > ch_retry) {
                    return 1;
                }
            }
        }
 
        return 0;
    }
};
 
}  // namespace fss::cuckoo_hash