Python中的非常快的滚动哈希？

Question

我正在用Python编写一个类似于rsync的玩具工具。与许多类似的工具一样，它首先使用非常快的哈希作为滚动哈希，一旦找到匹配项，就会使用SHA256（但后者不是本文的重点：SHA256、MD5等作为滚动哈希太慢了）。

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

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？

• I tried with

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

  but it's not much better (1.1 MB/s)

• I tried with sum(s[i:i+block_size]) % modulo and it's slow too

• Interesting fact: even without any hash fonction, the loop itself is slow!

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

  I get: 3.0 MB/s only! So the simpe fact of having a loop accessing to a rolling block on s is already slow.

不要重复造轮子并编写自己的哈希函数/或使用自定义的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。

- Basj

---

每次重新计算整个块的哈希不是“滚动哈希”。你只需计算一次完整的哈希，然后对于每个步骤，您仅使用两个字节的数据更新该计算 - 刚刚在开头退出块的字节和刚刚在结尾进入块的字节。这与大多数哈希函数不兼容，但如果您使用所有字节的总和或XOR，则非常简单。 - jasonharper

@jasonharper 即使使用滑动窗口循环且没有哈希，速度已经很慢了（2.4MB/s）。我找到的唯一方法是使用Numba（请参见最后更新的问题）。 - Basj

你的循环仍然在每一步中制作一个块大小的数据切片 - 这是大量不必要的数据复制。 - jasonharper

@jasonharper 我认为 block = s[i:i+block_size] 不会复制，它只是对该块的引用/视图，这样对吗？ - Basj

我认为任何内置的Python类型在切片时都不会创建对现有对象的视图（这是一种有些问题的方法 - 很容易因为微小的切片而遇到由于原始对象保持活动状态而导致的内存问题）。您必须使用numpy才能获得该行为。 - jasonharper

Answer 1

不要重新发明轮子并编写自己的哈希函数/或使用自定义的Rabin-Karp算法，你有什么建议来加快这个循环的速度，并作为一个哈希函数？

始终以这种心态开始是很好的，但似乎你没有理解滚动哈希的概念。对于滚动哈希函数来说，使其变得出色的是它能够重用之前的处理结果。

一些哈希函数允许非常快速地计算滚动哈希——只需给定旧哈希值、从窗口中移除的旧值和添加到窗口中的新值，就可以迅速计算出新的哈希值。

（来自同一wikipedia页面）

在没有timeit的情况下很难跨不同机器比较性能，但我改变了你的脚本，使用了简单的多项式哈希函数和一个素数模数（使用Mersene prime可能会更快，因为模运算可以通过二进制操作完成）。

import os, random, time

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

base = 256
mod  = int(1e9)+7

def extend(previous_mod, byte):
    return ((previous_mod * base) + ord(byte)) % mod

most_significant = pow(base, block_size-1, mod)

def remove_left(previous_mod, byte):
    return (previous_mod - (most_significant * ord(byte)) % mod) % mod
    
def start_hash(bytes):
    h = 0
    for b in bytes:
        h = extend(h, b)
    return h

t0 = time.time()

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

显然，你在使用Numba方面取得了相当大的进步，它也可能加速这段代码。 为了提高性能，你可以编写一个C语言（或其他低级语言如Rust）函数，一次处理一个大的列表切片，并返回一个包含哈希值的数组。

我也正在创建一个类似于rsync的工具，但由于我是用Rust编写的，所以性能在这个层面上并不是我的关注点。相反，我正在遵循rsync的创建者的建议，尽可能地并行化所有操作，这在Python中是一项艰巨的任务（可能没有Jython就无法实现）。

- Daniel Mitre

Answer 2

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

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

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

- Masklinn

---

这并不像这样简单（你可以尝试使用更高的 block_size 值来运行我的代码）。 - Basj

确实如此，我想我刚刚意识到问题所在：您没有按块大小进行步进，因此您正在对每个字节哈希一个块。而不是哈希10k个块，您正在哈希1m（大部分重叠的）块。 - Masklinn

确切地说，就像@Masklkinn所说的那样！在分析文件old.raw和new.raw之间的更改时，始终有可能在文件中间插入单个字节，因此必须计算滚动哈希，步长为1。 - Basj

Answer 3

首先，你的循环速度较慢。正如已经提到的，你正在为流中的每个字节（块大小以下）切割一个新块。这对CPU和内存都是很大的负担。

更快的循环方法是将数据预先分块成并行位。

chunksize = 4096 # suggestion
# roll the window over the previous chunk's last block into the new chunk
lastblock = None
for readchunk in read_file_chunks(chunksize):
    for i in range(0, len(readchunk), blocksize):
        # slice a block only once
        newblock = readchunk[i:blocksize]
        if lastblock:
            for bi in range(len(newblock)):
                outbyte = lastblock[bi]
                inbyte = newblock[bi]     
                # update rolling hash with inbyte and outbyte
                # check rolling hash for "hit"
        else:
            pass # calculate initial weak hash, check for "hit"
        lastblock = newblock

Chunksize 应该是块大小的倍数

接下来，你在依次计算每个块的整体“滚动哈希”，而不是以“滚动”方式逐字节更新哈希。这样会非常慢。上面的循环强制你在字节进出窗口时进行处理。尽管如此，我的测试显示吞吐量相当低（~3Mbps~编辑：抱歉，应该是3MiB/s），即使对每个字节进行了适度数量的算术运算。编辑：我最初使用了zip()，但它似乎很慢。仅使用循环而不使用zip（当前代码如上）可以获得两倍以上的吞吐量。

Python 是单线程和解释型的。我看到一个CPU被卡住了，这就是瓶颈所在。要想更快，你需要多个线程（子进程）或者转换成C语言，或者两者兼备。仅仅在C语言中运行数学计算可能已经足够了，我想。（哈哈，“仅仅”）

- vontrapp

---

看起来 Python 的迭代速度似乎无法更快了。我编写了一个小的 C 程序来读取文件并为每个输入字节（减去第一个块）输出一个 4 字节的“fastsum”。这个程序单独运行时速度超过 1.2Gbps（从 nvme 读取）。但如果将其输出导入到一个 Python 脚本中，该脚本会对每个 4 字节的和进行计算（不执行任何操作，只是进行迭代），这会使文件输入速度降至不到 20Mbps。:( - vontrapp