Subject: Re: [PATCH next-next-2.6] netdev: better dev_name_hash

From: Stephen Hemminger <[email-masked]>
Date: Mon, 26 Oct 2009 09:55:16 -0700

Added more algorithms to test...

Time is in seconds for 10000000 entries with hashbits = 8
Ratio is number of probes / ideal hash probes

Result sorted by distribution:

Algorithm             Time       Ratio       Max   StdDev
string10             1.434087       1.00     39064   0.01
SuperFastHash        1.469511       1.00     40497   2.17
string_hash17        1.472544       1.00     39497   1.50
jhash_string         1.501508       1.00     39669   1.04
crc                  2.826795       1.00     39088   0.07
md5_string           3.608253       1.00     39605   0.98
djb2                 1.462722       1.15     60681  76.16
string_hash31        1.457253       1.21     64950  91.12
sdbm                 1.566174       2.38    129900 232.22
pjw                  1.527306       2.45     99990 237.86
elf                  1.576096       2.45     99990 237.86
kr_hash              1.400072       7.80    468451 515.52
fletcher             1.449671       7.80    468451 515.52
full_name_hash       1.487707      13.09    562501 687.24
xor                  1.400403      13.36    583189 694.98
lastchar             1.348798      25.60   1000000 980.27

Another run sorted by speed:
Algorithm             Time       Ratio       Max   StdDev
lastchar             1.338545      25.60   1000000 980.27
kr_hash              1.398453       7.80    468451 515.52
xor                  1.398843      13.36    583189 694.98
string10             1.432756       1.00     39064   0.01
fletcher             1.448499       7.80    468451 515.52
string_hash31        1.457524       1.21     64950  91.12
string_hash17        1.462548       1.00     39497   1.50
djb2                 1.462956       1.15     60681  76.16
SuperFastHash        1.469907       1.00     40497   2.17
full_name_hash       1.486465      13.09    562501 687.24
jhash_string         1.500959       1.00     39669   1.04
pjw                  1.526097       2.45     99990 237.86
sdbm                 1.566533       2.38    129900 232.22
elf                  1.576470       2.45     99990 237.86
crc                  2.811210       1.00     39088   0.07
md5_string           3.604675       1.00     39605   0.98