哈希表内存访问模式优化：预去重场景性能提升技术问询

在实际业务场景中，我需要使用简化版hashmap对新生成的数据进行预去重，以加速后续排序流程。目标是在排序前高效识别并过滤重复数据（无需完全去重），因此无需处理哈希冲突或调整哈希表大小。

但当前遇到性能瓶颈，主要源于hashmap固有的随机内存访问模式，导致缓存命中率低，进而执行速度缓慢。

为说明问题，我创建了一个简化测试示例（如下），对比三个计算量相近的函数，但其执行时间差异显著，比例约为1:7:7

import time
import numpy as np
from numba import prange, njit

# Function 1: fills an array with hashed values.
@njit(nogil=True, parallel=True)
def test_array(arr):
    array = np.empty(2**24, dtype=np.uint32)
    for i in prange(2**24):
        hashed = (arr[i] * np.uint64(2844674407709551453)) >> np.uint64(40)
        array[i] = hashed
    return array

# Function 2: fills an hashmap with indices.
@njit(nogil=True, parallel=True)
def test_hashmap(arr):
    hashmap = np.empty(2**24, dtype=np.uint32)
    for i in prange(2**24):
        hashed = (arr[i] * np.uint64(2844674407709551453)) >> np.uint64(40)
        hashmap[hashed] = i
    return hashmap

# Optimized Function2: Separates the hashing and storing phases into two steps.
@njit(nogil=True, parallel=True)
def optimized_test_hashmap(arr):
    # First, compute all hash values and store them in an array.
    hash_values = np.empty(2**24, dtype=np.uint32)
    for i in prange(2**24):
        hash_values[i] = (arr[i] * np.uint64(2844674407709551453)) >> np.uint64(40)

    # Then, use the precomputed hash values to fill the hashmap.
    hashmap = np.empty(2**24, dtype=np.uint32)
    for i in prange(2**24):
        hashmap[hash_values[i]] = i
    
    return hashmap


arr = np.random.randint(0, 1 << 64, 2**24, dtype=np.uint64)

# Warm-up runs to ensure JIT compilation is done before timing
t1 = test_array(arr)
t2 = test_hashmap(arr)
t3 = optimized_test_hashmap(arr)

t0 = time.time()
t1 = test_array(arr)
print(f"Execution time for test_array: {time.time() - t0} seconds")

t0 = time.time()
t2 = test_hashmap(arr)
print(f"Execution time for test_hashmap: {time.time() - t0} seconds")

t0 = time.time()
t3 = optimized_test_hashmap(arr)
print(f"Execution time for optimized_test_hashmap: {time.time() - t0} seconds")

• test_array：该函数将哈希值顺序写入数组，内存访问连续，缓存效率高，执行速度快。
• test_hashmap：该函数用哈希值作为索引将数据存入hashmap（数组），哈希索引的随机性导致内存访问不可预测，缓存性能差，执行远慢于test_array。
• optimized_test_hashmap：该函数将哈希计算与存储分离，但执行时间仍与test_hashmap相近，说明结果与Numba的向量化无关。

鉴于实际场景需用hashmap在排序前高效过滤重复数据（无需完全去重），是否存在可显著提升hashmap性能的设计或优化策略，尤其在内存访问效率方面？有无技术可缓解不可预测访问模式导致的缓存低效问题？

我无需处理哈希冲突或调整哈希表大小，仅关注内存访问效率优化。

• 实际处理的数据类型为uint64，数据量过大无法存入缓存。
• 哈希函数包含简单乘法和移位操作，当hashmap长度与不同元素数量相近时去重性能良好。
• 核心目标是加速预去重流程，减少后续排序耗时，排序后会再次去重。

恳请提供提升缓存效率的建议或适配该工作负载的替代数据结构。

优化建议与替代方案 #

1. 分块哈希设计提升缓存局部性

将大哈希表拆分为多个小的连续内存桶，每个桶对应一个哈希值范围。写入时先通过哈希值高位定位桶，再用低位作为桶内偏移，把随机访问的跨度限制在桶内，大幅提升缓存行利用率。

示例实现：

@njit(nogil=True, parallel=True)
def bucketed_hashmap(arr, num_buckets=2**12):
    bucket_size = 2**24 // num_buckets
    # 二维桶数组，每个桶为连续内存块
    hashmap = np.empty((num_buckets, bucket_size), dtype=np.uint32)
    for i in prange(2**24):
        hashed = (arr[i] * np.uint64(2844674407709551453)) >> np.uint64(40)
        bucket_idx = hashed // bucket_size
        offset = hashed % bucket_size
        hashmap[bucket_idx, offset] = i
    return hashmap

2. 用位集替代哈希数组压缩内存占用

既然仅需标记元素是否存在，无需存储索引，可改用位集——每个元素占1位，内存占用降至原uint32数组的1/32，更多数据能被缓存加载，直接提升命中率。

示例实现：

@njit(nogil=True, parallel=True)
def bitset_deduplicate(arr):
    bitset = np.zeros(2**24 // 64, dtype=np.uint64)
    filtered = []
    for i in prange(2**24):
        hashed = (arr[i] * np.uint64(2844674407709551453)) >> np.uint64(40)
        word_idx = hashed // 64
        bit_idx = hashed % 64
        if not (bitset[word_idx] & (1 << bit_idx)):
            bitset[word_idx] |= (1 << bit_idx)
            filtered.append(arr[i])
    return np.array(filtered)

3. 局部预排序替代全局哈希去重

先对数据做轻量级局部排序（比如基数排序前几轮），将哈希值相近的元素集中到连续内存块，再在组内做哈希去重。局部排序的连续内存访问效率远高于随机哈希访问，同时能减少后续全局排序的工作量。

4. 并行模式优化避免伪共享

当前并行模式可能引发多线程缓存行竞争，可按线程划分独立哈希分区，每个线程仅操作自己的分区，最后合并结果，彻底避免跨线程的缓存冲突。

内容的提问来源于stack exchange，提问作者game_difficulty