I wrote:
>
> * v8 with chunked interface:
> latency average = 555.688 ms
>
> This starts to improve things for me.
>
> * v8 with chunked, and return lower 32 bits of full 64-bit hash:
> latency average = 556.324 ms
>
> This is within the noise level. There doesn't seem to be much downside
> of using a couple cycles for fasthash's 32-bit reduction.
>
> * revert back to master from Dec 4 and then cherry pick a86c61c9ee
> (save last entry of SearchPathCache)
> latency average = 545.747 ms
>
> So chunked incremental hashing gets within ~2% of that, which is nice.
> It seems we should use that when removing strlen, when convenient.
>
> Updated next steps:
> * Investigate whether/how to incorporate final length into the
> calculation when we don't have the length up front.
> * Add some desperately needed explanatory comments.
> * Use this in some existing cases where it makes sense.
> * Get back to GUC hash and dynahash.
For #1 here, I cloned SMHasher and was dismayed at the complete lack
of documentation, but after some poking around, found how to run the
tests, using the 32-bit hash to save time. It turns out that the input
length is important. I've attached two files of results -- "nolen"
means stop using the initial length to tweak the internal seed. As you
can see, there are 8 failures. "pluslen" means I then incorporated the
length within the finalizer. This *does* pass SMHasher, so that's
good. (of course this way can't produce the same hash as when we know
the length up front, but that's not important). The attached shows how
that would work, further whacking around and testing with Jeff's
prototype for the search path cache hash table. I'll work on code
comments and get it polished.
--- Testing fasthash32 "fast-hash 32bit" with NO LENGTH
[[[ Sanity Tests ]]]
Verification value 0x6A202089 ....... FAIL! (Expected 0xe9481afc)
Running sanity check 1 .......... PASS
Running AppendedZeroesTest .......... PASS
[[[ Keyset 'Sparse' Tests ]]]
Keyset 'Sparse' - 16-bit keys with up to 9 bits set - 50643 keys
Testing collisions ( 32-bit) - Expected 0.3, actual 0 (0.00x)
Testing collisions (high 19-25 bits) - Worst is 20 bits: 1227/1203 (1.02x)
Testing collisions (low 19-25 bits) - Worst is 24 bits: 81/76 (1.06x)
Testing distribution - Worst bias is the 13-bit window at bit 31 - 0.436%
Keyset 'Sparse' - 24-bit keys with up to 8 bits set - 1271626 keys
Testing collisions ( 32-bit) - Expected 188.2, actual 182 (0.97x)
Testing distribution - Worst bias is the 17-bit window at bit 11 - 0.089%
Keyset 'Sparse' - 32-bit keys with up to 7 bits set - 4514873 keys
Testing collisions ( 32-bit) - Expected 2372.2, actual 2286 (0.96x)
Testing distribution - Worst bias is the 19-bit window at bit 23 - 0.044%
Keyset 'Sparse' - 40-bit keys with up to 6 bits set - 4598479 keys
Testing collisions ( 32-bit) - Expected 2460.8, actual 2426 (0.99x) (-34)
Testing distribution - Worst bias is the 19-bit window at bit 25 - 0.041%
Keyset 'Sparse' - 48-bit keys with up to 6 bits set - 14196869 keys
Testing collisions ( 32-bit) - Expected 23437.8, actual 23601 (1.01x) (164)
Testing distribution - Worst bias is the 20-bit window at bit 31 - 0.020%
Keyset 'Sparse' - 56-bit keys with up to 5 bits set - 4216423 keys
Testing collisions ( 32-bit) - Expected 2069.0, actual 1958 (0.95x)
Testing distribution - Worst bias is the 19-bit window at bit 2 - 0.040%
Keyset 'Sparse' - 64-bit keys with up to 5 bits set - 8303633 keys
Testing collisions ( 32-bit) - Expected 8021.7, actual 7994 (1.00x) (-27)
Testing distribution - Worst bias is the 20-bit window at bit 30 - 0.040%
Keyset 'Sparse' - 72-bit keys with up to 5 bits set - 15082603 keys
Testing collisions ( 32-bit) - Expected 26451.8, actual 26503 (1.00x) (52)
Testing distribution - Worst bias is the 20-bit window at bit 11 - 0.021%
Keyset 'Sparse' - 96-bit keys with up to 4 bits set - 3469497 keys
Testing collisions ( 32-bit) - Expected 1401.0, actual 1415 (1.01x) (15)
Testing distribution - Worst bias is the 19-bit window at bit 12 - 0.058%
Keyset 'Sparse' - 160-bit keys with up to 4 bits set - 26977161 keys
Testing collisions ( 32-bit) - Expected 84546.1, actual 84165 (1.00x) (-381)
Testing distribution - Worst bias is the 20-bit window at bit 12 - 0.012%
Keyset 'Sparse' - 256-bit keys with up to 3 bits set - 2796417 keys
Testing collisions ( 32-bit) - Expected 910.2, actual 905 (0.99x) (-5)
Testing distribution - Worst bias is the 18-bit window at bit 21 - 0.056%
Keyset 'Sparse' - 512-bit keys with up to 3 bits set - 22370049 keys
Testing collisions ( 32-bit) - Expected 58155.4, actual 57846 (0.99x) (-309)
Testing distribution - Worst bias is the 20-bit window at bit 6 - 0.013%
Keyset 'Sparse' - 1024-bit keys with up to 2 bits set - 524801 keys
Testing collisions ( 32-bit) - Expected 32.1, actual 35 (1.09x) (3)
Testing distribution - Worst bias is the 16-bit window at bit 13 - 0.118%
Keyset 'Sparse' - 2048-bit keys with up to 2 bits set - 2098177 keys
Testing collisions ( 32-bit) - Expected 512.4, actual 513 (1.00x) (1)
Testing distribution - Worst bias is the 18-bit window at bit 20 - 0.086%
[[[ Keyset 'Permutation' Tests ]]]
Combination Lowbits Tests:
Keyset 'Combination' - up to 7 blocks from a set of 8 - 2396744 keys
Testing collisions ( 32-bit) - Expected 668.6, actual 33953 (50.78x) (33285)
!!!!!
*********FAIL*********
Combination Highbits Tests
Keyset 'Combination' - up to 7 blocks from a set of 8 - 2396744 keys
Testing collisions ( 32-bit) - Expected 668.6, actual 33990 (50.84x) (33322)
!!!!!
*********FAIL*********
Combination Hi-Lo Tests:
Keyset 'Combination' - up to 6 blocks from a set of 15 - 12204240 keys
Testing collisions ( 32-bit) - Expected 17322.9, actual 777895 (44.91x)
(760573) !!!!!
*********FAIL*********
Combination 0x8000000 Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 2799870 (342.00x)
(2791684) !!!!!
*********FAIL*********
Combination 0x0000001 Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 2799806 (342.00x)
(2791620) !!!!!
*********FAIL*********
Combination 0x800000000000000 Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8241 (1.01x) (55)
Testing distribution - Worst bias is the 20-bit window at bit 23 - 0.031%
Combination 0x000000000000001 Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8150 (1.00x) (-36)
Testing distribution - Worst bias is the 20-bit window at bit 22 - 0.056%
Combination 16-bytes [0-1] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8016 (0.98x)
Testing distribution - Worst bias is the 20-bit window at bit 19 - 0.033%
Combination 16-bytes [0-last] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8250 (1.01x) (64)
Testing distribution - Worst bias is the 20-bit window at bit 17 - 0.029%
Combination 32-bytes [0-1] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8066 (0.99x) (-120)
Testing distribution - Worst bias is the 19-bit window at bit 12 - 0.022%
Combination 32-bytes [0-last] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8265 (1.01x) (79)
Testing distribution - Worst bias is the 20-bit window at bit 10 - 0.044%
Combination 64-bytes [0-1] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8051 (0.98x) (-135)
Testing distribution - Worst bias is the 20-bit window at bit 30 - 0.031%
Combination 64-bytes [0-last] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8122 (0.99x) (-64)
Testing distribution - Worst bias is the 20-bit window at bit 4 - 0.032%
Combination 128-bytes [0-1] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8107 (0.99x) (-79)
Testing distribution - Worst bias is the 20-bit window at bit 9 - 0.038%
Combination 128-bytes [0-last] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8050 (0.98x) (-136)
Testing distribution - Worst bias is the 20-bit window at bit 11 - 0.026%
[[[ Keyset 'Cyclic' Tests ]]]
Keyset 'Cyclic' - 8 cycles of 4 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 125 (1.07x) (9)
Testing distribution - Worst bias is the 17-bit window at bit 2 - 0.141%
Keyset 'Cyclic' - 8 cycles of 5 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 108 (0.93x)
Testing distribution - Worst bias is the 17-bit window at bit 19 - 0.046%
Keyset 'Cyclic' - 8 cycles of 6 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 121 (1.04x) (5)
Testing distribution - Worst bias is the 17-bit window at bit 2 - 0.116%
Keyset 'Cyclic' - 8 cycles of 7 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 104 (0.89x)
Testing distribution - Worst bias is the 15-bit window at bit 26 - 0.068%
Keyset 'Cyclic' - 8 cycles of 8 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 118 (1.01x) (2)
Testing distribution - Worst bias is the 17-bit window at bit 9 - 0.140%
Keyset 'Cyclic' - 8 cycles of 12 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 98 (0.84x)
Testing distribution - Worst bias is the 17-bit window at bit 26 - 0.093%
[[[ Keyset 'TwoBytes' Tests ]]]
Keyset 'TwoBytes' - up-to-4-byte keys, 652545 total keys
Testing collisions ( 32-bit) - Expected 49.6, actual 261390 (5273.28x)
(261341) !!!!!
Keyset 'TwoBytes' - up-to-8-byte keys, 5471025 total keys
Testing collisions ( 32-bit) - Expected 3483.1, actual 3648670 (1047.54x)
(3645187) !!!!!
Keyset 'TwoBytes' - up-to-12-byte keys, 18616785 total keys
Testing collisions ( 32-bit) - Expected 40289.5, actual 12503722 (310.35x)
(12463433) !!!!!
Keyset 'TwoBytes' - up-to-16-byte keys, 44251425 total keys
Testing collisions ( 32-bit) - Expected 227182.3, actual 34632335 (152.44x)
(34405153) !!!!!
Keyset 'TwoBytes' - up-to-20-byte keys, 86536545 total keys
Testing collisions ( 32-bit) - Expected 865959.1, actual 64602745 (74.60x)
(63736786) !!!!!
Keyset 'TwoBytes' - up-to-24-byte keys, 149633745 total keys
Testing collisions ( 32-bit) - Expected 2576560.5, actual 122139184 (47.40x)
(119562624) !!!!!
*********FAIL*********
[[[ Keyset 'Text' Tests ]]]
Keyset 'Text' - keys of form "FooXXXXBar" - 14776336 keys
Testing collisions ( 32-bit) - Expected 25389.0, actual 25539 (1.01x) (150)
Testing distribution - Worst bias is the 20-bit window at bit 3 - 0.024%
Keyset 'Text' - keys of form "FooBarXXXX" - 14776336 keys
Testing collisions ( 32-bit) - Expected 25389.0, actual 25349 (1.00x) (-40)
Testing distribution - Worst bias is the 20-bit window at bit 30 - 0.033%
Keyset 'Text' - keys of form "XXXXFooBar" - 14776336 keys
Testing collisions ( 32-bit) - Expected 25389.0, actual 25368 (1.00x) (-21)
Testing distribution - Worst bias is the 20-bit window at bit 14 - 0.018%
Keyset 'Words' - 4000000 random keys of len 6-16 from alnum charset
Testing collisions ( 32-bit) - Expected 1862.1, actual 1859 (1.00x) (-3)
Testing distribution - Worst bias is the 19-bit window at bit 30 - 0.065%
Keyset 'Words' - 4000000 random keys of len 6-16 from password charset
Testing collisions ( 32-bit) - Expected 1862.1, actual 1818 (0.98x)
Testing distribution - Worst bias is the 18-bit window at bit 14 - 0.042%
Keyset 'Words' - 479826 dict words
Testing collisions ( 32-bit) - Expected 26.8, actual 34 (1.27x) (8)
Testing distribution - Worst bias is the 16-bit window at bit 11 - 0.144%
[[[ Keyset 'Zeroes' Tests ]]]
Keyset 'Zeroes' - 204800 keys
Testing collisions ( 32-bit) - Expected 4.9, actual 179199 (36700.72x)
(179195) !!!!!!
*********FAIL*********
[[[ Keyset 'Seed' Tests ]]]
Keyset 'Seed' - 5000000 keys
Testing collisions ( 32-bit) - Expected 2909.3, actual 2886 (0.99x) (-23)
Testing distribution - Worst bias is the 19-bit window at bit 0 - 0.044%
[[[ Keyset 'PerlinNoise' Tests ]]]
Testing 16777216 coordinates (L2) :
Testing collisions ( 32-bit) - Expected 32725.4, actual 32812 (1.00x) (87)
Testing AV variant, 128 count with 4 spacing, 4-12:
Testing collisions ( 32-bit) - Expected 1116.2, actual 2064632 (1849.78x)
(2063516)
[[[ DiffDist 'Differential Distribution' Tests ]]]
Testing bit 0
Testing collisions ( 32-bit) - Expected 511.9, actual 516 (1.01x) (5)
Testing distribution - Worst bias is the 18-bit window at bit 28 - 0.060%
Testing bit 1
Testing collisions ( 32-bit) - Expected 511.9, actual 543 (1.06x) (32)
Testing distribution - Worst bias is the 18-bit window at bit 19 - 0.075%
Testing bit 2
Testing collisions ( 32-bit) - Expected 511.9, actual 544 (1.06x) (33)
Testing distribution - Worst bias is the 18-bit window at bit 17 - 0.053%
Testing bit 3
Testing collisions ( 32-bit) - Expected 511.9, actual 487 (0.95x)
Testing distribution - Worst bias is the 18-bit window at bit 26 - 0.064%
Testing bit 4
Testing collisions ( 32-bit) - Expected 511.9, actual 517 (1.01x) (6)
Testing distribution - Worst bias is the 17-bit window at bit 6 - 0.057%
Testing bit 5
Testing collisions ( 32-bit) - Expected 511.9, actual 551 (1.08x) (40)
Testing distribution - Worst bias is the 18-bit window at bit 21 - 0.058%
Testing bit 6
Testing collisions ( 32-bit) - Expected 511.9, actual 531 (1.04x) (20)
Testing distribution - Worst bias is the 18-bit window at bit 30 - 0.053%
Testing bit 7
Testing collisions ( 32-bit) - Expected 511.9, actual 532 (1.04x) (21)
Testing distribution - Worst bias is the 18-bit window at bit 1 - 0.055%
Testing bit 8
Testing collisions ( 32-bit) - Expected 511.9, actual 530 (1.04x) (19)
Testing distribution - Worst bias is the 18-bit window at bit 23 - 0.080%
Testing bit 9
Testing collisions ( 32-bit) - Expected 511.9, actual 511 (1.00x)
Testing distribution - Worst bias is the 18-bit window at bit 5 - 0.065%
Testing bit 10
Testing collisions ( 32-bit) - Expected 511.9, actual 524 (1.02x) (13)
Testing distribution - Worst bias is the 18-bit window at bit 6 - 0.061%
Testing bit 11
Testing collisions ( 32-bit) - Expected 511.9, actual 498 (0.97x)
Testing distribution - Worst bias is the 18-bit window at bit 20 - 0.071%
Testing bit 12
Testing collisions ( 32-bit) - Expected 511.9, actual 504 (0.98x) (-7)
Testing distribution - Worst bias is the 18-bit window at bit 19 - 0.110%
Testing bit 13
Testing collisions ( 32-bit) - Expected 511.9, actual 513 (1.00x) (2)
Testing distribution - Worst bias is the 17-bit window at bit 7 - 0.032%
Testing bit 14
Testing collisions ( 32-bit) - Expected 511.9, actual 526 (1.03x) (15)
Testing distribution - Worst bias is the 18-bit window at bit 20 - 0.050%
Testing bit 15
Testing collisions ( 32-bit) - Expected 511.9, actual 502 (0.98x) (-9)
Testing distribution - Worst bias is the 18-bit window at bit 23 - 0.053%
Testing bit 16
Testing collisions ( 32-bit) - Expected 511.9, actual 493 (0.96x)
Testing distribution - Worst bias is the 18-bit window at bit 17 - 0.071%
Testing bit 17
Testing collisions ( 32-bit) - Expected 511.9, actual 506 (0.99x) (-5)
Testing distribution - Worst bias is the 18-bit window at bit 5 - 0.066%
Testing bit 18
Testing collisions ( 32-bit) - Expected 511.9, actual 504 (0.98x) (-7)
Testing distribution - Worst bias is the 18-bit window at bit 0 - 0.090%
Testing bit 19
Testing collisions ( 32-bit) - Expected 511.9, actual 499 (0.97x)
Testing distribution - Worst bias is the 18-bit window at bit 26 - 0.076%
Testing bit 20
Testing collisions ( 32-bit) - Expected 511.9, actual 534 (1.04x) (23)
Testing distribution - Worst bias is the 18-bit window at bit 5 - 0.109%
Testing bit 21
Testing collisions ( 32-bit) - Expected 511.9, actual 508 (0.99x) (-3)
Testing distribution - Worst bias is the 18-bit window at bit 8 - 0.065%
Testing bit 22
Testing collisions ( 32-bit) - Expected 511.9, actual 506 (0.99x) (-5)
Testing distribution - Worst bias is the 16-bit window at bit 4 - 0.040%
Testing bit 23
Testing collisions ( 32-bit) - Expected 511.9, actual 516 (1.01x) (5)
Testing distribution - Worst bias is the 18-bit window at bit 22 - 0.096%
Testing bit 24
Testing collisions ( 32-bit) - Expected 511.9, actual 496 (0.97x)
Testing distribution - Worst bias is the 18-bit window at bit 17 - 0.066%
Testing bit 25
Testing collisions ( 32-bit) - Expected 511.9, actual 514 (1.00x) (3)
Testing distribution - Worst bias is the 18-bit window at bit 17 - 0.082%
Testing bit 26
Testing collisions ( 32-bit) - Expected 511.9, actual 527 (1.03x) (16)
Testing distribution - Worst bias is the 18-bit window at bit 15 - 0.067%
Testing bit 27
Testing collisions ( 32-bit) - Expected 511.9, actual 500 (0.98x)
Testing distribution - Worst bias is the 18-bit window at bit 3 - 0.042%
Testing bit 28
Testing collisions ( 32-bit) - Expected 511.9, actual 565 (1.10x) (54)
Testing distribution - Worst bias is the 18-bit window at bit 26 - 0.069%
Testing bit 29
Testing collisions ( 32-bit) - Expected 511.9, actual 481 (0.94x)
Testing distribution - Worst bias is the 18-bit window at bit 4 - 0.061%
Testing bit 30
Testing collisions ( 32-bit) - Expected 511.9, actual 518 (1.01x) (7)
Testing distribution - Worst bias is the 18-bit window at bit 1 - 0.063%
Testing bit 31
Testing collisions ( 32-bit) - Expected 511.9, actual 511 (1.00x)
Testing distribution - Worst bias is the 18-bit window at bit 22 - 0.084%
Testing bit 32
Testing collisions ( 32-bit) - Expected 511.9, actual 519 (1.01x) (8)
Testing distribution - Worst bias is the 18-bit window at bit 30 - 0.058%
Testing bit 33
Testing collisions ( 32-bit) - Expected 511.9, actual 532 (1.04x) (21)
Testing distribution - Worst bias is the 18-bit window at bit 30 - 0.058%
Testing bit 34
Testing collisions ( 32-bit) - Expected 511.9, actual 502 (0.98x) (-9)
Testing distribution - Worst bias is the 18-bit window at bit 0 - 0.077%
Testing bit 35
Testing collisions ( 32-bit) - Expected 511.9, actual 479 (0.94x)
Testing distribution - Worst bias is the 18-bit window at bit 29 - 0.063%
Testing bit 36
Testing collisions ( 32-bit) - Expected 511.9, actual 548 (1.07x) (37)
Testing distribution - Worst bias is the 18-bit window at bit 14 - 0.059%
Testing bit 37
Testing collisions ( 32-bit) - Expected 511.9, actual 545 (1.06x) (34)
Testing distribution - Worst bias is the 18-bit window at bit 16 - 0.100%
Testing bit 38
Testing collisions ( 32-bit) - Expected 511.9, actual 532 (1.04x) (21)
Testing distribution - Worst bias is the 18-bit window at bit 3 - 0.052%
Testing bit 39
Testing collisions ( 32-bit) - Expected 511.9, actual 500 (0.98x)
Testing distribution - Worst bias is the 18-bit window at bit 1 - 0.090%
Testing bit 40
Testing collisions ( 32-bit) - Expected 511.9, actual 556 (1.09x) (45)
Testing distribution - Worst bias is the 18-bit window at bit 16 - 0.074%
Testing bit 41
Testing collisions ( 32-bit) - Expected 511.9, actual 542 (1.06x) (31)
Testing distribution - Worst bias is the 18-bit window at bit 15 - 0.032%
Testing bit 42
Testing collisions ( 32-bit) - Expected 511.9, actual 520 (1.02x) (9)
Testing distribution - Worst bias is the 18-bit window at bit 25 - 0.059%
Testing bit 43
Testing collisions ( 32-bit) - Expected 511.9, actual 446 (0.87x)
Testing distribution - Worst bias is the 18-bit window at bit 15 - 0.063%
Testing bit 44
Testing collisions ( 32-bit) - Expected 511.9, actual 515 (1.01x) (4)
Testing distribution - Worst bias is the 18-bit window at bit 31 - 0.063%
Testing bit 45
Testing collisions ( 32-bit) - Expected 511.9, actual 487 (0.95x)
Testing distribution - Worst bias is the 18-bit window at bit 4 - 0.065%
Testing bit 46
Testing collisions ( 32-bit) - Expected 511.9, actual 529 (1.03x) (18)
Testing distribution - Worst bias is the 18-bit window at bit 2 - 0.066%
Testing bit 47
Testing collisions ( 32-bit) - Expected 511.9, actual 525 (1.03x) (14)
Testing distribution - Worst bias is the 18-bit window at bit 0 - 0.084%
Testing bit 48
Testing collisions ( 32-bit) - Expected 511.9, actual 534 (1.04x) (23)
Testing distribution - Worst bias is the 18-bit window at bit 20 - 0.071%
Testing bit 49
Testing collisions ( 32-bit) - Expected 511.9, actual 534 (1.04x) (23)
Testing distribution - Worst bias is the 18-bit window at bit 27 - 0.073%
Testing bit 50
Testing collisions ( 32-bit) - Expected 511.9, actual 550 (1.07x) (39)
Testing distribution - Worst bias is the 18-bit window at bit 23 - 0.080%
Testing bit 51
Testing collisions ( 32-bit) - Expected 511.9, actual 487 (0.95x)
Testing distribution - Worst bias is the 18-bit window at bit 19 - 0.022%
Testing bit 52
Testing collisions ( 32-bit) - Expected 511.9, actual 526 (1.03x) (15)
Testing distribution - Worst bias is the 18-bit window at bit 4 - 0.072%
Testing bit 53
Testing collisions ( 32-bit) - Expected 511.9, actual 491 (0.96x)
Testing distribution - Worst bias is the 18-bit window at bit 11 - 0.063%
Testing bit 54
Testing collisions ( 32-bit) - Expected 511.9, actual 516 (1.01x) (5)
Testing distribution - Worst bias is the 18-bit window at bit 12 - 0.053%
Testing bit 55
Testing collisions ( 32-bit) - Expected 511.9, actual 496 (0.97x)
Testing distribution - Worst bias is the 18-bit window at bit 28 - 0.037%
Testing bit 56
Testing collisions ( 32-bit) - Expected 511.9, actual 488 (0.95x)
Testing distribution - Worst bias is the 18-bit window at bit 27 - 0.054%
Testing bit 57
Testing collisions ( 32-bit) - Expected 511.9, actual 477 (0.93x)
Testing distribution - Worst bias is the 18-bit window at bit 24 - 0.062%
Testing bit 58
Testing collisions ( 32-bit) - Expected 511.9, actual 517 (1.01x) (6)
Testing distribution - Worst bias is the 18-bit window at bit 17 - 0.067%
Testing bit 59
Testing collisions ( 32-bit) - Expected 511.9, actual 518 (1.01x) (7)
Testing distribution - Worst bias is the 18-bit window at bit 10 - 0.057%
Testing bit 60
Testing collisions ( 32-bit) - Expected 511.9, actual 467 (0.91x)
Testing distribution - Worst bias is the 18-bit window at bit 14 - 0.056%
Testing bit 61
Testing collisions ( 32-bit) - Expected 511.9, actual 507 (0.99x) (-4)
Testing distribution - Worst bias is the 18-bit window at bit 31 - 0.058%
Testing bit 62
Testing collisions ( 32-bit) - Expected 511.9, actual 495 (0.97x)
Testing distribution - Worst bias is the 18-bit window at bit 26 - 0.078%
Testing bit 63
Testing collisions ( 32-bit) - Expected 511.9, actual 505 (0.99x) (-6)
Testing distribution - Worst bias is the 18-bit window at bit 8 - 0.046%
Input vcode 0x00000001, Output vcode 0x00000001, Result vcode 0x00000001
Verification value is 0x00000001 - Testing took 264.327292 seconds
[[[ Avalanche Tests ]]]
Testing 24-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.576000%
Testing 32-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.652667%
Testing 40-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.716000%
Testing 48-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.664667%
Testing 56-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.634667%
Testing 64-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.760667%
Testing 72-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.696667%
Testing 80-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.678000%
Testing 96-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.784667%
Testing 112-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.610000%
Testing 128-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.603333%
Testing 160-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.709333%
Testing 512-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.768667%
Testing 1024-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.751333%
[[[ Diff 'Differential' Tests ]]]
Testing 8303632 up-to-5-bit differentials in 64-bit keys -> 32 bit hashes.
1000 reps, 8303632000 total tests, expecting 1.93 random collisions..........
0 total collisions, of which 0 single collisions were ignored
Testing 11017632 up-to-4-bit differentials in 128-bit keys -> 32 bit hashes.
1000 reps, 11017632000 total tests, expecting 2.57 random collisions..........
0 total collisions, of which 0 single collisions were ignored
Testing 2796416 up-to-3-bit differentials in 256-bit keys -> 32 bit hashes.
1000 reps, 2796416000 total tests, expecting 0.65 random collisions..........
0 total collisions, of which 0 single collisions were ignored
[[[ MomentChi2 Tests ]]]
Analyze hashes produced from a serie of linearly increasing numbers of 32-bit,
using a step of 2 ...
Target values to approximate : 1391290.000000 - 686.666667
4 threads starting... done
Popcount 1 stats : 1391274.272774 - 687.214286
Popcount 0 stats : 1391326.086340 - 687.394241
MomentChi2 for bits 1 : 0.180034
MomentChi2 for bits 0 : 0.947719
Derivative stats (transition from 2 consecutive values) :
Popcount 1 stats : 1391337.595605 - 687.344446
Popcount 0 stats : 1391285.423503 - 687.295030
MomentChi2 for deriv b1 : 1.64871
MomentChi2 for deriv b0 : 0.0152437
Great
[[[ Prng Tests ]]]
Skipping PRNG test; it is designed for hashes >= 64-bits
[[[ BIC 'Bit Independence Criteria' Tests ]]]
...........
Max bias 0.005424 - ( 1 : 13, 26)
Input vcode 0x00000001, Output vcode 0x00000001, Result vcode 0x00000001
Verification value is 0x00000001 - Testing took 720.371917 seconds
--- Testing fasthash32 "fast-hash 32bit" with length in finalizer
[[[ Sanity Tests ]]]
Verification value 0x6A202089 ....... FAIL! (Expected 0xe9481afc) [JCN - won't
give the same answer obviously]
Running sanity check 1 .......... PASS
Running AppendedZeroesTest .......... PASS
[[[ Keyset 'Sparse' Tests ]]]
Keyset 'Sparse' - 16-bit keys with up to 9 bits set - 50643 keys
Testing collisions ( 32-bit) - Expected 0.3, actual 0 (0.00x)
Testing collisions (high 19-25 bits) - Worst is 25 bits: 47/38 (1.23x)
Testing collisions (low 19-25 bits) - Worst is 24 bits: 80/76 (1.05x)
Testing distribution - Worst bias is the 13-bit window at bit 2 - 0.495%
Keyset 'Sparse' - 24-bit keys with up to 8 bits set - 1271626 keys
Testing collisions ( 32-bit) - Expected 188.2, actual 183 (0.97x)
Testing distribution - Worst bias is the 17-bit window at bit 30 - 0.081%
Keyset 'Sparse' - 32-bit keys with up to 7 bits set - 4514873 keys
Testing collisions ( 32-bit) - Expected 2372.2, actual 2427 (1.02x) (55)
Testing distribution - Worst bias is the 19-bit window at bit 28 - 0.047%
Keyset 'Sparse' - 40-bit keys with up to 6 bits set - 4598479 keys
Testing collisions ( 32-bit) - Expected 2460.8, actual 2569 (1.04x) (109)
Testing distribution - Worst bias is the 19-bit window at bit 4 - 0.057%
Keyset 'Sparse' - 48-bit keys with up to 6 bits set - 14196869 keys
Testing collisions ( 32-bit) - Expected 23437.8, actual 23175 (0.99x) (-262)
Testing distribution - Worst bias is the 20-bit window at bit 30 - 0.022%
Keyset 'Sparse' - 56-bit keys with up to 5 bits set - 4216423 keys
Testing collisions ( 32-bit) - Expected 2069.0, actual 2093 (1.01x) (25)
Testing distribution - Worst bias is the 19-bit window at bit 11 - 0.049%
Keyset 'Sparse' - 64-bit keys with up to 5 bits set - 8303633 keys
Testing collisions ( 32-bit) - Expected 8021.7, actual 8008 (1.00x) (-13)
Testing distribution - Worst bias is the 20-bit window at bit 31 - 0.033%
Keyset 'Sparse' - 72-bit keys with up to 5 bits set - 15082603 keys
Testing collisions ( 32-bit) - Expected 26451.8, actual 26440 (1.00x) (-11)
Testing distribution - Worst bias is the 20-bit window at bit 1 - 0.018%
Keyset 'Sparse' - 96-bit keys with up to 4 bits set - 3469497 keys
Testing collisions ( 32-bit) - Expected 1401.0, actual 1408 (1.01x) (8)
Testing distribution - Worst bias is the 19-bit window at bit 26 - 0.055%
Keyset 'Sparse' - 160-bit keys with up to 4 bits set - 26977161 keys
Testing collisions ( 32-bit) - Expected 84546.1, actual 84196 (1.00x) (-350)
Testing distribution - Worst bias is the 20-bit window at bit 23 - 0.015%
Keyset 'Sparse' - 256-bit keys with up to 3 bits set - 2796417 keys
Testing collisions ( 32-bit) - Expected 910.2, actual 890 (0.98x)
Testing distribution - Worst bias is the 19-bit window at bit 27 - 0.044%
Keyset 'Sparse' - 512-bit keys with up to 3 bits set - 22370049 keys
Testing collisions ( 32-bit) - Expected 58155.4, actual 57845 (0.99x) (-310)
Testing distribution - Worst bias is the 20-bit window at bit 1 - 0.007%
Keyset 'Sparse' - 1024-bit keys with up to 2 bits set - 524801 keys
Testing collisions ( 32-bit) - Expected 32.1, actual 37 (1.15x) (5)
Testing distribution - Worst bias is the 16-bit window at bit 21 - 0.125%
Keyset 'Sparse' - 2048-bit keys with up to 2 bits set - 2098177 keys
Testing collisions ( 32-bit) - Expected 512.4, actual 547 (1.07x) (35)
Testing distribution - Worst bias is the 18-bit window at bit 14 - 0.063%
[[[ Keyset 'Permutation' Tests ]]]
Combination Lowbits Tests:
Keyset 'Combination' - up to 7 blocks from a set of 8 - 2396744 keys
Testing collisions ( 32-bit) - Expected 668.6, actual 618 (0.92x)
Testing distribution - Worst bias is the 18-bit window at bit 12 - 0.050%
Combination Highbits Tests
Keyset 'Combination' - up to 7 blocks from a set of 8 - 2396744 keys
Testing collisions ( 32-bit) - Expected 668.6, actual 691 (1.03x) (23)
Testing distribution - Worst bias is the 18-bit window at bit 15 - 0.071%
Combination Hi-Lo Tests:
Keyset 'Combination' - up to 6 blocks from a set of 15 - 12204240 keys
Testing collisions ( 32-bit) - Expected 17322.9, actual 17300 (1.00x) (-22)
Testing distribution - Worst bias is the 20-bit window at bit 12 - 0.034%
Combination 0x8000000 Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8259 (1.01x) (73)
Testing distribution - Worst bias is the 20-bit window at bit 13 - 0.040%
Combination 0x0000001 Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8168 (1.00x) (-18)
Testing distribution - Worst bias is the 20-bit window at bit 15 - 0.022%
Combination 0x800000000000000 Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8173 (1.00x) (-13)
Testing distribution - Worst bias is the 20-bit window at bit 31 - 0.027%
Combination 0x000000000000001 Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8087 (0.99x) (-99)
Testing distribution - Worst bias is the 20-bit window at bit 5 - 0.015%
Combination 16-bytes [0-1] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8066 (0.99x) (-120)
Testing distribution - Worst bias is the 20-bit window at bit 7 - 0.028%
Combination 16-bytes [0-last] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8314 (1.02x) (128)
Testing distribution - Worst bias is the 20-bit window at bit 21 - 0.030%
Combination 32-bytes [0-1] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8304 (1.01x) (118)
Testing distribution - Worst bias is the 20-bit window at bit 0 - 0.016%
Combination 32-bytes [0-last] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8253 (1.01x) (67)
Testing distribution - Worst bias is the 20-bit window at bit 12 - 0.034%
Combination 64-bytes [0-1] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8108 (0.99x) (-78)
Testing distribution - Worst bias is the 20-bit window at bit 26 - 0.035%
Combination 64-bytes [0-last] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8216 (1.00x) (30)
Testing distribution - Worst bias is the 20-bit window at bit 11 - 0.041%
Combination 128-bytes [0-1] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8073 (0.99x) (-113)
Testing distribution - Worst bias is the 20-bit window at bit 17 - 0.027%
Combination 128-bytes [0-last] Tests:
Keyset 'Combination' - up to 22 blocks from a set of 2 - 8388606 keys
Testing collisions ( 32-bit) - Expected 8186.7, actual 8048 (0.98x) (-138)
Testing distribution - Worst bias is the 19-bit window at bit 5 - 0.026%
[[[ Keyset 'Cyclic' Tests ]]]
Keyset 'Cyclic' - 8 cycles of 4 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 108 (0.93x)
Testing distribution - Worst bias is the 17-bit window at bit 16 - 0.124%
Keyset 'Cyclic' - 8 cycles of 5 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 126 (1.08x) (10)
Testing distribution - Worst bias is the 17-bit window at bit 19 - 0.092%
Keyset 'Cyclic' - 8 cycles of 6 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 111 (0.95x)
Testing distribution - Worst bias is the 17-bit window at bit 10 - 0.087%
Keyset 'Cyclic' - 8 cycles of 7 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 117 (1.01x) (1)
Testing distribution - Worst bias is the 17-bit window at bit 21 - 0.113%
Keyset 'Cyclic' - 8 cycles of 8 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 134 (1.15x) (18)
Testing distribution - Worst bias is the 16-bit window at bit 13 - 0.062%
Keyset 'Cyclic' - 8 cycles of 12 bytes - 1000000 keys
Testing collisions ( 32-bit) - Expected 116.4, actual 127 (1.09x) (11)
Testing distribution - Worst bias is the 17-bit window at bit 25 - 0.091%
[[[ Keyset 'TwoBytes' Tests ]]]
Keyset 'TwoBytes' - up-to-4-byte keys, 652545 total keys
Testing collisions ( 32-bit) - Expected 49.6, actual 50 (1.01x) (1)
Testing distribution - Worst bias is the 16-bit window at bit 21 - 0.089%
Keyset 'TwoBytes' - up-to-8-byte keys, 5471025 total keys
Testing collisions ( 32-bit) - Expected 3483.1, actual 3457 (0.99x) (-26)
Testing distribution - Worst bias is the 20-bit window at bit 9 - 0.094%
Keyset 'TwoBytes' - up-to-12-byte keys, 18616785 total keys
Testing collisions ( 32-bit) - Expected 40289.5, actual 40410 (1.00x) (121)
Testing distribution - Worst bias is the 20-bit window at bit 29 - 0.017%
Keyset 'TwoBytes' - up-to-16-byte keys, 44251425 total keys
Testing collisions ( 32-bit) - Expected 227182.3, actual 227335 (1.00x) (153)
Testing distribution - Worst bias is the 20-bit window at bit 23 - 0.008%
Keyset 'TwoBytes' - up-to-20-byte keys, 86536545 total keys
Testing collisions ( 32-bit) - Expected 865959.1, actual 865658 (1.00x) (-301)
Testing distribution - Worst bias is the 20-bit window at bit 23 - 0.004%
Keyset 'TwoBytes' - up-to-24-byte keys, 149633745 total keys
Testing collisions ( 32-bit) - Expected 2576560.5, actual 2575915 (1.00x) (-645)
Testing distribution - Worst bias is the 20-bit window at bit 23 - 0.002%
[[[ Keyset 'Text' Tests ]]]
Keyset 'Text' - keys of form "FooXXXXBar" - 14776336 keys
Testing collisions ( 32-bit) - Expected 25389.0, actual 25549 (1.01x) (160)
Testing distribution - Worst bias is the 20-bit window at bit 15 - 0.024%
Keyset 'Text' - keys of form "FooBarXXXX" - 14776336 keys
Testing collisions ( 32-bit) - Expected 25389.0, actual 25290 (1.00x) (-99)
Testing distribution - Worst bias is the 20-bit window at bit 23 - 0.014%
Keyset 'Text' - keys of form "XXXXFooBar" - 14776336 keys
Testing collisions ( 32-bit) - Expected 25389.0, actual 25389 (1.00x)
Testing distribution - Worst bias is the 20-bit window at bit 13 - 0.025%
Keyset 'Words' - 4000000 random keys of len 6-16 from alnum charset
Testing collisions ( 32-bit) - Expected 1862.1, actual 1905 (1.02x) (43)
Testing distribution - Worst bias is the 19-bit window at bit 26 - 0.060%
Keyset 'Words' - 4000000 random keys of len 6-16 from password charset
Testing collisions ( 32-bit) - Expected 1862.1, actual 1899 (1.02x) (37)
Testing distribution - Worst bias is the 19-bit window at bit 23 - 0.029%
Keyset 'Words' - 479826 dict words
Testing collisions ( 32-bit) - Expected 26.8, actual 19 (0.71x)
Testing distribution - Worst bias is the 15-bit window at bit 3 - 0.141%
[[[ Keyset 'Zeroes' Tests ]]]
Keyset 'Zeroes' - 204800 keys
Testing collisions ( 32-bit) - Expected 4.9, actual 5 (1.02x) (1)
Testing collisions (high 21-29 bits) - Worst is 26 bits: 329/312 (1.05x)
Testing collisions (low 21-29 bits) - Worst is 26 bits: 310/312 (0.99x)
Testing distribution - Worst bias is the 15-bit window at bit 26 - 0.177%
[[[ Keyset 'Seed' Tests ]]]
Keyset 'Seed' - 5000000 keys
Testing collisions ( 32-bit) - Expected 2909.3, actual 3028 (1.04x) (119)
Testing distribution - Worst bias is the 19-bit window at bit 17 - 0.050%
[[[ Keyset 'PerlinNoise' Tests ]]]
Testing 16777216 coordinates (L2) :
Testing collisions ( 32-bit) - Expected 32725.4, actual 32761 (1.00x) (36)
Testing AV variant, 128 count with 4 spacing, 4-12:
Testing collisions ( 32-bit) - Expected 1116.2, actual 1079 (0.97x)
[[[ DiffDist 'Differential Distribution' Tests ]]]
Testing bit 0
Testing collisions ( 32-bit) - Expected 511.9, actual 517 (1.01x) (6)
Testing distribution - Worst bias is the 18-bit window at bit 7 - 0.073%
Testing bit 1
Testing collisions ( 32-bit) - Expected 511.9, actual 497 (0.97x)
Testing distribution - Worst bias is the 18-bit window at bit 16 - 0.064%
Testing bit 2
Testing collisions ( 32-bit) - Expected 511.9, actual 482 (0.94x)
Testing distribution - Worst bias is the 18-bit window at bit 17 - 0.069%
Testing bit 3
Testing collisions ( 32-bit) - Expected 511.9, actual 484 (0.95x)
Testing distribution - Worst bias is the 18-bit window at bit 11 - 0.055%
Testing bit 4
Testing collisions ( 32-bit) - Expected 511.9, actual 497 (0.97x)
Testing distribution - Worst bias is the 17-bit window at bit 2 - 0.052%
Testing bit 5
Testing collisions ( 32-bit) - Expected 511.9, actual 516 (1.01x) (5)
Testing distribution - Worst bias is the 17-bit window at bit 4 - 0.045%
Testing bit 6
Testing collisions ( 32-bit) - Expected 511.9, actual 496 (0.97x)
Testing distribution - Worst bias is the 18-bit window at bit 13 - 0.096%
Testing bit 7
Testing collisions ( 32-bit) - Expected 511.9, actual 527 (1.03x) (16)
Testing distribution - Worst bias is the 18-bit window at bit 14 - 0.088%
Testing bit 8
Testing collisions ( 32-bit) - Expected 511.9, actual 514 (1.00x) (3)
Testing distribution - Worst bias is the 18-bit window at bit 12 - 0.046%
Testing bit 9
Testing collisions ( 32-bit) - Expected 511.9, actual 482 (0.94x)
Testing distribution - Worst bias is the 18-bit window at bit 31 - 0.063%
Testing bit 10
Testing collisions ( 32-bit) - Expected 511.9, actual 495 (0.97x)
Testing distribution - Worst bias is the 18-bit window at bit 25 - 0.043%
Testing bit 11
Testing collisions ( 32-bit) - Expected 511.9, actual 524 (1.02x) (13)
Testing distribution - Worst bias is the 18-bit window at bit 21 - 0.041%
Testing bit 12
Testing collisions ( 32-bit) - Expected 511.9, actual 505 (0.99x) (-6)
Testing distribution - Worst bias is the 17-bit window at bit 8 - 0.067%
Testing bit 13
Testing collisions ( 32-bit) - Expected 511.9, actual 554 (1.08x) (43)
Testing distribution - Worst bias is the 18-bit window at bit 12 - 0.037%
Testing bit 14
Testing collisions ( 32-bit) - Expected 511.9, actual 502 (0.98x) (-9)
Testing distribution - Worst bias is the 18-bit window at bit 19 - 0.104%
Testing bit 15
Testing collisions ( 32-bit) - Expected 511.9, actual 505 (0.99x) (-6)
Testing distribution - Worst bias is the 18-bit window at bit 24 - 0.065%
Testing bit 16
Testing collisions ( 32-bit) - Expected 511.9, actual 526 (1.03x) (15)
Testing distribution - Worst bias is the 18-bit window at bit 4 - 0.088%
Testing bit 17
Testing collisions ( 32-bit) - Expected 511.9, actual 482 (0.94x)
Testing distribution - Worst bias is the 18-bit window at bit 19 - 0.082%
Testing bit 18
Testing collisions ( 32-bit) - Expected 511.9, actual 556 (1.09x) (45)
Testing distribution - Worst bias is the 17-bit window at bit 1 - 0.067%
Testing bit 19
Testing collisions ( 32-bit) - Expected 511.9, actual 507 (0.99x) (-4)
Testing distribution - Worst bias is the 18-bit window at bit 26 - 0.073%
Testing bit 20
Testing collisions ( 32-bit) - Expected 511.9, actual 506 (0.99x) (-5)
Testing distribution - Worst bias is the 18-bit window at bit 11 - 0.068%
Testing bit 21
Testing collisions ( 32-bit) - Expected 511.9, actual 513 (1.00x) (2)
Testing distribution - Worst bias is the 18-bit window at bit 13 - 0.049%
Testing bit 22
Testing collisions ( 32-bit) - Expected 511.9, actual 518 (1.01x) (7)
Testing distribution - Worst bias is the 18-bit window at bit 26 - 0.057%
Testing bit 23
Testing collisions ( 32-bit) - Expected 511.9, actual 520 (1.02x) (9)
Testing distribution - Worst bias is the 18-bit window at bit 29 - 0.069%
Testing bit 24
Testing collisions ( 32-bit) - Expected 511.9, actual 488 (0.95x)
Testing distribution - Worst bias is the 18-bit window at bit 18 - 0.086%
Testing bit 25
Testing collisions ( 32-bit) - Expected 511.9, actual 575 (1.12x) (64)
Testing distribution - Worst bias is the 18-bit window at bit 28 - 0.087%
Testing bit 26
Testing collisions ( 32-bit) - Expected 511.9, actual 525 (1.03x) (14)
Testing distribution - Worst bias is the 18-bit window at bit 24 - 0.070%
Testing bit 27
Testing collisions ( 32-bit) - Expected 511.9, actual 481 (0.94x)
Testing distribution - Worst bias is the 18-bit window at bit 20 - 0.068%
Testing bit 28
Testing collisions ( 32-bit) - Expected 511.9, actual 496 (0.97x)
Testing distribution - Worst bias is the 18-bit window at bit 17 - 0.084%
Testing bit 29
Testing collisions ( 32-bit) - Expected 511.9, actual 509 (0.99x) (-2)
Testing distribution - Worst bias is the 18-bit window at bit 30 - 0.073%
Testing bit 30
Testing collisions ( 32-bit) - Expected 511.9, actual 509 (0.99x) (-2)
Testing distribution - Worst bias is the 18-bit window at bit 28 - 0.051%
Testing bit 31
Testing collisions ( 32-bit) - Expected 511.9, actual 516 (1.01x) (5)
Testing distribution - Worst bias is the 17-bit window at bit 25 - 0.064%
Testing bit 32
Testing collisions ( 32-bit) - Expected 511.9, actual 499 (0.97x)
Testing distribution - Worst bias is the 17-bit window at bit 12 - 0.055%
Testing bit 33
Testing collisions ( 32-bit) - Expected 511.9, actual 500 (0.98x)
Testing distribution - Worst bias is the 18-bit window at bit 12 - 0.118%
Testing bit 34
Testing collisions ( 32-bit) - Expected 511.9, actual 506 (0.99x) (-5)
Testing distribution - Worst bias is the 18-bit window at bit 25 - 0.050%
Testing bit 35
Testing collisions ( 32-bit) - Expected 511.9, actual 489 (0.96x)
Testing distribution - Worst bias is the 18-bit window at bit 1 - 0.084%
Testing bit 36
Testing collisions ( 32-bit) - Expected 511.9, actual 532 (1.04x) (21)
Testing distribution - Worst bias is the 18-bit window at bit 11 - 0.072%
Testing bit 37
Testing collisions ( 32-bit) - Expected 511.9, actual 532 (1.04x) (21)
Testing distribution - Worst bias is the 18-bit window at bit 4 - 0.064%
Testing bit 38
Testing collisions ( 32-bit) - Expected 511.9, actual 506 (0.99x) (-5)
Testing distribution - Worst bias is the 18-bit window at bit 2 - 0.071%
Testing bit 39
Testing collisions ( 32-bit) - Expected 511.9, actual 530 (1.04x) (19)
Testing distribution - Worst bias is the 18-bit window at bit 23 - 0.053%
Testing bit 40
Testing collisions ( 32-bit) - Expected 511.9, actual 511 (1.00x)
Testing distribution - Worst bias is the 18-bit window at bit 13 - 0.060%
Testing bit 41
Testing collisions ( 32-bit) - Expected 511.9, actual 539 (1.05x) (28)
Testing distribution - Worst bias is the 18-bit window at bit 29 - 0.083%
Testing bit 42
Testing collisions ( 32-bit) - Expected 511.9, actual 510 (1.00x) (-1)
Testing distribution - Worst bias is the 18-bit window at bit 16 - 0.063%
Testing bit 43
Testing collisions ( 32-bit) - Expected 511.9, actual 519 (1.01x) (8)
Testing distribution - Worst bias is the 18-bit window at bit 13 - 0.079%
Testing bit 44
Testing collisions ( 32-bit) - Expected 511.9, actual 523 (1.02x) (12)
Testing distribution - Worst bias is the 18-bit window at bit 16 - 0.084%
Testing bit 45
Testing collisions ( 32-bit) - Expected 511.9, actual 542 (1.06x) (31)
Testing distribution - Worst bias is the 18-bit window at bit 31 - 0.076%
Testing bit 46
Testing collisions ( 32-bit) - Expected 511.9, actual 543 (1.06x) (32)
Testing distribution - Worst bias is the 18-bit window at bit 20 - 0.088%
Testing bit 47
Testing collisions ( 32-bit) - Expected 511.9, actual 547 (1.07x) (36)
Testing distribution - Worst bias is the 18-bit window at bit 16 - 0.105%
Testing bit 48
Testing collisions ( 32-bit) - Expected 511.9, actual 512 (1.00x) (1)
Testing distribution - Worst bias is the 18-bit window at bit 8 - 0.068%
Testing bit 49
Testing collisions ( 32-bit) - Expected 511.9, actual 505 (0.99x) (-6)
Testing distribution - Worst bias is the 18-bit window at bit 3 - 0.076%
Testing bit 50
Testing collisions ( 32-bit) - Expected 511.9, actual 496 (0.97x)
Testing distribution - Worst bias is the 18-bit window at bit 0 - 0.071%
Testing bit 51
Testing collisions ( 32-bit) - Expected 511.9, actual 487 (0.95x)
Testing distribution - Worst bias is the 18-bit window at bit 25 - 0.083%
Testing bit 52
Testing collisions ( 32-bit) - Expected 511.9, actual 514 (1.00x) (3)
Testing distribution - Worst bias is the 18-bit window at bit 16 - 0.055%
Testing bit 53
Testing collisions ( 32-bit) - Expected 511.9, actual 492 (0.96x)
Testing distribution - Worst bias is the 18-bit window at bit 18 - 0.049%
Testing bit 54
Testing collisions ( 32-bit) - Expected 511.9, actual 494 (0.97x)
Testing distribution - Worst bias is the 18-bit window at bit 4 - 0.076%
Testing bit 55
Testing collisions ( 32-bit) - Expected 511.9, actual 503 (0.98x) (-8)
Testing distribution - Worst bias is the 17-bit window at bit 30 - 0.044%
Testing bit 56
Testing collisions ( 32-bit) - Expected 511.9, actual 491 (0.96x)
Testing distribution - Worst bias is the 18-bit window at bit 13 - 0.051%
Testing bit 57
Testing collisions ( 32-bit) - Expected 511.9, actual 502 (0.98x) (-9)
Testing distribution - Worst bias is the 18-bit window at bit 1 - 0.098%
Testing bit 58
Testing collisions ( 32-bit) - Expected 511.9, actual 524 (1.02x) (13)
Testing distribution - Worst bias is the 18-bit window at bit 18 - 0.064%
Testing bit 59
Testing collisions ( 32-bit) - Expected 511.9, actual 519 (1.01x) (8)
Testing distribution - Worst bias is the 18-bit window at bit 25 - 0.068%
Testing bit 60
Testing collisions ( 32-bit) - Expected 511.9, actual 541 (1.06x) (30)
Testing distribution - Worst bias is the 18-bit window at bit 13 - 0.034%
Testing bit 61
Testing collisions ( 32-bit) - Expected 511.9, actual 472 (0.92x)
Testing distribution - Worst bias is the 18-bit window at bit 10 - 0.065%
Testing bit 62
Testing collisions ( 32-bit) - Expected 511.9, actual 507 (0.99x) (-4)
Testing distribution - Worst bias is the 18-bit window at bit 1 - 0.069%
Testing bit 63
Testing collisions ( 32-bit) - Expected 511.9, actual 482 (0.94x)
Testing distribution - Worst bias is the 18-bit window at bit 22 - 0.077%
Input vcode 0x00000001, Output vcode 0x00000001, Result vcode 0x00000001
Verification value is 0x00000001 - Testing took 350.971248 seconds
[[[ Avalanche Tests ]]]
Testing 24-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.576000%
Testing 32-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.652667%
Testing 40-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.716000%
Testing 48-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.664667%
Testing 56-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.634667%
Testing 64-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.760667%
Testing 72-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.696667%
Testing 80-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.678000%
Testing 96-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.784667%
Testing 112-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.610000%
Testing 128-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.603333%
Testing 160-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.709333%
Testing 512-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.768667%
Testing 1024-bit keys -> 32-bit hashes, 300000 reps.......... worst bias is
0.751333%
[[[ Diff 'Differential' Tests ]]]
Testing 8303632 up-to-5-bit differentials in 64-bit keys -> 32 bit hashes.
1000 reps, 8303632000 total tests, expecting 1.93 random collisions..........
0 total collisions, of which 0 single collisions were ignored
Testing 11017632 up-to-4-bit differentials in 128-bit keys -> 32 bit hashes.
1000 reps, 11017632000 total tests, expecting 2.57 random collisions..........
0 total collisions, of which 0 single collisions were ignored
Testing 2796416 up-to-3-bit differentials in 256-bit keys -> 32 bit hashes.
1000 reps, 2796416000 total tests, expecting 0.65 random collisions..........
0 total collisions, of which 0 single collisions were ignored
[[[ MomentChi2 Tests ]]]
Analyze hashes produced from a serie of linearly increasing numbers of 32-bit,
using a step of 2 ...
Target values to approximate : 1391290.000000 - 686.666667
4 threads starting... done
Popcount 1 stats : 1391274.272774 - 687.214286
Popcount 0 stats : 1391326.086340 - 687.394241
MomentChi2 for bits 1 : 0.180034
MomentChi2 for bits 0 : 0.947719
Derivative stats (transition from 2 consecutive values) :
Popcount 1 stats : 1391337.595605 - 687.344446
Popcount 0 stats : 1391285.423503 - 687.295030
MomentChi2 for deriv b1 : 1.64871
MomentChi2 for deriv b0 : 0.0152437
Great
[[[ Prng Tests ]]]
Skipping PRNG test; it is designed for hashes >= 64-bits
[[[ BIC 'Bit Independence Criteria' Tests ]]]
...........
Max bias 0.005424 - ( 1 : 13, 26)
Input vcode 0x00000001, Output vcode 0x00000001, Result vcode 0x00000001
Verification value is 0x00000001 - Testing took 718.518900 seconds
From eacb3fccb25c10696334def8a8346257958ec3dd Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Sun, 10 Dec 2023 15:14:24 +0700
Subject: [PATCH v9 4/6] Assert that incremental fasthash variants give the
same answer as the original
Test that incremental hashing gives the right answer for strings.
Use the initial length only for the init step. Test that
we can ignore the length afterwards, and only use the
presence of the NUL terminator to stop iterating. Assert
that this results in the same hash.
Based on "Use new hash APIs for search path cache" by Jeff Davis,
rebased over v7.
---
src/backend/catalog/namespace.c | 48 ++++++++++++++++++++++++++++++---
1 file changed, 44 insertions(+), 4 deletions(-)
diff --git a/src/backend/catalog/namespace.c b/src/backend/catalog/namespace.c
index 5027efc91d..6bb28aecfc 100644
--- a/src/backend/catalog/namespace.c
+++ b/src/backend/catalog/namespace.c
@@ -41,7 +41,7 @@
#include "catalog/pg_ts_template.h"
#include "catalog/pg_type.h"
#include "commands/dbcommands.h"
-#include "common/hashfn.h"
+#include "common/hashfn_unstable.h"
#include "funcapi.h"
#include "mb/pg_wchar.h"
#include "miscadmin.h"
@@ -247,11 +247,51 @@ static bool MatchNamedCall(HeapTuple proctup, int nargs, List *argnames,
static inline uint32
spcachekey_hash(SearchPathCacheKey key)
{
- const unsigned char *bytes = (const unsigned char *) key.searchPath;
+ const char *buf = key.searchPath;
+ fasthash_state hs;
+
+ // XXX not for commit
+#ifdef USE_ASSERT_CHECKING
int blen = strlen(key.searchPath);
- return hash_combine(hash_bytes(bytes, blen),
- hash_uint32(key.roleid));
+ uint64 h_orig = fasthash64_orig(buf, blen, key.roleid);
+
+ // check full function that calls incremental interface
+ Assert(fasthash64((const unsigned char *) buf, blen, key.roleid) == h_orig);
+
+ // Test that chunked interface can give the same answer,
+ // if we have length up front. We would typically use it
+ // for cases where we don't know, but let's try to make
+ // it as similar as conveniently possible.
+ fasthash_init(&hs, blen, key.roleid);
+ while (*buf)
+ {
+ int chunk_len = 0;
+
+ while(chunk_len < FH_SIZEOF_ACCUM && buf[chunk_len] != '\0')
+ chunk_len++;
+
+ fasthash_accum(&hs, (const unsigned char *) buf, chunk_len);
+ buf += chunk_len;
+ }
+ Assert(fasthash_final64(&hs) == h_orig);
+ buf = key.searchPath; /* reset */
+#endif
+
+ // WIP: maybe roleid should be mixed in normally
+ // WIP: For now fake the length to preserve the internal seed
+ fasthash_init(&hs, 1, key.roleid);
+ while (*buf)
+ {
+ int chunk_len = 0;
+
+ while(chunk_len < FH_SIZEOF_ACCUM && buf[chunk_len] != '\0')
+ chunk_len++;
+
+ fasthash_accum(&hs, (const unsigned char *) buf, chunk_len);
+ buf += chunk_len;
+ }
+ return fasthash_final32(&hs);
}
static inline bool
--
2.43.0
From 3d77e7effda9360315ab4af330839eb82ed97925 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Thu, 14 Dec 2023 19:41:17 +0700
Subject: [PATCH v9 6/6] Add optional tweak to finalizer
For hashing strings, we need to incorporate the length of the
input into the final hash when we call the finalizer. This is
necessary to pass SMHasher.
To reduce the number of places that need to know about this,
it seemed best to make the finalizer a void function, and to
make the 32-bit reducer able to accept any uint64 input.
---
src/backend/catalog/namespace.c | 11 +++++++++--
src/include/common/hashfn_unstable.h | 21 ++++++++++-----------
2 files changed, 19 insertions(+), 13 deletions(-)
diff --git a/src/backend/catalog/namespace.c b/src/backend/catalog/namespace.c
index 6bb28aecfc..3a3cb8ef70 100644
--- a/src/backend/catalog/namespace.c
+++ b/src/backend/catalog/namespace.c
@@ -247,6 +247,7 @@ static bool MatchNamedCall(HeapTuple proctup, int nargs, List *argnames,
static inline uint32
spcachekey_hash(SearchPathCacheKey key)
{
+ const char * const start = key.searchPath;
const char *buf = key.searchPath;
fasthash_state hs;
@@ -274,7 +275,10 @@ spcachekey_hash(SearchPathCacheKey key)
fasthash_accum(&hs, (const unsigned char *) buf, chunk_len);
buf += chunk_len;
}
- Assert(fasthash_final64(&hs) == h_orig);
+
+ // We passed the length to fasthash_init, so no tweak for assert testing
+ fasthash_final64(&hs, 0);
+ Assert(hs.hash == h_orig);
buf = key.searchPath; /* reset */
#endif
@@ -291,7 +295,10 @@ spcachekey_hash(SearchPathCacheKey key)
fasthash_accum(&hs, (const unsigned char *) buf, chunk_len);
buf += chunk_len;
}
- return fasthash_final32(&hs);
+
+ /* pass the length to tweak the final mix */
+ fasthash_final64(&hs, buf - start);
+ return fasthash_reduce32(hs.hash);
}
static inline bool
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index e8ca39fed2..578a4d0a83 100644
--- a/src/include/common/hashfn_unstable.h
+++ b/src/include/common/hashfn_unstable.h
@@ -53,9 +53,9 @@ typedef struct fasthash_state
} fasthash_state;
static inline uint64
-fasthash_mix(uint64 h)
+fasthash_mix(uint64 h, uint64 tweak)
{
- h ^= h >> 23;
+ h ^= (h >> 23) + tweak;
h *= 0x2127599bf4325c37;
h ^= h >> 47;
return h;
@@ -64,7 +64,7 @@ fasthash_mix(uint64 h)
static inline void
fasthash_combine(fasthash_state* hs)
{
- hs->hash ^= fasthash_mix(hs->accum);
+ hs->hash ^= fasthash_mix(hs->accum, 0);
hs->hash *= 0x880355f21e6d1965;
/* reset hash state for next input */
@@ -114,19 +114,18 @@ fasthash_accum(fasthash_state *hs, const unsigned char *k, int len)
}
-static inline uint64
-fasthash_final64(fasthash_state *hs)
+static inline void
+fasthash_final64(fasthash_state *hs, uint64 tweak)
{
- return fasthash_mix(hs->hash);
+ hs->hash = fasthash_mix(hs->hash, tweak);
}
static inline uint32
-fasthash_final32(fasthash_state *hs)
+fasthash_reduce32(uint64 h)
{
// the following trick converts the 64-bit hashcode to Fermat
// residue, which shall retain information from both the higher
// and lower parts of hashcode.
- uint64 h = fasthash_final64(hs);
return h - (h >> 32);
}
@@ -145,14 +144,14 @@ fasthash64(const unsigned char * k, int len, uint64 seed)
}
fasthash_accum(&hs, k, len);
- return fasthash_final64(&hs);
+ fasthash_final64(&hs, 0);
+ return hs.hash;
}
static inline uint64
fasthash32(const unsigned char * k, int len, uint64 seed)
{
- uint64 h = fasthash64(k, len, seed);
- return h - (h >> 32);
+ return fasthash_reduce32(fasthash64(k, len, seed));
}
--
2.43.0
From 4e1c6836894c5bed8315ac52c6f0c1ff5439076a Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Sun, 10 Dec 2023 12:11:37 +0700
Subject: [PATCH v9 2/6] Rewrite fasthash functions using a homegrown
incremental interface
The incremental interface will be useful for cases we don't know
the length up front, such as NUL-terminated strings. First, we
need to validate that this interface can give the same answer
as the original functions when we do know the length. A future
commit will add a temporary assert for testing in CI.
---
src/include/common/hashfn_unstable.h | 161 +++++++++++++++++++++++++--
1 file changed, 153 insertions(+), 8 deletions(-)
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index a5bf965fa2..fbae7a5522 100644
--- a/src/include/common/hashfn_unstable.h
+++ b/src/include/common/hashfn_unstable.h
@@ -1,3 +1,25 @@
+/*
+Building blocks for creating fast inlineable hash functions. The
+unstable designation is in contrast to hashfn.h, which cannot break
+compatibility because hashes can be writen to disk and so must have
+the same hashes between versions.
+
+ *
+ * Portions Copyright (c) 2018-2023, PostgreSQL Global Development Group
+ *
+ * src/include/common/hashfn_unstable.c
+ */
+
+#ifndef HASHFN_UNSTABLE_H
+#define HASHFN_UNSTABLE_H
+
+/*
+ * fasthash is a modification of code taken from
+ * https://code.google.com/archive/p/fast-hash/source/default/source
+ * under the terms of the MIT licencse. The original copyright
+ * notice follows:
+ */
+
/* The MIT License
Copyright (C) 2012 Zilong Tan (eric.zltan@gmail.com)
@@ -23,16 +45,130 @@
SOFTWARE.
*/
-#include "fasthash.h"
+typedef struct fasthash_state
+{
+ uint64 accum;
+#define FH_SIZEOF_ACCUM sizeof(uint64)
+ uint64 hash;
+} fasthash_state;
+
+static inline uint64
+fasthash_mix(uint64 h)
+{
+ h ^= h >> 23;
+ h *= 0x2127599bf4325c37ULL;
+ h ^= h >> 47;
+ return h;
+}
+
+static inline void
+fasthash_combine(fasthash_state* hs)
+{
+ hs->hash ^= fasthash_mix(hs->accum);
+ hs->hash *= 0x880355f21e6d1965ULL;
+
+ /* reset hash state for next input */
+ hs->accum = 0;
+}
+
+static inline void
+fasthash_init(fasthash_state *hs, int len, uint64 seed)
+{
+ memset(hs, 0, sizeof(fasthash_state));
+
+ // since we don't know the length for a nul-terminated string
+ // handle some other way -- maybe we can accum the length in
+ // the state and fold it in during the finalizer (cf. xxHash3)
+ hs->hash = seed ^ (len * 0x880355f21e6d1965ULL);
+}
+
+static inline void
+fasthash_accum(fasthash_state *hs, const unsigned char *k, int len)
+{
+ Assert(hs->accum == 0);
+ Assert(len <= FH_SIZEOF_ACCUM);
+
+ switch (len)
+ {
+ case 8: memcpy(&hs->accum, k, 8);
+ break;
+ case 7: hs->accum |= (uint64) k[6] << 48;
+ /* FALLTHROUGH */
+ case 6: hs->accum |= (uint64) k[5] << 40;
+ /* FALLTHROUGH */
+ case 5: hs->accum |= (uint64) k[4] << 32;
+ /* FALLTHROUGH */
+ case 4: hs->accum |= (uint64) k[3] << 24;
+ /* FALLTHROUGH */
+ case 3: hs->accum |= (uint64) k[2] << 16;
+ /* FALLTHROUGH */
+ case 2: hs->accum |= (uint64) k[1] << 8;
+ /* FALLTHROUGH */
+ case 1: hs->accum |= (uint64) k[0];
+ break;
+ case 0:
+ return;
+ }
+
+ fasthash_combine(hs);
+}
+
+
+static inline uint64
+fasthash_final64(fasthash_state *hs)
+{
+ return fasthash_mix(hs->hash);
+}
+
+static inline uint32
+fasthash_final32(fasthash_state *hs)
+{
+ // the following trick converts the 64-bit hashcode to Fermat
+ // residue, which shall retain information from both the higher
+ // and lower parts of hashcode.
+ uint64 h = fasthash_final64(hs);
+ return h - (h >> 32);
+}
+
+static inline uint64
+fasthash64(const unsigned char * k, int len, uint64 seed)
+{
+ fasthash_state hs;
+
+ fasthash_init(&hs, len, seed);
+
+ while (len >= FH_SIZEOF_ACCUM)
+ {
+ fasthash_accum(&hs, k, FH_SIZEOF_ACCUM);
+ k += FH_SIZEOF_ACCUM;
+ len -= FH_SIZEOF_ACCUM;
+ }
+
+ fasthash_accum(&hs, k, len);
+ return fasthash_final64(&hs);
+}
+
+static inline uint64
+fasthash32(const unsigned char * k, int len, uint64 seed)
+{
+ uint64 h = fasthash64(k, len, seed);
+ return h - (h >> 32);
+}
+
+
+// XXX NOT FOR COMMIT
// Compression function for Merkle-Damgard construction.
// This function is generated using the framework provided.
-#define mix(h) ({ \
- (h) ^= (h) >> 23; \
- (h) *= 0x2127599bf4325c37ULL; \
- (h) ^= (h) >> 47; })
+static inline uint64_t mix(uint64_t h) {
+ h ^= h >> 23;
+ h *= 0x2127599bf4325c37ULL;
+ h ^= h >> 47;
+ return h;
+}
-uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
+static inline
+uint64_t fasthash64_orig(const void *buf, size_t len, uint64_t seed)
{
const uint64_t m = 0x880355f21e6d1965ULL;
const uint64_t *pos = (const uint64_t *)buf;
@@ -52,11 +188,17 @@ uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
switch (len & 7) {
case 7: v ^= (uint64_t)pos2[6] << 48;
+ /* FALLTHROUGH */
case 6: v ^= (uint64_t)pos2[5] << 40;
+ /* FALLTHROUGH */
case 5: v ^= (uint64_t)pos2[4] << 32;
+ /* FALLTHROUGH */
case 4: v ^= (uint64_t)pos2[3] << 24;
+ /* FALLTHROUGH */
case 3: v ^= (uint64_t)pos2[2] << 16;
+ /* FALLTHROUGH */
case 2: v ^= (uint64_t)pos2[1] << 8;
+ /* FALLTHROUGH */
case 1: v ^= (uint64_t)pos2[0];
h ^= mix(v);
h *= m;
@@ -65,11 +207,14 @@ uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
return mix(h);
}
-uint32_t fasthash32(const void *buf, size_t len, uint32_t seed)
+static inline
+uint32_t fasthash32_orig(const void *buf, size_t len, uint32_t seed)
{
// the following trick converts the 64-bit hashcode to Fermat
// residue, which shall retain information from both the higher
// and lower parts of hashcode.
- uint64_t h = fasthash64(buf, len, seed);
+ uint64_t h = fasthash64_orig(buf, len, seed);
return h - (h >> 32);
}
+
+#endif /* HASHFN_UNSTABLE_H */
--
2.43.0
From 4f875eb84567ccaa31cfc4e01ccd61acb43f9a58 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Sun, 10 Dec 2023 21:27:13 +0700
Subject: [PATCH v9 3/6] Fix alignment issue in the original fastash
Found by UBSan in CI
---
src/include/common/hashfn_unstable.h | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index fbae7a5522..a167681c86 100644
--- a/src/include/common/hashfn_unstable.h
+++ b/src/include/common/hashfn_unstable.h
@@ -178,9 +178,10 @@ uint64_t fasthash64_orig(const void *buf, size_t len, uint64_t seed)
uint64_t v;
while (pos != end) {
- v = *pos++;
+ memcpy(&v, pos, 8);
h ^= mix(v);
h *= m;
+ pos++;
}
pos2 = (const unsigned char*)pos;
--
2.43.0
From 63b25e788c81bc47342f28e1e3e489fae8c61d26 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Thu, 14 Dec 2023 19:03:12 +0700
Subject: [PATCH v9 5/6] Remove ULL
---
src/include/common/hashfn_unstable.h | 10 +++++-----
1 file changed, 5 insertions(+), 5 deletions(-)
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index a167681c86..e8ca39fed2 100644
--- a/src/include/common/hashfn_unstable.h
+++ b/src/include/common/hashfn_unstable.h
@@ -56,7 +56,7 @@ static inline uint64
fasthash_mix(uint64 h)
{
h ^= h >> 23;
- h *= 0x2127599bf4325c37ULL;
+ h *= 0x2127599bf4325c37;
h ^= h >> 47;
return h;
}
@@ -65,7 +65,7 @@ static inline void
fasthash_combine(fasthash_state* hs)
{
hs->hash ^= fasthash_mix(hs->accum);
- hs->hash *= 0x880355f21e6d1965ULL;
+ hs->hash *= 0x880355f21e6d1965;
/* reset hash state for next input */
hs->accum = 0;
@@ -79,7 +79,7 @@ fasthash_init(fasthash_state *hs, int len, uint64 seed)
// since we don't know the length for a nul-terminated string
// handle some other way -- maybe we can accum the length in
// the state and fold it in during the finalizer (cf. xxHash3)
- hs->hash = seed ^ (len * 0x880355f21e6d1965ULL);
+ hs->hash = seed ^ (len * 0x880355f21e6d1965);
}
static inline void
@@ -162,7 +162,7 @@ fasthash32(const unsigned char * k, int len, uint64 seed)
// This function is generated using the framework provided.
static inline uint64_t mix(uint64_t h) {
h ^= h >> 23;
- h *= 0x2127599bf4325c37ULL;
+ h *= 0x2127599bf4325c37;
h ^= h >> 47;
return h;
}
@@ -170,7 +170,7 @@ static inline uint64_t mix(uint64_t h) {
static inline
uint64_t fasthash64_orig(const void *buf, size_t len, uint64_t seed)
{
- const uint64_t m = 0x880355f21e6d1965ULL;
+ const uint64_t m = 0x880355f21e6d1965;
const uint64_t *pos = (const uint64_t *)buf;
const uint64_t *end = pos + (len / 8);
const unsigned char *pos2;
--
2.43.0
From 6bd53c5ce11a44d39ad1deccc6c84e32b0d9a9fd Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Mon, 27 Nov 2023 17:03:38 +0700
Subject: [PATCH v9 1/6] Vendor fasthash
MIT licensed
---
src/include/common/hashfn_unstable.h | 75 ++++++++++++++++++++++++++++
1 file changed, 75 insertions(+)
create mode 100644 src/include/common/hashfn_unstable.h
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
new file mode 100644
index 0000000000..a5bf965fa2
--- /dev/null
+++ b/src/include/common/hashfn_unstable.h
@@ -0,0 +1,75 @@
+/* The MIT License
+
+ Copyright (C) 2012 Zilong Tan (eric.zltan@gmail.com)
+
+ Permission is hereby granted, free of charge, to any person
+ obtaining a copy of this software and associated documentation
+ files (the "Software"), to deal in the Software without
+ restriction, including without limitation the rights to use, copy,
+ modify, merge, publish, distribute, sublicense, and/or sell copies
+ of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be
+ included in all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ SOFTWARE.
+*/
+
+#include "fasthash.h"
+
+// Compression function for Merkle-Damgard construction.
+// This function is generated using the framework provided.
+#define mix(h) ({ \
+ (h) ^= (h) >> 23; \
+ (h) *= 0x2127599bf4325c37ULL; \
+ (h) ^= (h) >> 47; })
+
+uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
+{
+ const uint64_t m = 0x880355f21e6d1965ULL;
+ const uint64_t *pos = (const uint64_t *)buf;
+ const uint64_t *end = pos + (len / 8);
+ const unsigned char *pos2;
+ uint64_t h = seed ^ (len * m);
+ uint64_t v;
+
+ while (pos != end) {
+ v = *pos++;
+ h ^= mix(v);
+ h *= m;
+ }
+
+ pos2 = (const unsigned char*)pos;
+ v = 0;
+
+ switch (len & 7) {
+ case 7: v ^= (uint64_t)pos2[6] << 48;
+ case 6: v ^= (uint64_t)pos2[5] << 40;
+ case 5: v ^= (uint64_t)pos2[4] << 32;
+ case 4: v ^= (uint64_t)pos2[3] << 24;
+ case 3: v ^= (uint64_t)pos2[2] << 16;
+ case 2: v ^= (uint64_t)pos2[1] << 8;
+ case 1: v ^= (uint64_t)pos2[0];
+ h ^= mix(v);
+ h *= m;
+ }
+
+ return mix(h);
+}
+
+uint32_t fasthash32(const void *buf, size_t len, uint32_t seed)
+{
+ // the following trick converts the 64-bit hashcode to Fermat
+ // residue, which shall retain information from both the higher
+ // and lower parts of hashcode.
+ uint64_t h = fasthash64(buf, len, seed);
+ return h - (h >> 32);
+}
--
2.43.0
