Faster Hash Operators

CUDA Operators

template<typename TInput, typename TIdentity>
void _zero_collision_hash_cuda(Tensor &output, Tensor &evict_slots, const Tensor &input, Tensor &identities, int64_t max_probe, bool circular_probe, int64_t cur_hour, bool readonly, bool support_evict, const std::optional<Tensor> &local_sizes, const std::optional<Tensor> &offsets, int32_t hash_identity, const std::optional<Tensor> &metadata, bool disable_fallback, const std::optional<Tensor> &input_metadata, int64_t eviction_threshold, int64_t eviction_policy, int64_t opt_in_prob, int64_t num_reserved_slots, const std::optional<Tensor> &opt_in_rands)

CUDA implementation of zero collision hash This function performs zero collision hash on the input feature IDs in the input tensor and returns the remapped IDs in the output tensor. It also updates the metadata table if the eviction policy is enabled. Specifically, it performs the following steps:

1. For each input feature ID, it computes the hash value using the MurmurHash3 algorithm. And the hash value will be forwarded to the identity table (tensor named identities).

2. Check if the slot in the identity table indexed by the hash value is empty. If it is empty, the feature ID will be inserted into the slot and the hash value will be returned as the remapped ID.

3. If the slot is not empty, it will linearly probe the next slot until it finds an empty slot or reaches the maximum number of probes. If an empty slot is found, the feature ID will be inserted into that slot and the index of the empty slot will be returned as the remapped ID.

4. If no empty slot is found, it will find the evictable slot based on the eviction policy and evict the feature ID in that slot. Then, it will insert the current feature ID into the evicted slot and return the index of the evicted slot as the remapped ID. The metadata table will also be updated accordingly.

Parameters:

• output – the output tensor that will be modified in place

• evict_slots – the slots that will be evicted

• input – the input tensor

• identities – the identity tensor

• max_probe – the maximum number of probes

• circular_probe – whether to use circular probe

• cur_hour – the current hour

• readonly – whether to use readonly mode

• support_evict – whether to support evict

• local_sizes – the local sizes tensor

• offsets – the offsets tensor

• hash_identity – whether to hash the identity

• metadata – the metadata tensor

• disable_fallback – whether to disable fallback

• input_metadata – the input metadata tensor

• eviction_threshold – the eviction threshold

• eviction_policy – the eviction policy

• opt_in_prob – the opt-in probability

• num_reserved_slots – the number of reserved slots

• opt_in_rands – the opt-in randoms tensor

Returns:

None (the output tensor will be modified in place)

Tensor murmur_hash3_cuda(const Tensor &input, int64_t y, int64_t seed)

Murmur hash operator for CUDA device.

This function implements the Murmur hash algorithm. Given an input tensor a y value and a seed value, it returns the hash value of the input tensor. The hash value is calculated using the Murmur hash3 x64 algorithm implemented in the murmur_hash3_2x64 function in common_utils.cuh.

Parameters:

• input – the input tensor

• y – the y value

• seed – the seed value

Returns:

the output tensor

CPU Operators

std::tuple<Tensor, Tensor> create_zch_buffer_cpu(const int64_t size, bool support_evict, std::optional<at::Device> device, bool long_type)

Create buffers for identity table and metadata table for ZCH This function declare and initialize the identity table and metadata table for ZCH. The identity table is a tensor of size [size, 1] and the metadata table is a tensor of size [size, 1]. Slots in both the identity table and metadata table are initialized with default value as -1.

Parameters:

• size – The target tensor dimensions

• support_evict – Whether to support eviction

• device – The device to allocate the tensor on

• long_type – Whether to use long type for the tensor

Returns:

A tuple of two tensors, the first tensor is the

Tensor murmur_hash3_cpu(const Tensor &input, int64_t y, int64_t seed)

Murmur hash operator for CPU.

This function implements the Murmur hash algorithm. Given an input tensor a y value and a seed value, it returns the hash value of the input tensor. The hash value is calculated using the Murmur hash3 x64 algorithm implemented in the murmur_hash3_2x64 function in common_utils.cuh.

Parameters:

• input – The input tensor

• y – The y value

• seed – The seed value

Returns:

The output hash value

std::tuple<Tensor, Tensor> zero_collision_hash_cpu(const Tensor &input, Tensor &identities, int64_t max_probe, bool circular_probe, int64_t exp_hours, bool readonly, const std::optional<Tensor> &local_sizes, const std::optional<Tensor> &offsets, const std::optional<Tensor> &metadata, bool, bool disable_fallback, bool _modulo_identity_DPRECATED, const std::optional<Tensor> &input_metadata, int64_t eviction_threshold, int64_t, int64_t opt_in_prob, int64_t num_reserved_slots, const std::optional<Tensor> &opt_in_rands)

