nympy/torch 中整数序列的快速哈希？ （除了与随机向量的点积 - 它非常好，但可能是其他东西？）

Question

考虑像 (1,0,2,4,...,100) 这样的整数序列。 我们有很多（！）它们，我们需要对它们进行哈希处理，并且在 Python 中应该非常快 - 所以我正在寻找使用 numpy/torch 的方法 - 即没有缓慢的 Python 循环。

有效的简单有效方法 - 是生成随机整数向量 - 只需考虑点积 - 可以仅用一个矩阵积来实现：

np.matmul(array_of_sequences, random_int_vector )

问题1：有什么可以做得更好的想法吗？

欢迎任何评论/想法/建议！

C++ 人们向我建议了类似的内容：https://www.kaggle.com/competitions/santa-2023/discussion/466399#2600835但不确定它是否与 Python 相关。

上述方法的问题之一是它无法在像 P100 这样的旧 GPU 上工作，因为它不支持整数矩阵的乘法。当整数转换为浮点数时， 我们还有另一个麻烦：浮点乘法可能会失去精度，并且散列将无法正常工作。当哈希值是浮点数时 - 更需要解释原因：https://www.kaggle.com/competitions/santa-2023/discussion/468370。但对于整数哈希也存在问题，这更令人惊讶。

Answer 1

此答案在使用相同方法时提供了比

np.matmul

更快的替代方案。

这是用于对代码进行基准测试的初始设置：

import numpy as np

# Note: 
# Items of random_int_vector and array_of_sequences are 32-bit integers
# It might be 64-bit on some machine (eg. on Linux) so a manual conversion is needed
n = 50
seq_count = 10_000_000
random_int_vector = np.random.randint(0, 1000, n)
array_of_sequences = np.array([np.random.permutation(n) for i in range(seq_count)])

首先，

np.matmul

在基于整数的数组中显然不是最优的。事实上，Numpy 为浮点数组调用了高度优化的 BLAS 原语，但迄今为止它对基于整数的数组使用了自己的次优实现。这个实现是sequential（就像所有 Numpy 内部函数一样，不要与 BLAS 函数混淆）。更快的实现包括调用

np.einsum

，这通常会更快一点（但在我的机器上仍然是顺序的）。这是一个例子：

# 532 ms ± 564 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit np.matmul(array_of_sequences, random_int_vector)

# 228 ms ± 504 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
np.einsum('ij,j', array_of_sequences, random_int_vector)

虽然

np.einsum

更好，但它仍然不是最优的并且使用 1 个线程。借助 Numba，我们可以使用更高效的编译代码和多线程来加速计算。这是生成的代码：

import numba as nb

@nb.njit('(int32[:,::1],int32[::1])', parallel=True)
def faster_int_matmul(array_of_sequences, random_int_vector):
    seq_count, n = array_of_sequences.shape
    out = np.empty(seq_count, dtype=np.int32)
    for i in nb.prange(seq_count):
        s = 0
        for j in range(n):
            s += array_of_sequences[i, j] * random_int_vector[j]
        out[i] = s
    return out

# Sequential: 127 ms ± 1.38 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
# Parallel: 58.1 ms ± 1.19 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
faster_int_matmul(array_of_sequences, random_int_vector)

此解决方案对于我的机器上的 32 位基于整数的数组来说几乎是最佳的。事实上，读取

array_of_sequences 并将输出存储在像我这样的 40 GiB/s RAM 上的时间至少为 48.4 毫秒（我的 CPU 上的最佳时间）。在实践中，混合读取/存储通常会导致 CPU 很难使 RAM 饱和，并且页面错误等开销也会阻止 RAM 完全饱和。最后，这个 Numba 实现占用了我 83% 的 RAM

。简而言之，它是

内存限制。这就解释了为什么并行执行在我的 6 核 CPU (i5-9600KF) 上只快了 2.2 倍。 显着加快速度的唯一解决方案是对较小的整数进行操作，例如16位整数

。也就是说，数字应该适合 16 位整数。此外，在实践中，Numba 在这种情况下生成的代码效率明显较低（花费 93.3 毫秒），因此不值得。这似乎是由于 SIMD 指令的缺失/低效使用造成的。虽然较低级别的 C 实现肯定可以解决此问题，但应该记住，速度提升不会高于 2 倍（因为 16 位整数小两倍，并且操作在 32 位上受内存限制）的）。

只要n适合L1/L2缓存，所提供的实现对于更大的random_int_vector

应该是有效的。这意味着它应该很快

n < 10_000

（至少在所有主流 CPU 上）。