Re: [PATCH 2/2] diff.c: get rid of duplicate implementation

On Mon, Oct 30, 2017 at 10:59:41AM -0700, Jeff King wrote:

quoted

There's also https://www.strchr.com/hash_functions, which lists DJB2
as Bernstein.  Both functions rank somewhere in the middle of that list.

FWIW, I did some experiments with Murmur3 and SipHash a while back, but
I don't think I came up with anything faster than the existing code.
OTOH, moving to SipHash gives us the ability to randomize the hashes,
which can resist some DoS attacks (although as I've said before,
computing arbitrary diffs for untrusted strangers is pretty much a
DoS-in-a-box).

By the way, one of the things that complicates plugging new functions
into xdiff's hashing is that xdl_hash_record() simultaneously computes
the hash _and_ finds the end-of-line marker.

So the "siphash is only 10% slower" number I showed came with quite a
few contortions to do both. Here it is compared to a more naive
application of the siphash code (i.e., memchr to find end-of-line, and
then feed the resulting bytes to siphash):

Test                                  origin            HEAD^                    jk/xdl-siphash-wip
-------------------------------------------------------------------------------------------------------
4000.1: log -3000 (baseline)          0.05(0.05+0.00)   0.05(0.05+0.00) +0.0%    0.05(0.05+0.00) +0.0%
4000.2: log --raw -3000 (tree-only)   0.31(0.27+0.03)   0.31(0.27+0.03) +0.0%    0.31(0.27+0.03) +0.0%
4000.3: log -p -3000 (Myers)          2.06(2.01+0.05)   2.30(2.21+0.09) +11.7%   2.96(2.91+0.04) +43.7%
4000.4: log -p -3000 --histogram      2.44(2.38+0.06)   2.67(2.60+0.07) +9.4%    3.32(3.26+0.06) +36.1%
4000.5: log -p -3000 --patience       2.57(2.47+0.09)   2.90(2.82+0.08) +12.8%   3.48(3.43+0.05) +35.4%

There "origin" is the existing djb hash, "HEAD^" is the complicated
"fast" siphash (which I very well may have screwed up), and the final is
the more naive version, which is quite a bit slower.

-Peff