From: Stephen Hemminger <stephen.hemminger@vyatta.com>
To: Eric Dumazet <eric.dumazet@gmail.com>
Cc: 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,
Al Viro <viro@zeniv.linux.org.uk>
Subject: Re: [PATCH] dcache: better name hash function
Date: Mon, 26 Oct 2009 22:19:44 -0700 (PDT) [thread overview]
Message-ID: <19864844.24581256620784317.JavaMail.root@tahiti.vyatta.com> (raw)
In-Reply-To: <9986527.24561256620662709.JavaMail.root@tahiti.vyatta.com>
One of the root causes of slowness in network usage
was my original choice of power of 2 for hash size, to avoid
a mod operation. It turns out if size is not a power of 2
the original algorithm works fairly well.
On slow cpu; with 10million entries and 211 hash size
Algorithm Time Ratio Max StdDev
string10 1.271871 1.00 47397 0.01
djb2 1.406322 1.00 47452 0.12
SuperFastHash 1.422348 1.00 48400 1.99
string_hash31 1.424079 1.00 47437 0.08
jhash_string 1.459232 1.00 47954 1.01
sdbm 1.499209 1.00 47499 0.22
fnv32 1.539341 1.00 47728 0.75
full_name_hash 1.556792 1.00 47412 0.04
string_hash17 1.719039 1.00 47413 0.05
pjw 1.827365 1.00 47441 0.09
elf 2.033545 1.00 47441 0.09
fnv64 2.199533 1.00 47666 0.53
crc 5.705784 1.00 47913 0.95
md5_string 10.308376 1.00 47946 1.00
fletcher 1.418866 1.01 53189 18.65
adler32 2.842117 1.01 53255 18.79
kr_hash 1.175678 6.43 468517 507.44
xor 1.114692 11.02 583189 688.96
lastchar 0.795316 21.10 1000000 976.02
How important is saving the one division, versus getting better
distribution.
next parent reply other threads:[~2009-10-27 5:19 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <9986527.24561256620662709.JavaMail.root@tahiti.vyatta.com>
2009-10-27 5:19 ` Stephen Hemminger [this message]
2009-10-27 5:24 ` [PATCH] dcache: better name hash function David Miller
2009-10-27 17:22 ` [PATCH] net: fold network name hash Stephen Hemminger
2009-10-27 18:02 ` Octavian Purdila
2009-10-27 22:04 ` [PATCH] net: fold network name hash (v2) Stephen Hemminger
2009-10-28 6:07 ` Eric Dumazet
2009-10-28 9:28 ` David Miller
2009-10-28 15:57 ` Stephen Hemminger
2009-10-27 6:07 ` [PATCH] dcache: better name hash function 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
2009-10-25 19:58 [PATCH next-next-2.6] netdev: better dev_name_hash Octavian Purdila
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
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=19864844.24581256620784317.JavaMail.root@tahiti.vyatta.com \
--to=stephen.hemminger@vyatta.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=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.