Seeing as we have a simple, elegant, and effective hash_long in
hash.h, and seeing that I need to hash things that aren't a long
(i.e. strings), I would like to propose defining "hash_mem" based on
hash_long as done in the following patch (hash_mem already exists
local to net/sunrpc/svcauth.c, this patch tidies it up and moves it to
lib/hash.c).
It could be argued that there are better hashing functions for
strings, and indeed Andrew Morton pointed me to ext3/hash.c
I did a little testing and found that on a list of 2 million
basenames from a recent backup index (800,000 unique):
hash_mem (as included here) is noticably faster than HASH_HALF_MD4 or
HASH_TEA:
hash_mem: 10 seconds
DX_HASH_HALF_MD4: 14 seconds
DX_HASH_TEA: 15.2 seconds
but that hash_mem is slightly worse at distributing the names into an
8bit space. The normalised standard deviation of the frequencies of
the 256 possibly hash values (which you would like to be small) was:
hash_mem: 0.0225508
DX_HASH_HALF_MD4 0.0182673
DX_HASH_TEA 0.0169549
so for a general-purpose internal hash function, I think hash_mem
wins :-)
Statisticians: please be gentle if I have said something silly - it's
a while since I have done much formal maths.
### Comments for ChangeSet
Define hash_mem in lib/hash.c to apply hash_long to an arbitraty piece of memory.
This moves hash_mem out of net/sunrpc/svcauth.c where it was used to hash
some strings, into lib/hash.c where it can be used by everyone.
As some achitectures don't like dereferencing unalinged longs we
always memcpy into a long if the buffer isn't aligned.
Unfortunately the 'unlikely' doesn't move the unlikely code very
far out of the way. It is still between the function entry and
exit points.
----------- Diffstat output ------------
./include/linux/hash.h | 5 ++++
./include/linux/string.h | 3 ++
./include/linux/sunrpc/svcauth.h | 7 -----
./lib/Makefile | 4 +--
./lib/hash.c | 47 +++++++++++++++++++++++++++++++++++++++
./net/sunrpc/svcauth.c | 20 ----------------
./net/sunrpc/svcauth_unix.c | 1
7 files changed, 59 insertions(+), 28 deletions(-)
diff ./include/linux/hash.h~current~ ./include/linux/hash.h
--- ./include/linux/hash.h~current~ 2003-01-07 14:43:38.000000000 +1100
+++ ./include/linux/hash.h 2003-01-07 13:55:28.000000000 +1100
@@ -55,4 +55,9 @@ static inline unsigned long hash_ptr(voi
{
return hash_long((unsigned long)ptr, bits);
}
+
+
+extern unsigned long hash_mem(void *buf, unsigned int len, unsigned int bits);
+/* hash_str is also available in linux/string.h */
+
#endif /* _LINUX_HASH_H */
diff ./include/linux/string.h~current~ ./include/linux/string.h
--- ./include/linux/string.h~current~ 2003-01-07 14:43:38.000000000 +1100
+++ ./include/linux/string.h 2003-01-07 13:54:59.000000000 +1100
@@ -82,5 +82,8 @@ extern void * memchr(const void *,int,__
}
#endif
+/* #define rather than inline so hash.h isn't needed for compilation */
+#define hash_str(str,bits) hash_mem(str, strlen(str), bits)
+
#endif
#endif /* _LINUX_STRING_H_ */
diff ./include/linux/sunrpc/svcauth.h~current~ ./include/linux/sunrpc/svcauth.h
--- ./include/linux/sunrpc/svcauth.h~current~ 2003-01-07 14:43:38.000000000 +1100
+++ ./include/linux/sunrpc/svcauth.h 2003-01-07 14:30:21.000000000 +1100
@@ -14,7 +14,6 @@
#include <linux/string.h>
#include <linux/sunrpc/msg_prot.h>
#include <linux/sunrpc/cache.h>
-#include <linux/string.h>
struct svc_cred {
uid_t cr_uid;
@@ -113,12 +112,6 @@ extern struct auth_domain *auth_unix_loo
extern int auth_unix_forget_old(struct auth_domain *dom);
extern void svcauth_unix_purge(void);
-extern int hash_mem(char *buf, int len, int bits);
-static inline int hash_str(char *name, int bits)
-{
- return hash_mem(name, strlen(name), bits);
-}
-
extern struct cache_detail auth_domain_cache, ip_map_cache;
#endif /* __KERNEL__ */
diff ./lib/Makefile~current~ ./lib/Makefile
--- ./lib/Makefile~current~ 2003-01-07 14:43:38.000000000 +1100
+++ ./lib/Makefile 2003-01-07 13:51:45.000000000 +1100
@@ -9,11 +9,11 @@
L_TARGET := lib.a
export-objs := cmdline.o dec_and_lock.o rwsem-spinlock.o rwsem.o \
- crc32.o rbtree.o radix-tree.o kobject.o
+ crc32.o rbtree.o radix-tree.o kobject.o hash.o
obj-y := errno.o ctype.o string.o vsprintf.o brlock.o cmdline.o \
bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
- kobject.o
+ kobject.o hash.o
obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
obj-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
diff ./lib/hash.c~current~ ./lib/hash.c
--- ./lib/hash.c~current~ 2003-01-07 14:43:38.000000000 +1100
+++ ./lib/hash.c 2003-01-07 14:00:53.000000000 +1100
@@ -0,0 +1,47 @@
+/*
+ * linux/lib/hash.c
+ *
+ * No Copyright Claimed.
+ * Author: Neil Brown
+ */
+
+#include <linux/types.h>
+#include <linux/hash.h>
+#include <linux/compiler.h>
+#include <linux/module.h>
+
+#define BYTES_PER_LONG (BITS_PER_LONG/8)
+#define IsLongAligned(ptr) (((unsigned long)ptr & (BYTES_PER_LONG-1))==0)
+unsigned long hash_mem(void *buf, unsigned int len, unsigned int bits)
+{
+ int hash = 0;
+ unsigned long l;
+
+ if (unlikely(IsLongAligned(buf))) {
+
+ /* Some architectures don't like dereferencing a long
+ * pointer that isn't aligned, so we do it by hand...
+ */
+ while (len >= BYTES_PER_LONG) {
+ memcpy(&l, buf, BYTES_PER_LONG);
+ buf += BYTES_PER_LONG;
+ len -= BYTES_PER_LONG;
+ hash ^= hash_long(l, bits);
+ }
+ } else {
+ while (len >= BYTES_PER_LONG) {
+ l = *(unsigned long *)buf;
+ buf += BYTES_PER_LONG;
+ len -= BYTES_PER_LONG;
+ hash ^= hash_long(l, bits);
+ }
+ }
+ if (len) {
+ l=0;
+ memcpy((char*)&l, buf, len);
+ hash ^= hash_long(l, bits);
+ }
+ return hash;
+}
+
+EXPORT_SYMBOL(hash_mem);
diff ./net/sunrpc/svcauth.c~current~ ./net/sunrpc/svcauth.c
--- ./net/sunrpc/svcauth.c~current~ 2003-01-07 14:43:38.000000000 +1100
+++ ./net/sunrpc/svcauth.c 2003-01-07 14:44:02.000000000 +1100
@@ -17,6 +17,7 @@
#include <linux/sunrpc/svcauth.h>
#include <linux/err.h>
#include <linux/hash.h>
+#include <linux/string.h>
#define RPCDBG_FACILITY RPCDBG_AUTH
@@ -97,25 +98,6 @@ svc_auth_unregister(rpc_authflavor_t fla
* it will complain.
*/
-int hash_mem(char *buf, int len, int bits)
-{
- int hash = 0;
- unsigned long l;
- while (len >= BITS_PER_LONG/8) {
- l = *(unsigned long *)buf;
- buf += BITS_PER_LONG/8;
- len -= BITS_PER_LONG/8;
- hash ^= hash_long(l, bits);
- }
- if (len) {
- l=0;
- memcpy((char*)&l, buf, len);
- hash ^= hash_long(l, bits);
- }
- return hash;
-}
-
-
/*
* Auth auth_domain cache is somewhat different to other caches,
* largely because the entries are possibly of different types:
diff ./net/sunrpc/svcauth_unix.c~current~ ./net/sunrpc/svcauth_unix.c
--- ./net/sunrpc/svcauth_unix.c~current~ 2003-01-07 14:43:38.000000000 +1100
+++ ./net/sunrpc/svcauth_unix.c 2003-01-07 14:31:11.000000000 +1100
@@ -7,6 +7,7 @@
#include <linux/err.h>
#include <linux/seq_file.h>
#include <linux/hash.h>
+#include <linux/string.h>
#define RPCDBG_FACILITY RPCDBG_AUTH
Neil Brown <[email protected]> writes:
> +unsigned long hash_mem(void *buf, unsigned int len, unsigned int bits)
> +{
> + int hash = 0;
Shouldn't that be unsigned long?
BTW, in my experience using a good hash function is usually more
important than using a fast hash function. Especially the use of '^'
here could lead to very bad performance in obscure cases because of
bit canceling.
--
Falk
On Tue, Jan 07, 2003 at 04:03:28PM +1100, Neil Brown wrote:
> I did a little testing and found that on a list of 2 million
> basenames from a recent backup index (800,000 unique):
>
> hash_mem (as included here) is noticably faster than HASH_HALF_MD4 or
> HASH_TEA:
>
> hash_mem: 10 seconds
> DX_HASH_HALF_MD4: 14 seconds
> DX_HASH_TEA: 15.2 seconds
I'm curious how the hash at
http://www.burtleburtle.net/bob/hash/doobs.html would fare. He has a
64-bit version at
http://www.burtleburtle.net/bob/c/lookup8.c.
On Monday January 6, [email protected] wrote:
> On Tue, Jan 07, 2003 at 04:03:28PM +1100, Neil Brown wrote:
> > I did a little testing and found that on a list of 2 million
> > basenames from a recent backup index (800,000 unique):
> >
> > hash_mem (as included here) is noticably faster than HASH_HALF_MD4 or
> > HASH_TEA:
> >
> > hash_mem: 10 seconds
> > DX_HASH_HALF_MD4: 14 seconds
> > DX_HASH_TEA: 15.2 seconds
>
> I'm curious how the hash at
> http://www.burtleburtle.net/bob/hash/doobs.html would fare. He has a
> 64-bit version at
> http://www.burtleburtle.net/bob/c/lookup8.c.
Performing the same tests: producing 8 bit hashes from 800,000
filenames.
Speed is 10 seconds, comarable to hash_mem
normalised standard deviation of frequencies is 0.0171039
which is is the same ball park as the hashes ext3 uses
(they gave 0.0169 and 0.0182. hash_mem gave 0.02255).
So (on this set of values at least) it does seem to be a better hash
function.
I might look more closely at it.
Thanks,
NeilBrown
On Tue, 7 Jan 2003, Neil Brown wrote:
> + if (unlikely(IsLongAligned(buf))) {
> +
> + /* Some architectures don't like dereferencing a long
> + * pointer that isn't aligned, so we do it by hand...
> + */
> + while (len >= BYTES_PER_LONG) {
> + memcpy(&l, buf, BYTES_PER_LONG);
Ugh. What a crock.
This is what we have "get_unaligned()" for.
Linus
On Mon, 2003-01-06 at 21:03, Neil Brown wrote:
> Seeing as we have a simple, elegant, and effective hash_long in
> hash.h, and seeing that I need to hash things that aren't a long
> (i.e. strings), I would like to propose defining "hash_mem" based on
> hash_long as done in the following patch (hash_mem already exists
> local to net/sunrpc/svcauth.c, this patch tidies it up and moves it to
> lib/hash.c).
>
> It could be argued that there are better hashing functions for
> strings, and indeed Andrew Morton pointed me to ext3/hash.c
>
> I did a little testing and found that on a list of 2 million
> basenames from a recent backup index (800,000 unique):
>
> hash_mem (as included here) is noticably faster than HASH_HALF_MD4 or
> HASH_TEA:
>
> hash_mem: 10 seconds
> DX_HASH_HALF_MD4: 14 seconds
> DX_HASH_TEA: 15.2 seconds
I think they have a different set of design requirements. They're both
designed to not only generate hashes, but make the hashes
cryptographically strong (ie, impossible to generate collisions with
less effort than brute force). They're naturally slower than a simple
hash, so you'd only use them if you need the stronger requirements.
J
On 6 Jan 2003, Jeremy Fitzhardinge wrote:
>
> I think they have a different set of design requirements. They're both
> designed to not only generate hashes, but make the hashes
> cryptographically strong (ie, impossible to generate collisions with
> less effort than brute force). They're naturally slower than a simple
> hash, so you'd only use them if you need the stronger requirements.
The filesystem hashes also have another design criteria: they need to
reliably give the _same_ hash on different machines.
In particular, the suggested hash_mem() thing is endian-unsafe, meaning
that it will give different answers on an x86 than on a sparc CPU, for
example. Which can be ok if the only thing you care about is some
temporary hash, but is unacceptable for a lot of uses. The filesystem
hashes (well, at least some of them) are also designed to hash out files
on the disk, which means that they _have_ to be the same regardless of
architecture, or you can't move disks between machines.
Quite frankly, I think the suggested hash_mem() is too special-cased to
make any sense as a generic function. The endian problems means that it
_isn't_ really generic anyway, and as such it might as well just be some
internal nfs helper function rather than something in <linux/string.h>
Linus
On Monday January 6, [email protected] wrote:
>
> On 6 Jan 2003, Jeremy Fitzhardinge wrote:
> >
> > I think they have a different set of design requirements. They're both
> > designed to not only generate hashes, but make the hashes
> > cryptographically strong (ie, impossible to generate collisions with
> > less effort than brute force). They're naturally slower than a simple
> > hash, so you'd only use them if you need the stronger requirements.
>
> The filesystem hashes also have another design criteria: they need to
> reliably give the _same_ hash on different machines.
>
> In particular, the suggested hash_mem() thing is endian-unsafe, meaning
> that it will give different answers on an x86 than on a sparc CPU, for
> example. Which can be ok if the only thing you care about is some
> temporary hash, but is unacceptable for a lot of uses. The filesystem
> hashes (well, at least some of them) are also designed to hash out files
> on the disk, which means that they _have_ to be the same regardless of
> architecture, or you can't move disks between machines.
Not only endian-unsafe but also word-length-unsafe!
I certainly never imagined hash_mem would be a replacement for an
externally visible hash function such as those used by ext3. Rather I
was wondering if one of those used by ext3 would be a suitable
candidate for hash_mem, and found that they weren't convincingly
better.
>
> Quite frankly, I think the suggested hash_mem() is too special-cased to
> make any sense as a generic function. The endian problems means that it
> _isn't_ really generic anyway, and as such it might as well just be some
> internal nfs helper function rather than something in <linux/string.h>
>
That's a shame.... It fills a similar purpose to full_name_hash in
dcache.h. It might be nice to have just one function for internal
hashing of names.
The proposed hash_mem() seems slightly better than full_name_hash, and
much the same speed (Depending on how you measure it...)
Maybe full_name_hash et.al could be moved to linux/hash.h and I could
use that ...
My current preferred internal 'hash-a-string' function is:
static inline unsigned long hash_str(unsigned char *name, int bits, char term)
{
unsigned long hash = 0;
unsigned long l = 0;
int len = 0;
unsigned char c;
while (likely(c = *name++) && likely(c != term)) {
l = (l << 8) | c;
len++;
if ((len & (BITS_PER_LONG/8-1))==0)
hash = hash_long(hash^l, BITS_PER_LONG);
}
l = l << 8 ^ len;
return hash_long(hash^l, bits);
}
Given that we need to search for a terminator, using *(unsigned long*)
doesn't really help.
This hash_str could be used in place of the namei/dcache hashing, and
can be used where I need to hash a string.
Would anyone like to independantly compare it with:
c = *(const unsigned char *)name;
hash = init_name_hash();
do {
name++;
hash = partial_name_hash(c, hash);
c = *(const unsigned char *)name;
} while (c && (c != '/'));
which is the comparable function from namei.c
NeilBrown