Zero collision hash operator for CPU.

This function performs zero collision hash on the input feature IDs in the input tensor and returns the remapped IDs in the output tensor. It also updates the metadata table if the eviction policy is enabled. Specifically, it performs the following steps:

1. For each input feature ID, it computes the hash value using the MurmurHash3 algorithm. And the hash value will be forwarded to the identity table (tensor named identities).

2. Check if the slot in the identity table indexed by the hash value is empty. If it is empty, the feature ID will be inserted into the slot and the hash value will be returned as the remapped ID.

3. If the slot is not empty, it will linearly probe the next slot until it finds an empty slot or reaches the maximum number of probes. If an empty slot is found, the feature ID will be inserted into that slot and the index of the empty slot will be returned as the remapped ID.

4. If no empty slot is found, it will find the evictable slot based on the eviction policy and evict the feature ID in that slot. Then, it will insert the current feature ID into the evicted slot and return the index of the evicted slot as the remapped ID. The metadata table will also be updated accordingly.

Parameters:

• input – The input tensor

• identities – The identity table

• max_probe – The maximum number of probes

• circular_probe – Whether to use circular probe

• exp_hours – The number of hours before identity table item’s expirition

• readonly – Whether to use readonly mode

• local_sizes – The local sizes tensor

• offsets – The offsets tensor

• metadata – The metadata tensor

• output_on_uvm – Whether to output on UVM

• disable_fallback – Whether to disable fallback

• _modulo_identity_DPRECATED – The modulo identity

• input_metadata – The input metadata tensor

• eviction_threshold – The eviction threshold

• eviction_policy – The eviction policy

• opt_in_prob – The opt-in probability

• num_reserved_slots – The number of reserved slots

• opt_in_rands – The opt-in randoms tensor

Returns:

A tuple of two tensors, the first tensor is the output tensor and the second tensor is the slots to be evicted

std::tuple<Tensor, Tensor> zero_collision_hash_meta(const Tensor &input, Tensor&, int64_t, bool, int64_t, bool, const std::optional<Tensor>&, const std::optional<Tensor>&, const std::optional<Tensor>&, bool, bool, bool, const std::optional<Tensor>&, int64_t, int64_t, int64_t, int64_t, const std::optional<Tensor>&)

Zero collision hash operator for Meta device.

This function performs zero collision hash on the input feature IDs in the input tensor and returns the remapped IDs in the output tensor. It also updates the metadata table if the eviction policy is enabled. Specifically, it performs the following steps:

1. For each input feature ID, it computes the hash value using the MurmurHash3 algorithm. And the hash value will be forwarded to the identity table (tensor named identities).

2. Check if the slot in the identity table indexed by the hash value is empty. If it is empty, the feature ID will be inserted into the slot and the hash value will be returned as the remapped ID.

3. If the slot is not empty, it will linearly probe the next slot until it finds an empty slot or reaches the maximum number of probes. If an empty slot is found, the feature ID will be inserted into that slot and the index of the empty slot will be returned as the remapped ID.

4. If no empty slot is found, it will find the evictable slot based on the eviction policy and evict the feature ID in that slot. Then, it will insert the current feature ID into the evicted slot and return the index of the evicted slot as the remapped ID. The metadata table will also be updated accordingly.

Parameters:

• input – The input tensor

• identities – The identity table

• max_probe – The maximum number of probes

• circular_probe – Whether to use circular probe

• exp_hours – The number of hours before identity table item’s expirition

• readonly – Whether to use readonly mode

• local_sizes – The local sizes tensor

• offsets – The offsets tensor

• metadata – The metadata tensor

• output_on_uvm – Whether to output on UVM

• disable_fallback – Whether to disable fallback

• _modulo_identity_DPRECATED – The modulo identity

• input_metadata – The input metadata tensor

• eviction_threshold – The eviction threshold

• eviction_policy – The eviction policy

• opt_in_prob – The opt-in probability

• num_reserved_slots – The number of reserved slots

• opt_in_rands – The opt-in randoms tensor

Returns:

A tuple of two tensors, the first tensor is the output tensor and the second tensor is the slots to be evicted

Tensor murmur_hash3_meta(const Tensor &input, int64_t y, int64_t seed)

Murmur hash operator for Meta device.

This function implements the Murmur hash algorithm. Given an input tensor a y value and a seed value, it returns the hash value of the input tensor. The hash value is calculated using the Murmur hash3 x64 algorithm implemented in the murmur_hash3_2x64 function in common_utils.cuh.

Parameters:

• input – The input tensor

• y – The y value

• seed – The seed value