On 2/13/2020 11:41 PM, Jason Gunthorpe wrote:
On Thu, Feb 13, 2020 at 10:26:09AM -0500, Tom Talpey wrote:
If both src & dst ports are in the high value range you loss those
hash bits in the masking.
If src & dst port are both 0xE000, your masked hash equals 0. You'll
get the same hash if both ports are equal 0xF000.
Sure, but this is because it's a 20-bit hash of a 32-bit object. There
will always be collisions, this is just one example. My concern is the
statistical spread of the results. I argue it's not changed by the
proposed bit-folding, possibly even damaged.
I've always thought that 'folding' by modulo results in an abnormal
statistical distribution
The point here is not collisions but to have a hash distribution which
is generally uniform for the input space.
Alex, it would be good to make a quick program to measure the
uniformity of the distribution..
Hi,
I did some tests with a quick program (hope it's not buggy...), seems
the hash without "folding" has a better distribution than hash with
fold. The "hash quality" is reflected by the "total_access"[1] below.
I tested only with cma_dport from 18515 (ib_write_bw default) to 18524.
I can do more tests if required, for example use multiple cma_dport in
one statistic.
[1]
https://stackoverflow.com/questions/24729730/measuring-a-hash-functions-quality-for-use-with-maps-assosiative-arrays
$ ./a
max: Say for slot x there are tb[x] items, then 'max = max(tb[x])';
Lower is better;
min: Say for slot x there are tb[x] items, then 'min = min(tb[x])';
Likely min is always 0
total_access: The sum of all 'accesses' (for each slot:
accesses=n*(n+1)/2); Lower is better
n[X]: How many slots that has X items
cm source port range [32768, 65534], dest port 18515:
Hash with folding:
flow_label: max 2 min 0 total_access 32766 n[1] = 32514 n[2] = 126
udp_sport: max 10 min 0 total_access 51740 n[1] = 4420 n[2] =
4670 n[3] = 3112 n[4] = 1433 n[5] = 535 n[6] = 163 n[7] = 31
n[8] = 5 n[9] = 2 n[10] = 1
Hash without folding:
flow_label: max 1 min 0 total_access 32766 n[1] = 32766
udp_sport: max 4 min 0 total_access 48618 n[1] = 532 n[2] =
7926 n[3] = 530 n[4] = 3698
cm source port range [32768, 65534], dest port 18516:
Hash with folding:
flow_label: max 3 min 0 total_access 32774 n[1] = 31214 n[2] = 770
n[3] = 4
udp_sport: max 8 min 0 total_access 50808 n[1] = 4406 n[2] =
4873 n[3] = 3157 n[4] = 1413 n[5] = 509 n[6] = 129 n[7] = 20
n[8] = 4
Hash without folding:
flow_label: max 1 min 0 total_access 32766 n[1] = 32766
udp_sport: max 2 min 1 total_access 32766 n[1] = 2 n[2] = 16382
cm source port range [32768, 65534], dest port 18517:
Hash with folding:
flow_label: max 2 min 0 total_access 32766 n[1] = 32250 n[2] = 258
udp_sport: max 10 min 0 total_access 54916 n[1] = 4536 n[2] =
4170 n[3] = 2817 n[4] = 1445 n[5] = 622 n[6] = 275 n[7] = 94
n[8] = 22 n[9] = 5 n[10] = 2
Hash without folding:
flow_label: max 1 min 0 total_access 32766 n[1] = 32766
udp_sport: max 3 min 1 total_access 38402 n[1] = 2820 n[2] =
10746 n[3] = 2818
cm source port range [32768, 65534], dest port 18518:
Hash with folding:
flow_label: max 2 min 0 total_access 32766 n[1] = 32066 n[2] = 350
udp_sport: max 8 min 0 total_access 50018 n[1] = 4435 n[2] =
4970 n[3] = 3294 n[4] = 1376 n[5] = 465 n[6] = 92 n[7] = 16
n[8] = 2
Hash without folding:
flow_label: max 1 min 0 total_access 32766 n[1] = 32766
udp_sport: max 2 min 1 total_access 32766 n[1] = 2 n[2] = 16382
cm source port range [32768, 65534], dest port 18519:
Hash with folding:
flow_label: max 3 min 0 total_access 32774 n[1] = 31816 n[2] = 469
n[3] = 4
udp_sport: max 8 min 0 total_access 51462 n[1] = 4414 n[2] =
4734 n[3] = 3088 n[4] = 1466 n[5] = 508 n[6] = 160 n[7] = 32
n[8] = 4
Hash without folding:
flow_label: max 1 min 0 total_access 32766 n[1] = 32766
udp_sport: max 4 min 0 total_access 45490 n[1] = 3662 n[2] =
6360 n[3] = 3660 n[4] = 1351
cm source port range [32768, 65534], dest port 18520:
Hash with folding:
flow_label: max 6 min 0 total_access 34618 n[1] = 20349 n[2] =
5027 n[3] = 550 n[4] = 164 n[5] = 9 n[6] = 2
udp_sport: max 13 min 0 total_access 82542 n[1] = 549 n[2] =
1167 n[3] = 1635 n[4] = 1706 n[5] = 1341 n[6] = 836 n[7] = 483
n[8] = 223 n[9] = 87 n[10] = 27
Hash without folding:
flow_label: max 1 min 0 total_access 32766 n[1] = 32766
udp_sport: max 4 min 0 total_access 65530
n[3] = 2 n[4] = 8190
cm source port range [32768, 65534], dest port 18521:
Hash with folding:
flow_label: max 2 min 0 total_access 32766 n[1] = 31924 n[2] = 421
udp_sport: max 9 min 0 total_access 51864 n[1] = 4505 n[2] =
4645 n[3] = 3038 n[4] = 1464 n[5] = 542 n[6] = 154 n[7] = 43
n[8] = 6 n[9] = 2
Hash without folding:
flow_label: max 1 min 0 total_access 32766 n[1] = 32766
udp_sport: max 3 min 1 total_access 32810 n[1] = 24 n[2] =
16338 n[3] = 22
cm source port range [32768, 65534], dest port 18522:
Hash with folding:
flow_label: max 3 min 0 total_access 32768 n[1] = 32197 n[2] = 283
n[3] = 1
udp_sport: max 9 min 0 total_access 50850 n[1] = 4561 n[2] =
4756 n[3] = 3187 n[4] = 1452 n[5] = 453 n[6] = 137 n[7] = 29
n[8] = 2 n[9] = 2
Hash without folding:
flow_label: max 1 min 0 total_access 32766 n[1] = 32766
udp_sport: max 2 min 1 total_access 32766 n[1] = 2 n[2] = 16382
cm source port range [32768, 65534], dest port 18523:
Hash with folding:
flow_label: max 2 min 0 total_access 32766 n[1] = 32514 n[2] = 126
udp_sport: max 8 min 0 total_access 52208 n[1] = 4426 n[2] =
4609 n[3] = 3069 n[4] = 1435 n[5] = 533 n[6] = 180 n[7] = 50
n[8] = 10
Hash without folding:
flow_label: max 1 min 0 total_access 32766 n[1] = 32766
udp_sport: max 4 min 0 total_access 46062 n[1] = 3096 n[2] =
6640 n[3] = 3094 n[4] = 1777
cm source port range [32768, 65534], dest port 18524:
Hash with folding:
flow_label: max 3 min 0 total_access 32774 n[1] = 31362 n[2] = 696
n[3] = 4
udp_sport: max 8 min 0 total_access 49490 n[1] = 4440 n[2] =
5148 n[3] = 3240 n[4] = 1413 n[5] = 394 n[6] = 97 n[7] = 14
n[8] = 1
Hash without folding:
flow_label: max 1 min 0 total_access 32766 n[1] = 32766
udp_sport: max 2 min 1 total_access 32766 n[1] = 2 n[2] = 16382
Jason
