lkml.org 
[lkml]   [2009]   [Oct]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH] dcache: better name hash function
Previously Stephen kindly sent me the source and instructions, and attached are 
results from 1.0 GHz Itanium "McKinley" processors using an older gcc, both -O2
and -O3, -O2 first:

>>>
>>>
>>> $ ./hashtest 10000000 14 | sort -n -k 3 -k 2
>>> Algorithm Time Ratio Max StdDev
>>> string10 0.234133 1.00 612 0.03
>>> fnv32 0.241471 1.00 689 0.93
>>> fnv64 0.241964 1.00 680 0.85
>>> string_hash17 0.269656 1.00 645 0.36
>>> jhash_string 0.295795 1.00 702 1.00
>>> crc 1.609449 1.00 634 0.41
>>> md5_string 2.479467 1.00 720 0.99
>>> SuperFastHash 0.273793 1.01 900 2.13
>>> djb2 0.265877 1.15 964 9.52
>>> string_hash31 0.259110 1.21 1039 11.39
>>> sdbm 0.369414 2.87 3268 33.77
>>> elf 0.372251 3.71 2907 40.71
>>> pjw 0.401732 3.71 2907 40.71
>>> full_name_hash 0.283508 13.09 8796 85.91
>>> kr_hash 0.220033 499.17 468448 551.55
>>> fletcher 0.267009 499.17 468448 551.55
>>> adler32 0.635047 499.17 468448 551.55
>>> xor 0.220314 854.94 583189 722.12
>>> lastchar 0.155236 1637.61 1000000 999.69
>>
>>
>> here then are both, from a 1.0 GHz McKinley system, 64-bit, using an older
>> gcc
>>
>> raj@oslowest:~/hashtest$ ./hashtest 10000000 14 | sort -n -k 3 -k 2
>> Algorithm Time Ratio Max StdDev
>> string_hash17 0.901319 1.00 645 0.36
>> string10 0.986391 1.00 612 0.03
>> jhash_string 1.422065 1.00 702 1.00
>> fnv32 1.705116 1.00 689 0.93
>> fnv64 1.900326 1.00 680 0.85
>> crc 3.651519 1.00 634 0.41
>> md5_string 14.155621 1.00 720 0.99
>> SuperFastHash 1.185206 1.01 900 2.13
>> djb2 0.977166 1.15 964 9.52
>> string_hash31 0.989804 1.21 1039 11.39
>> sdbm 1.188299 2.87 3268 33.77
>> pjw 1.185963 3.71 2907 40.71
>> elf 1.257023 3.71 2907 40.71
>> full_name_hash 1.231514 13.09 8796 85.91
>> kr_hash 0.890761 499.17 468448 551.55
>> fletcher 1.080981 499.17 468448 551.55
>> adler32 4.141714 499.17 468448 551.55
>> xor 1.061445 854.94 583189 722.12
>> lastchar 0.676697 1637.61 1000000 999.69
>>
>> raj@oslowest:~/hashtest$ ./hashtest 10000000 8 | sort -n -k 3 -k 2
>> Algorithm Time Ratio Max StdDev
>> string_hash17 0.899988 1.00 39497 1.50
>> string10 0.985100 1.00 39064 0.01
>> SuperFastHash 1.141748 1.00 40497 2.17
>> jhash_string 1.376414 1.00 39669 1.04
>> fnv32 1.656967 1.00 39895 2.25
>> fnv64 1.855259 1.00 39215 0.35
>> crc 3.615341 1.00 39088 0.07
>> md5_string 14.113307 1.00 39605 0.98
>> djb2 0.972180 1.15 60681 76.16
>> string_hash31 0.982233 1.21 64950 91.12
>> sdbm 1.181952 2.38 129900 232.22
>> pjw 1.178994 2.45 99990 237.86
>> elf 1.250936 2.45 99990 237.86
>> kr_hash 0.892633 7.80 468451 515.52
>> fletcher 1.082932 7.80 468451 515.52
>> adler32 4.142414 7.80 468451 515.52
>> full_name_hash 1.175324 13.09 562501 687.24
>> xor 1.060091 13.36 583189 694.98
>> lastchar 0.675610 25.60 1000000 980.27
>>
>> raj@oslowest:~/hashtest$ gcc -v
>> Using built-in specs.
>> Target: ia64-linux-gnu
>> Configured with: ../src/configure -v
--enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr
--enable-shared --with-system-zlib --libexecdir=/usr/lib
--without-included-gettext --enable-threads=posix --enable-nls
--program-suffix=-4.1 --enable-__cxa_atexit --enable-clocale=gnu
--enable-libstdcxx-debug --enable-mpfr --disable-libssp --with-system-libunwind
--enable-checking=release ia64-linux-gnu
>> Thread model: posix
>> gcc version 4.1.2 20061115 (prerelease) (Debian 4.1.1-21)
>> raj@oslowest:~/hashtest$
>>
>> fnv doesn't seem to do as well there relative to the others as it did in your
>> tests.
>
>
>
> You could try -O3 since then gcc may replace the multiply with shift/add
> or is there something about forcing 32 and 64 bit that makes ia64 suffer.


