Python/Cython/Numpy 中计算 2 个二进制向量之间汉明距离的最快方法
Fastest way to calculate the Hamming distance between 2 binary vectors in Python / Cython / Numpy
我正在尝试计算二进制向量和二进制向量矩阵之间的汉明距离。我能找到的最快方法是在 Numpy 中使用无符号 8 位整数：
import numpy as np
np.count_nonzero(data[0] != data, axis=1)
但是，这种方法的问题在于它首先找到所有不同的位，然后对差异的数量求和。这不是有点浪费吗？我尝试在 C++ 中实现一个基本版本，其中我还对不同的位数进行计数，这样最后就不需要求和了，但这要慢得多。可能是因为 Numpy 使用 SIMD 指令。
所以我的问题是。有没有办法在 Numpy / Python / Cython 中使用 SIMD 指令直接计算汉明距离？
理想情况下，您真正希望 CPU 做的是 sum += popcount( a[i] ^ b[i]) 块尽可能大。例如在 x86 上，使用 AVX2 使用一条指令一次对 32 个字节进行异或，然后使用更多指令（包括 vpshufb 和 vpaddq）将计数累加到每个元素计数的 SIMD 向量中（最后水平求和）。
对于特定的 ISA，如 x86-64，使用 C++ 内在函数很容易。
您可以接近可移植代码，使用 std::bitset<64> 将 64 位块异或在一起，并将 .count() 作为可移植 API 以获得高效的 popcount。 Clang 可以将标量 popcount 自动矢量化为 AVX2，但 GCC 不能。
为了在不违反严格别名的情况下安全地构造它，您可能需要 memcpy 从另一种类型的任意数据转换为 unsigned long long。
我不知道 Numpy 是否为此编译了一个循环，否则你可能需要在一次传递中进行 XOR，然后在另一次传递中进行 popcount，这会降低计算强度，所以你肯定想要缓存 -将它分成小块，在您返回重新读取它们之前在 L1d 缓存中保持热。
我正在尝试计算二进制向量和二进制向量矩阵之间的汉明距离。我能找到的最快方法是在 Numpy 中使用无符号 8 位整数：
import numpy as np
np.count_nonzero(data[0] != data, axis=1)
但是，这种方法的问题在于它首先找到所有不同的位，然后对差异的数量求和。这不是有点浪费吗？我尝试在 C++ 中实现一个基本版本，其中我还对不同的位数进行计数，这样最后就不需要求和了，但这要慢得多。可能是因为 Numpy 使用 SIMD 指令。
所以我的问题是。有没有办法在 Numpy / Python / Cython 中使用 SIMD 指令直接计算汉明距离？
理想情况下，您真正希望 CPU 做的是 sum += popcount( a[i] ^ b[i]) 块尽可能大。例如在 x86 上，使用 AVX2 使用一条指令一次对 32 个字节进行异或，然后使用更多指令（包括 vpshufb 和 vpaddq）将计数累加到每个元素计数的 SIMD 向量中（最后水平求和）。
对于特定的 ISA，如 x86-64，使用 C++ 内在函数很容易。
您可以接近可移植代码，使用 std::bitset<64> 将 64 位块异或在一起，并将 .count() 作为可移植 API 以获得高效的 popcount。 Clang 可以将标量 popcount 自动矢量化为 AVX2，但 GCC 不能。
为了在不违反严格别名的情况下安全地构造它，您可能需要 memcpy 从另一种类型的任意数据转换为 unsigned long long。
我不知道 Numpy 是否为此编译了一个循环，否则你可能需要在一次传递中进行 XOR，然后在另一次传递中进行 popcount，这会降低计算强度，所以你肯定想要缓存 -将它分成小块，在您返回重新读取它们之前在 L1d 缓存中保持热。