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

[Jeff King <peff@peff.net>]

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

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