On Apr 24, 2006, at 15:10, Davide Libenzi wrote:
Right, but you are looking at highest equal-probability distribution over your hash buckets ;) Anyway, thanks for bringing Rabin's polynomial fingerprint up from the forgotten lands. Performance and delta size are quite amazing, and I decided to add Rabin's delta to libxdiff. I hacked some code (attached) to generate T/U tables. Since libxdiff must be portable everywhere, even on system w/out 64 bits support, I use xrabin to create both 64 bits tables (poly degree 61) and 32 bits tables (poly degree 31), and store them in a .c file letting the build environment to pick the correct one for the platform.
It might actually make sense to use the 32-bit code for GIT as well, since it turns out that on the typical small source files with few differences, the full 64-bit Rabin is a problem for performance. When diffing large files (my main interest), this is more than offset by the better hash quality. For tiny files with few changes it appears to be overkill... -Geert - : send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html