From: Rick Jones <rick.jones2@hp.com>
To: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Stephen Hemminger <shemminger@vyatta.com>,
Al Viro <viro@zeniv.linux.org.uk>,
Andrew Morton <akpm@linux-foundation.org>,
Linus Torvalds <torvalds@linux-foundation.org>,
Octavian Purdila <opurdila@ixiacom.com>,
netdev@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: Re: [PATCH] dcache: better name hash function
Date: Tue, 27 Oct 2009 09:38:31 -0700 [thread overview]
Message-ID: <4AE72207.4030702@hp.com> (raw)
In-Reply-To: <4AE65EDE.8080605@gmail.com>
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
next prev parent reply other threads:[~2009-10-27 16:38 UTC|newest]
Thread overview: 35+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-10-25 19:58 [PATCH next-next-2.6] netdev: better dev_name_hash Octavian Purdila
2009-10-25 20:17 ` Hagen Paul Pfeifer
2009-10-25 21:24 ` Eric Dumazet
2009-10-25 21:55 ` Octavian Purdila
2009-10-25 22:41 ` Hagen Paul Pfeifer
2009-10-25 22:45 ` Octavian Purdila
2009-10-26 5:28 ` Eric Dumazet
2009-10-26 13:07 ` Krishna Kumar2
2009-10-26 14:31 ` Octavian Purdila
2009-10-26 14:55 ` Eric Dumazet
2009-10-26 15:52 ` Octavian Purdila
2009-10-26 16:55 ` Stephen Hemminger
2009-10-26 17:45 ` Stephen Hemminger
2009-10-27 1:24 ` David Miller
2009-10-27 1:40 ` Eric Dumazet
2009-10-26 6:30 ` Stephen Hemminger
2009-10-26 7:48 ` Eric Dumazet
2009-10-26 4:43 ` Stephen Hemminger
2009-10-26 22:36 ` [PATCH] dcache: better name hash function Stephen Hemminger <shemminger@vyatta.com>, Al Viro
2009-10-27 2:45 ` Eric Dumazet
2009-10-27 3:53 ` Stephen Hemminger
2009-10-27 16:38 ` Rick Jones [this message]
[not found] <9986527.24561256620662709.JavaMail.root@tahiti.vyatta.com>
2009-10-27 5:19 ` Stephen Hemminger
2009-10-27 5:24 ` David Miller
2009-10-27 6:07 ` Eric Dumazet
2009-10-27 6:50 ` Eric Dumazet
2009-10-27 7:29 ` Eric Dumazet
2009-10-27 17:07 ` Stephen Hemminger
2009-10-27 17:32 ` Linus Torvalds
2009-10-27 23:08 ` Stephen Hemminger
2009-10-27 23:41 ` Linus Torvalds
2009-10-28 0:10 ` Stephen Hemminger
2009-10-28 0:58 ` Linus Torvalds
2009-10-28 1:56 ` Stephen Hemminger
[not found] ` <4AE72B91.7040700@gmail.com>
2009-10-27 17:35 ` Stephen Hemminger
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4AE72207.4030702@hp.com \
--to=rick.jones2@hp.com \
--cc=akpm@linux-foundation.org \
--cc=eric.dumazet@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=netdev@vger.kernel.org \
--cc=opurdila@ixiacom.com \
--cc=shemminger@vyatta.com \
--cc=torvalds@linux-foundation.org \
--cc=viro@zeniv.linux.org.uk \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).