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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.