Python 中的滚动哈希非常快？

Question

我正在rsync用 Python 编写一个类似玩具的工具。与许多类似的工具一样，它首先使用非常快的哈希作为滚动哈希，然后在找到匹配项后使用 SHA256（但后者不在此处的主题：SHA256、MDA5 等作为滚动哈希太慢）哈希）。

我目前正在测试各种快速哈希方法：

import os, random, time

block_size = 1024  # 1 KB blocks
total_size = 10*1024*1024  # 10 MB random bytes
s = os.urandom(total_size)

t0 = time.time()
for i in range(len(s)-block_size):
    h = hash(s[i:i+block_size])
print('rolling hashes computed in %.1f sec (%.1f MB/s)' % (time.time()-t0, total_size/1024/1024/(time.time()-t0)))

我得到：0.8 MB/s ...所以Python内置hash(...)函数在这里太慢了。

哪种解决方案可以在标准机器上实现至少 10 MB/s 的更快哈希值？

• 我尝试过

  import zlib
  ...
      h = zlib.adler32(s[i:i+block_size])
  

  但也好不了多少（1.1 MB/s）

• 我尝试过sum(s[i:i+block_size]) % modulo，它也很慢

• 有趣的事实：即使没有任何哈希函数，循环本身也很慢！

  t0 = time.time()
  for i in range(len(s)-block_size):
      s[i:i+block_size]
  

  我得到：仅 3.0 MB/s！因此，使用循环访问滚动块的简单事实s已经很慢了。

您建议不要重新发明轮子并编写自己的哈希/或使用自定义 Rabin-Karp 算法，首先加速此循环，然后作为哈希？

---

编辑：上面“有趣的事实”慢循环的（部分）解决方案：

import os, random, time, zlib
from numba import jit

@jit()
def main(s):
    for i in range(len(s)-block_size):
        block = s[i:i+block_size]

total_size = 10*1024*1024  # 10 MB random bytes
block_size = 1024  # 1 KB blocks
s = os.urandom(total_size)
t0 = time.time()
main(s)
print('rolling hashes computed in %.1f sec (%.1f MB/s)' % (time.time()-t0, total_size/1024/1024/(time.time()-t0)))

使用 Numba，有一个巨大的改进：40.0 MB/s，但这里仍然没有完成哈希处理。至少我们在 3 MB/s 时没有被阻塞。

Answer 1

你有什么建议，首先加速这个循环，然后作为哈希？

增加块大小。块大小越小，每个字节执行的 python 就越多，速度就越慢。

编辑：您的范围的默认步长为 1 并且您不乘以i，block_size因此您不是在 10*1024 个不重叠的 1k 块上迭代，而是在 1000 万 - 1024 个大部分重叠的块上迭代