Very fast rolling hash in Python?

Question

I'm writing a toy rsync-like tool in Python. Like many similar tools, it will first use a very fast hash as the rolling hash, and then a SHA256 once a match has been found (but the latter is out of topic here: SHA256, MDA5, etc. are too slow as a rolling hash).

I'm currently testing various fast hash methods:

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)))

I get: 0.8 MB/s ... so the Python built-in hash(...) function is too slow here.

Which solution would allow a faster hash of at least 10 MB/s on a standard machine?

• 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.

Instead of reinventing the wheel and write my own hash / or use custom Rabin-Karp algorithms, what would you suggest, first to speed up this loop, and then as a hash?

---

Edit: (Partial) solution for the "Interesting fact" slow loop above:

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)))

With Numba, there is a massive improvement: 40.0 MB/s, but still no hash done here. At least we're not blocked at 3 MB/s.

Answer 1

Instead of reinventing the wheel and write my own hash / or use custom Rabin-Karp algorithms, what would you suggest, first to speed up this loop, and then as a hash?

It's always great to start with this mentality, but seems that you didn't get the idea of rolling hashes. What makes a hashing function great for rolling is its capability of reusing the previous processing.

A few hash functions allow a rolling hash to be computed very quickly—the new hash value is rapidly calculated given only the old hash value, the old value removed from the window, and the new value added to the window.

From the same wikipedia page

It's hard to compare performance across different machines without timeit, but I changed your script to use a simple polynomial hashing with a prime modulo (would be even faster to work with a Mersene prime, because the modulo operation could be done with binary operations):

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)))

Apparently you achieved quite a improvement with Numba and it may speed up this code as well. To extract more performance you may want to write a C (or other low-level language as Rust) functions to process a big slice of the list at time and returns an array with the hashes.

I'm creating a rsync-like tool as well, but as I'm writing in Rust performance in this level isn't a concern of mine. Instead, I'm following the tips of the creator of rsync and trying to parallelize everything I can, a painful task to do in Python (probably impossible without Jython).