It seems to speed things up, but the relative ordering remains the same:

oslowest:/home/raj/hashtest# make
cc -O3 -Wall -c -o hashtest.o hashtest.c
cc -O3 -Wall -c -o md5.o md5.c
cc -lm hashtest.o md5.o -o hashtest
oslowest:/home/raj/hashtest# ./hashtest 10000000 14 | sort -n -k 3 -k 2
Algorithm Time Ratio Max StdDev
string_hash17 0.893813 1.00 645 0.36
string10 0.965596 1.00 612 0.03
jhash_string 1.387773 1.00 702 1.00
fnv32 1.699041 1.00 689 0.93
fnv64 1.882314 1.00 680 0.85
crc 3.273676 1.00 634 0.41
md5_string 13.913745 1.00 720 0.99
SuperFastHash 1.135802 1.01 900 2.13
djb2 0.951571 1.15 964 9.52
string_hash31 0.971081 1.21 1039 11.39
sdbm 1.168148 2.87 3268 33.77
pjw 1.159304 3.71 2907 40.71
elf 1.237662 3.71 2907 40.71
full_name_hash 1.212588 13.09 8796 85.91
kr_hash 0.856584 499.17 468448 551.55
fletcher 1.054516 499.17 468448 551.55
adler32 4.123742 499.17 468448 551.55
xor 1.031910 854.94 583189 722.12
lastchar 0.648597 1637.61 1000000 999.69
oslowest:/home/raj/hashtest# ./hashtest 10000000 8 | sort -n -k 3 -k 2
Algorithm Time Ratio Max StdDev
string_hash17 0.884829 1.00 39497 1.50
string10 0.962258 1.00 39064 0.01
SuperFastHash 1.088602 1.00 40497 2.17
jhash_string 1.340878 1.00 39669 1.04
fnv32 1.637096 1.00 39895 2.25
fnv64 1.842330 1.00 39215 0.35
crc 3.230291 1.00 39088 0.07
md5_string 13.863056 1.00 39605 0.98
djb2 0.944159 1.15 60681 76.16
string_hash31 0.961978 1.21 64950 91.12
sdbm 1.159156 2.38 129900 232.22
pjw 1.154286 2.45 99990 237.86
elf 1.232842 2.45 99990 237.86
kr_hash 0.856873 7.80 468451 515.52
fletcher 1.055389 7.80 468451 515.52
adler32 4.123254 7.80 468451 515.52
full_name_hash 1.152628 13.09 562501 687.24
xor 1.033050 13.36 583189 694.98
lastchar 0.647504 25.60 1000000 980.27



\
 
 \ /
  Last update: 2009-10-27 17:41    [W:0.065 / U:0.152 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site