Author tim.peters
Recipients eric.smith, jdemeyer, mark.dickinson, rhettinger, sir-sigurd, tim.peters
Date 2018-09-25.01:51:49
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1537840310.17.0.545547206417.issue34751@psf.upfronthosting.co.za>
In-reply-to
Content
And one more:

        x = (x * mult) ^ t;

also appears to work equally well.  So, way back when, it appears we _could_ have wormed around the disaster du jour just by applying a shift-xor permutation to the raw hash results.

Note the implication:  if we believed our tuple hash worked OK before then (& we did), adding a shift-xor step would have changed nothing about it _except_ to permute the input space.  That alone was enough to repair the nested tuple problems.

Note that permutations are a bog standard way to improve algorithms with bad behaviors in some cases.  For example, at the end of the Mersenne Twister they do 4 permutations to improve otherwise-marginal results from "the real" pseudo-random generator:

    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680U;
    y ^= (y << 15) & 0xefc60000U;
    y ^= (y >> 18);
    return y;

At this point I see no "good reason" to prefer any of

    x = (x * mult) ^ t; // like Bernstein 33X & FNV-1
    x = (x * mult) + t; // like Bernstein 33A
    x = (x ^ t) * mult; // like FNV-1a

to any other.  In their _original_ contexts, they were applied to longish sequences of unsigned bytes.  But tuples used as keys and set elements are typically much shorter than strings, so results about how they worked in their original contexts are largely irrelevant for that reason too.

While lots of non-endcase testing is also needed, at this point I don't have any real fear about any of them.

As a sanity check,

        x = (x * mult) | t;

is disastrous for all the endcase tests.  So I believe I really am compiling and running the code ;-)
History
Date User Action Args
2018-09-25 01:51:50tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, eric.smith, jdemeyer, sir-sigurd
2018-09-25 01:51:50tim.peterssetmessageid: <1537840310.17.0.545547206417.issue34751@psf.upfronthosting.co.za>
2018-09-25 01:51:50tim.peterslinkissue34751 messages
2018-09-25 01:51:49tim.peterscreate