New best known functions

[TheIronBorn]

I used this project to learn combinatorial optimization.

UPDATE: a better function was found in a below comment, the new best is now 0.10704308166917044

[16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501

A metaheuristic was used with an estimate with len = 1 << 25 and constrained to be nearby other good functions (shifts [13, 19], muls popcnt [11, 19]). (Unfortunately I don't remember which metaheuristic I used for this). Finally an exhaustive exact search was applied nearby the best found. I verified the final bias with the hash-prospector library itself.

I also used some explicit SIMD acceleration in the bias calculation along with the current multi threading. The hash itself handles 8 "seeds" at once and the counting is faster too.
SIMD counting pseudo code:

// 256/32=8 so splat the 32-bit flips and use a mask to grab them all at once
__m256i sequence = _mm256_set_epi32(0, 1, 2, 3, 4, 5, 6, 7);
__m256i mask = _mm256_sllv_epi32(_mm256_set1_epi8(1), sequence);

for (int i = 0; i < 8; ++i) {
    __m256i splat = _mm256_set1_epi32(_mm256_extract_epi32(flips, i));
    __m256i flipped = _mm256_cmpeq_epi8(_mm256_and_si256(splat, mask), mask);
    byte_bins = _mm256_sub_epi8(byte_bins, flipped);
}

// accumulate intermediate byte bins to larger bins every 255 / 8

[skeeto]

Fascinating! This is such a big jump from my best, too. Since it's highly unlikely that there are better permutations outside those shift+popcnt constraints, and you did an exhaustive search, I suppose that means these are probably the best possible parameters (by this heuristic)? As in I should stop searching this particular space (not that I'm actively doing so now). I don't understand the role of "len = 1 << 25" so could you elaborate on that part?

[TheIronBorn]

I don't understand the role of "len = 1 << 25" so could you elaborate on that part?

I set score_quality of estimate_bias to 25

Also the final exact search only searched within 4 "neighborhood" steps of the initial so I think there may still be some multipliers that were not seen.

[TheIronBorn]

Here are some others for posterity

[16 23f0aaab 15 d35a2d97 15] = 0.13066275031171543
[16 20f0aaab 15 d35a2d97 15] = 0.13195879287932719
[16 21e0aaab 15 d35a2d97 15] = 0.13195905170130587
[16 a1f0aaab 15 d35a2d97 15] = 0.13269751635322202
[16 61f0aaab 15 d35a2d97 15] = 0.13305154922498447
[16 21f0eaab 15 d35a2d97 15] = 0.13363433980870795
[16 01f0aaab 15 d35a2d97 15] = 0.13404371380695335
[16 21f02aab 15 d35a2d97 15] = 0.13502476643020897
[16 21f0aaab 15 db5a2d97 15] = 0.13565766967918283
[15 21f0aaab 15 d35a2d97 15] = 0.1367387725165565
[16 21f0aaab 15 c35a2d97 15] = 0.13741914434507
[16 21f0aaab 15 f35a2d97 15] = 0.1379071419852113
[16 21f0aaab 15 535a2d97 15] = 0.13986211866666148
[16 21f0aaab 15 935a2d97 15] = 0.14007263708693393
[16 21f0aaab 15 d25a2d97 15] = 0.1407202290848398
[16 21f0aaab 15 d3da2d97 15] = 0.14336270330186673
[16 31f0aaab 15 d35a2d97 15] = 0.14339325760142133
[16 29f0aaab 15 d35a2d97 15] = 0.14363985334436025
[16 21f0aaa9 15 d35a2d97 15] = 0.1453336983612932
[16 21f8aaab 15 d35a2d97 15] = 0.1457843639293307
[16 21b0aaab 15 d35a2d97 15] = 0.1462415903758569
[16 21f0aaab 15 d75a2d97 15] = 0.14692234324205752
[16 21f0aaab 15 d35e2d97 15] = 0.14916750980179216
[16 21f0aaab 15 d15a2d97 15] = 0.1497718718021898
[16 21f1aaab 15 d35a2d97 15] = 0.15017720286015981
[16 21d0aaab 15 d35a2d97 15] = 0.1511000121456908
[16 21f0aaab 15 d3522d97 15] = 0.1513531790691242
[16 25f0aaab 15 d35a2d97 15] = 0.15256373883426125
[16 2170aaab 15 d35a2d97 15] = 0.15336204601641212
[16 21f0aaab 15 d31a2d97 15] = 0.15595696330990985
[16 21f0aaeb 15 d35a2d97 15] = 0.15696481972915902
[16 21f0aa8b 15 d35a2d97 15] = 0.15806891443846496
[16 21f0aaab 15 d37a2d97 15] = 0.15813387758513106
[16 21f0aaab 15 d35b2d97 15] = 0.15821584918520273
[16 21f0baab 15 d35a2d97 15] = 0.158832616180062
[17 21f0aaab 15 d35a2d97 15] = 0.16142064258064714

[TheIronBorn]

Some more

[15 21f0aaad 15 d35a2d97 15] = 0.1133028300049351
[16 450c2d35 15 caf649a9 16] = 0.12242779617496825
[16 c50c2d35 15 caf649a9 16] = 0.12390420060083929
[16 450c2d35 15 eaf649a9 16] = 0.12425550094456454
[16 450c2d35 15 6af649a9 16] = 0.12489788028691867
[16 050c2d35 15 eaf649a9 16] = 0.12541563776043774
[16 c50c2d35 15 eaf649a9 16] = 0.12566685457424706
[16 450c2d35 15 aaf649a9 16] = 0.12643361749669804
[16 0d0c2d35 15 eaf649a9 16] = 0.12663917962201937
[16 450c2d35 15 eae649a9 16] = 0.12730634146451852
[16 450c2d35 15 e8f649a9 16] = 0.12745444770306463
[16 d30332d3 15 c865c965 15] = 0.12786059224340487
[16 4d0c2d35 15 caf649a9 16] = 0.12891794597259876
[16 930332d3 15 c865c965 15] = 0.12895521715629882
[16 410c2d35 15 eaf649a9 16] = 0.12931407115109045
[16 5d0c2d35 15 eaf649a9 16] = 0.1293659073313086
[16 130332d3 15 c865c965 15] = 0.12941101452563722
[16 4d0c2d35 15 eaf649a9 16] = 0.13032013174253892

[TheIronBorn]

And just for fun, new best known functions for other types:

16-bit 2-round (17.5 minutes, 970,000 unique exact bias calculations):
[8 a3d3 7 4b2d 9] = 0.007252938393705358
16-bit 3-round (21 minutes, 1,100,000 unique exact bias calculations):
(lower bias limit is 0.00390625)
[11 b663 3 897d 6 ea57 8] = 0.0043694522287830665
and 16-bit 4-round w/o mul (43 minutes, 2,100,000 unique exact bias calculations):
[4 7 2 5 3 4 8 6] = 0.0056453446937279736
a significant jump from 0.02384 for 3-round

No improvement was found for 16-bit w/o mul 3-round. There are only ~11.5 million so a brute force global search might be feasible though likely unnecessary.

I used a generic implementation of this memetic algorithm with dynamic population management for each of these with the following specifics:

• maxcross = 500
• a neighborhood of shift+/-1 and flipping each bit in mul (except 0th), shuffled before each local search
• first improving local search, stopped after 11 steps or a local optimum
• pattern mining was applied to each local search
• bias evaluations were cached to speed up local search (a lot of duplicate neighbors, a->b encounters a again)

[TheIronBorn]

As mentioned in #12, I found a new best

[16 21f0aaad 15 f35a2d97 15] = 0.10734781817103507

[TheIronBorn]

Yet another new best:

[16 21f0aaad 15 735a2d97 15] = 0.10704308166917044

which is a local optimum. Note that it's not a local optimum by the math in #12

[OneKnightOnly]

Very impressive results. Have you made any progress with 64 bit hashes? perhaps it would be easier to treat the 64 bit hash as producing two 32 bit hashes, then you'd have two exact bias numbers, instead of one estimate.

[TheIronBorn]

I haven’t done any work on 64-bit hashes since they are already so close to optimal

[TheIronBorn]

Sorry, my bad, I confused 64-bit with 32-bit 3-round hashes.
No I haven't worked on 64-bit hashes

[Marc-B-Reynolds]

FWIW: Here's a structure I keep meaning to put some effort into but haven't gotten around to yet. The constants are all ad-hoc (no attempt at optimization)

static inline uint32_t crc32c(uint32_t x, uint32_t k) { return _mm_crc32_u32(x,k); }

uint32_t hash(uint32_t x)
{
  x  = crc32c(x,0x9e3d2c1b); x *= 0x9e485565;
  x  = crc32c(x,0x9e3d2c1b); x *= 0x9e485565;
  return x;
}

[TheIronBorn]

After a bit of optimization that structure seems quite strong:

[7cdff266 9c80bf99 f789c7a9 0c9cb5b5] = 0.05108489705921976

About twice as good as the "classic" hash function here and a significant jump from the previous work on CRC #13 (comment)

Unfortunately it doesn't vectorize as well so optimization/searching is slower