Some high-level comments:

• Some applications rely on persistent hash tables, i.e. hash tables that
  are saved to disk using output_value. Changing the hash function will
  cause the hash table read back with input_value to be unusable. When we
  switched to MurmurHash and seeded hash tables, I put ugly hacks in stdlib/
  hashtbl.ml so that "old" hashtables (created with the old hash function)
  would still be usable. I'm afraid those hacks cannot be extended to cover
  yet another hash function. Bottom line: if we change the hash function, we
  must outlaw this use of persistent hash tables and break some
  applications. (SpamOracle is one example.)
• Passing the hash state by reference rather than by value (as an argument
  and a result) is a good design.
• SipHash uses the type uint64_t from ISO C99, which is not guaranteed to
  be there in ISO C90. We've been thinking of using C99 rather than C90 as
  the baseline for the OCaml runtime system. This would simplify other
  things. But it means this patch should not be merged before this switch to
  C99 is completed.
• Don't use alloca(), please. It is not standardized in any way, neither
  in ISO C nor in POSIX.

I think this patch would really benefit from having a dedicated testsuite. I would expect at least:

• known-hash tests to make sure that this implementation really corresponds to SipHash
• performance-stressing code that easily allows to reproduce performance evaluation on various datatypes; Besides performance regression (of course), I'd be curious about performance on 32-bit machines.

@gashe As mentioned in the caveats, I haven't written/fixed the testsuite yet.
I was indeed planning on using known hashes for strings (generated, for instance, with the reference implementation); this ties in with the change in length handling.
Regarding benchmarking, I have a draft benchmark that still needs some work.

@xavierleroy I used uint64 as it was already defined and used elsewhere, but it indeed wouldn't work when ARCH_INT64_TYPE isn't defined.
Is there a more appropriate type, or should we wait until the codebase switched over to C99?

