These are a bunch of experiments, and results on rolling hash algorithms, trying variants and analysing how well they perform. This was prompted by work on the librsync hashtable which identified that the librsync rollsum had nasty clustering behaviour that required adding a MurmurHash3 mix32() finalizer to get decent open addressing hashtable performance. This suggested that the rollsum hash was far from optimal.
Initially this was used to analyse librsync's adler32/fletcher based rollsum and try variants to improve it. After that was exhausted, a tiny bit of research found the Wikipedia Rolling_hash page that included RabinKarp and CyclicPolynomial rolling hash algorithms. I added these algorithms with similar variations as used for the rollsum for comparison.
Martin Pool <[email protected]> for librsync. Martin Nowak <[email protected]> for pointing out how bad rollsum clusters and how MurmurHash's mix32() can fix it.
See LICENSE for the copyright and licencing details.
There is nothing to install here, just scripts to run and data to use.
For rollsum.py help run:
$ ./rollsum.py -h
To run rollsum.py to get detailed stats for a RabinKarp rolling hash:
$ ./rollsum.py -R rk -B 1K -C 1000000 --seed=1 --offs=0 \ --mult=0x41c64e6d --map=ord --indexbits=20 <data/csv.dat
To run rollsum.py for a bunch of librsync rollsum variants and output a summary:
$ run.sh -B 1K -C 1000000 ./data
To generate comparisons of rollsum, RabinKarp, and CyclicPoly hashes:
$ cmptest.py
- http://minkirri.apana.org.au/wiki/LibrsyncRollsumAnalysis
- Some early analysis and observations.
- http://github.com/dbaarda/rollsum-tests
- The project on github.
- RESULTS.rst
- Detailed analysis and comparisons of different rolling hash algorithms and their variants.
For any questions send email to [email protected] or use the github issue tracker.
Report any problems on the github issue tracker.
These scripts are a bit ad-hoc and were heavily modified and tweaked during various exploritory experiments. It is possible they still contain fragments of dead or broken code from old experiments that never got cleaned up.
Some result data provided may have been generated from older variants of the scripts and do not reflect the current output. Not all the result data that guided the experiments and contibuted to conclusions is provided or was kept.
Not so much designed, as evolved...
The results of this analysis will probably be used to implement a RabinKarp rollsum in future versions of librsync.
Unfortunately the early development history was not checked into git.
http://project/url/README