Hash Function Change - Murmur hash and true per process hash seed

This patch does the following:

*) Introduces multiple new hash functions to choose from at build
time. This includes Murmur-32, SDBM, DJB2, SipHash, SuperFast, and
One-at-a-time. Currently this is handled by muning hv.h. Configure
support hopefully to follow.

*) Changes the default hash to Murmur hash which is faster than the
old default One-at-a-time.

*) Rips out the old HvREHASH mechanism and replaces it with a
per-process random hash seed.

*) Changes the old PL_hash_seed from an interpreter value to a
global variable. This means it does not have to be copied during
interpreter setup or cloning.

*) Changes the format of the PERL_HASH_SEED variable to a hex
string so that hash seeds longer than fit in an integer are possible.

*) Changes the return of Hash::Util::hash_seed() from a number to a
string. This is to accomodate hash functions which have more bits than
can be fit in an integer.

*) Adds new functions to Hash::Util to improve introspection of hashes

  -) hash_value() - returns an integer hash value for a given string.
  -) bucket_info() - returns basic hash bucket utilization info
  -) bucket_stats() - returns more hash bucket utilization info
  -) bucket_array() - which keys are in which buckets in a hash

More details on the new hash functions can be found below:

    Murmur Hash: (v3) from google, see
        http://code.google.com/p/smhasher/wiki/MurmurHash3

    Superfast Hash: From Paul Hsieh.
        http://www.azillionmonkeys.com/qed/hash.html

    DJB2: a hash function from Daniel Bernstein
        http://www.cse.yorku.ca/~oz/hash.html

    SDBM: a hash function sdbm.
        http://www.cse.yorku.ca/~oz/hash.html

    SipHash: by Jean-Philippe Aumasson and Daniel J. Bernstein.
        https://www.131002.net/siphash/

They have all be converted into Perl's ugly macro format.
I have not done any rigorous testing to make sure this conversion
is correct. They seem to function as expected however.

All of them use the random hash seed.

You can force the use of a given function by defining one of

    PERL_HASH_FUNC_MURMUR
    PERL_HASH_FUNC_SUPERFAST
    PERL_HASH_FUNC_DJB2
    PERL_HASH_FUNC_SDBM
    PERL_HASH_FUNC_ONE_AT_A_TIME

Setting the environment variable PERL_HASH_SEED_DEBUG to 1 will make
perl output the current seed (changed to hex) and the hash function
it has been built with.

Setting the environment variable PERL_HASH_SEED to a hex value will
cause that value to be used at the seed. Any missing bits of the seed
will be set to 0. The bits are filled in from left to right, not
the traditional right to left so setting it to FE results in a seed
value of "FE000000" not "000000FE".

Note that we do the hash seed initialization in perl_construct().
Doing it via perl_alloc() (via init_tls) causes problems under
threaded builds as the buffers used for reentrant srand48 functions
are not allocated. See also the p5p mail "Hash improvements blocker:
portable random code that doesnt depend on a functional interpreter",
Message-ID:
<CANgJU+X+wNayjsNOpKRqYHnEy_+B9UH_2irRA5O3ZmcYGAAZFQ@mail.gmail.com>

1 files changed, 4 insertions, 0 deletions

diff --git a/perlapi.h b/perlapi.h
index 80425c368c..910f789540 100644
--- a/perlapi.h
+++ b/perlapi.h
@@ -115,6 +115,10 @@ END_EXTERN_C
 #define PL_dollarzero_mutex	(*Perl_Gdollarzero_mutex_ptr(NULL))
 #undef  PL_fold_locale
 #define PL_fold_locale		(*Perl_Gfold_locale_ptr(NULL))
+#undef  PL_hash_seed
+#define PL_hash_seed		(*Perl_Ghash_seed_ptr(NULL))
+#undef  PL_hash_seed_set
+#define PL_hash_seed_set	(*Perl_Ghash_seed_set_ptr(NULL))
 #undef  PL_hints_mutex
 #define PL_hints_mutex		(*Perl_Ghints_mutex_ptr(NULL))
 #undef  PL_keyword_plugin