Also, regarding the use of alloca(3) (which is indeed bad practice), should an automatic array be used (I'm not sure about its availability in C90), or should I just heap-allocate the state for the hash function (and pay the associated performance penalty) ?

@bobot The trivial collision occur before the integers are even fed to the hash function.
Basically, the higher and lower 32bits are xor-ed together (plus some fiddling with the sign bit).

Here is some quick-and-dirty code (for 64-bits machines) to generate universal collisions with a small integer:

let x0 = 123456 in (* We want many universal collisions with x0 *)
    assert(0 <= x0 && x0 < 1 lsl 32 && Sys.word_size = 64);
    for i=0 to 50_000 do (* The 50 000 bound is arbitrary *)
        let x = (x0 lxor i) lor (i lsl 32) in
        Printf.printf "%x hashes to %x\n" x @@ Hashtbl.hash x
    done

PS: The collisions are universal in the sense that, using the keyed hash function Hashtbl.seeded_hash, one gets a collision regardless of the hash function's key.

Also, regarding the use of alloca(3) (which is indeed bad practice), should an automatic array be used (I'm not sure about its availability in C90), or should I just heap-allocate the state for the hash function (and pay the associated performance penalty) ?

Perhaps I'm missing something obvious but when I looked at the patch yesterday, I was thinking to myself: "Why doesn't he just use a char a[CAML_HASH_T_SIZE] here?"

SipHash uses the type uint64_t from ISO C99, which is not guaranteed to be there in ISO C90.

Is that really an issue? Are there systems out there that ocaml supports that have neither a uint64_t or unsigned long long type? While purely anecdotal, I don't think I've seen any such system in the last 10 years, if not longer.

I would be more worried on the performance impact on 32 bits architectures. 32 bits ARM has instructions that let you do 64 bits arithmetic reasonably efficient but x86 probably has to go about it the long and slow way.

Then again, most operations here are very basic. I wouldn't be surprised if gcc at -m32 -O3 manages to crank out something that's close to optimal.

Are there systems out there that ocaml supports that have neither a
uint64_t or unsigned long long type?

I don't think so, and I'm willing to stop supporting them by removing the
64-bit integer emulation code in the OCaml runtime. My remark was just
that if we integrate this SipHash24-based code that uses native 64-bit
integers, it makes sense to do it while or after we remove this 64-bit
integer emulation code and switch to C99 in the runtime system.

I would be more worried on the performance impact on 32 bits architectures.

32 bits ARM has instructions that let you do 64 bits arithmetic reasonably
efficient but x86 probably has to go about it the long and slow way.

I use SipHash24 as a C benchmark in another context, and gcc generates very
reasonable x86-32 code for it, even at -O1. The only compiler that I saw
producing bad code for SipHash24 is gcc 4.2 on PowerPC 32-bits, for unknown
reasons.

A lot of effort are put into having the best hash functions for the polymorphic hash function of ocaml. Perhaps these hash functions should be accessible from ocaml (using external or better written in ocaml) in order to help the implementation of hash function in ocaml. Often people use combination function that must appear childish for specialist [0][1]:

let combine acc n = n * 65599 + acc

People can use an external library for that, but since the work is done in byterun/, it may be shared in stdlib/.

I second @bobot, it would be very interesting to have efficient, well-behaved built-in hash combinators for hashconsing-lovers (or other people who write their own hash functions).

In the spirit of @bobot's combine, it should be possible to expose the basic hash function:

• type t an opaque for the state of the hash function
• val init: Int32.t -> t builds the initial state from the key (I would be much happier with greater bit-width for keys and outputs, though)
• val compress: t -> Int64.t -> unit the compression function
• val final: t -> int (same issue with bit-width as init)

However, it is probably an orthogonal issue (though the refactoring of the API exposed in hash.h helps).

Yes, I should have said that it is orthogonal and shouldn't go in this merge request. But if someone want to write the code to make a new one, I expect it to be well received.

Here are some benchmarks I performed a few weeks ago; I still haven't benchmarked the impact on Hashtbl, as I couldn't find resources describing methodologies for benchmarking hash-tables.

As shown, the implementation needs some more work. The good news is that it was still fairly naive, and taking advantage of vectorization (either using hand-coded sipround() implementations and #ifdefs or more aggressive compiler optimizations, such as -O2 -ftree-vectorize) should help.

|          | SipHash            | 4.01.0              | Perf. hit |
| 32 chars | 17180522+- 25216/s | 37426014+- 80465/s  | 54.1%     |
| short    | 29820904+-954953/s | 62954641+- 96766/s  | 52.6%     |
| empty    | 30460935+-194229/s | 75118409+-206777/s  | 59.4%     |
|          |                    |                     |           |
| int      | 41318929+-127003/s | 116654005+-181840/s | 63.7%     |
| int64    | 33405769+-38009/s  | 76119185+-125293/s  | 56.1%     |
| int32    | 34526086+-18271/s  | 85051965+-149087/s  | 59.4%     |

PS: The benchmark was ran on my laptop (Core i5, amd64, Linux)

This PR has been sleeping for a long time, sorry about that. In the meantime, a few things happened:

• I mentioned a switch to ISO C99 standard integer types (uint64_t, etc) in the OCaml runtime system. This is now done in the trunk, so that's one less obstacle to putting Siphash there.
• I convinced myself that we don't need to maintain backward compatibility for hash tables that are persistent (e.g. stored in files using output_value). It will take some explaining to users, and we should provide functions to help migrating hash tables to a new hash function. But the consequence is that we can consider a change of hashing algorithm serenely.
• I did some benchmarking of my own on Siphash. Bottom line: yes, it is significantly slower than Murmur 3, especially on 32-bit architectures. What I measured is the speed of Hashtbl.seeded_hash_param, the core primitive.
  On x86-64 bits (Core i7): hashing time increases by 30% to 80% depending on data.
  On x86-32 bits (Core i7): +300% to +500% (ouch!).
  On ARMv7 32 bits (CubieTruck): +180% to +330%.
• The issue with Murmur3 is not that it has collisions. With our small key space (30 bits), collisions are to be expected as soon as we have about 2^15 entries, whether we're using Siphash or Murmur3. The real issue, as demonstrated by Aumasson and Bernstein, is that Murmur3 has collisions that are independent of the seed, therefore bypassing the random seeding of hash tables and opening up a security hole. I wish someone would come up with a Murmur3-like hash function (i.e. small key size, fast even on 32-bit machines) that mixes the random seed better, to thwart this attack. But Web searches found nothing of that kind.

Some thoughts:

• siphash24 is overkill even if siphash is considered for usage. Even siphash13 gives enough avalanche and certainly safe for use in hash table.

  I asked Jean-Philippe Aumasson about, and he had confirmed:

your arguments make a lot of sense: we proposed SipHash-2-4 as a
(strong) PRF/MAC, and so far no attack whatsoever has been found,
although many competent people tried to break it. However, fewer
rounds may be sufficient and I would be very surprised if
SipHash-1-3 introduced weaknesses for hash tables.

• i think 32bit counterpart of siphash is safe for this usecase too (ie using 432bit internal state and producing 32bit result instead of 464bit state and 64bit result) and has much better performance on 32bit cpu.

  https://github.com/funny-falcon/funny_hash/blob/master/others/csaphash.h

• I've made Murmur3-like hash function which has equal performance (32bit version) and much harder to break. (though I cannot proove it is unbreakable like SipHash)

  https://github.com/funny-falcon/funny_hash/blob/master/funny_hash.h

Is there any way to have some global in Hashtbl that will set which hash function we want to use? Having hash_secure and hash_fast, one of which will alias to 'hash' based on a global, seems like a decent solution to me. I'd rather not incur a performance penalty on every hashtable, especially when this concerns only a small subset of applications.

Is there any way to have some global in Hashtbl that will set which hash function we want to use?

Please don't. Hashtbl.Make is made for that.

Fine. But should the default then be fast or secure? I could make the argument that if you're writing for domains where security is critical, you should be using Hashtbl.Make for that.

And can we still have access to the old, fast hash, since I use Hashtbl.hash in many places that don't have to do with hash tables? I would like to maintain that fast hash as Hashtbl.hash_fast

@funny-falcon: thanks a lot for those pointers. It could very well be that your 32-bit "Saphash" variant is fast enough and strong enough for our purposes. When I find the time I'll redo my measurements using Saphash and Siphash13 instead of Siphash24.

@bluddy: OCaml's historic hash function (the one we used before Murmur3) isn't that fast -- Murmur3 is faster on strings, if I remember correctly -- and really bad distribution-wise. I'd rather have a single hash function that is good enough and fast enough for most uses.

The resolution of this PR is near, see #9764 .

Seems that this can be subsumed by #9764?

Seems that this can be subsumed by #9764?

Yes, that's fair. However, #9764 is kind of stuck on how to treat structured values so as to avoid trivial collisions, so we're not done yet...