Re: [rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash
Quoting Gleb Kurtsou (from Fri, 24 Dec 2010 00:46:20 +0200): Hi, I've recently noticed that hash table use in nullfs was inefficient, 1/3 to half of buckets remained unused. I've started investigating it further and came across SuperFastHash hashing function, SFH (SuperFastHash) has BSD license, used in WebKit and other open source projects. Detailed description and Comparision with FNV and Bob Jenkin's hash can be found here: http://www.azillionmonkeys.com/qed/hash.html I found some web pages which tell about an unfair speed comparision and about a collision problem in SFH: http://coding.derkeiler.com/Archive/General/comp.programming/2005-03/0650.html http://www.team5150.com/~andrew/blog/2007/03/breaking_superfasthash.html http://blog.clawpaws.net/post/2007/04/22/Good-Hash-Functions It may be that this is not an issue for the use case we have here, but blindly replacing it without looking at the above web pages looks a little bit risky to me. Bye, Alexander. -- The use of money is all the advantage there is to having money. -- Benjamin Franklin http://www.Leidinger.netAlexander @ Leidinger.net: PGP ID = B0063FE7 http://www.FreeBSD.org netchild @ FreeBSD.org : PGP ID = 72077137 ___ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
Re: [rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash
On (26/12/2010 15:20), Ivan Voras wrote: > On 26 December 2010 14:24, Gleb Kurtsou wrote: > > On (25/12/2010 20:29), Ivan Voras wrote: > >> On 23.12.2010 23:46, Gleb Kurtsou wrote: > >> > >> > For testing I've used dbench with 16 processes on 1 Gb swap back md > >> > device, UFS + SoftUpdates: > >> > Old hash (Mb/s): 599.94 600.096 599.536 > >> > SFH hash (Mb/s): 612.439 612.341 609.673 > >> > > >> > It's just ~1% improvement, but dbench is not a VFS metadata intensive > >> > benchmark. Subjectively it feels faster accessing maildir mailboxes > >> > with ~10.000 messages : ) > >> > >> Try blogbench if you need metadata-intensive operations, or even fsx. > > > blogbench should be good, but I've always had hard time interpreting its > > results. Besides results tend to very a lot, there is no way to set seed > > value like in fsx, so that I could run exactly the same test in different > > configurations. > > I think the exact sequence of blogbench operations depends on duration > of previous operations (it's multithreaded) so from that angle you are Why should it? Operation order in dbench or fsx doesn't depend on duration of previous operations. > right - you can't do a repeatable run except in the trivial cases. On > the other hand, it uses rand() without seeding it with > srand()/sranddev() so this part is actually very repeatable :) I've once tried to make its behaviour more predictable, I can't find the patch and can't recall any specifics, but there were architectural issues. You are right, setting seed and calling rand() should give stable results, that's what I was trying to achieve. The other way to work around such "limitation" is too run sufficiently large number of tests. Which requires patience :) > > fsx is a different beast, it reads/writes/truncates at random offsets - > > great tool for debugging mmap/truncate issues. Patch doesn't improve it > > in any way. > > It depends on what metadata operations you require - blogbench will > create, find and write files (if we ignore atime); fsx will create a > decent amount of traffic with file size and mtime changes. In your > case you'll probably need to run it on a memory file system or tmpfs > due to sensitivity to disk IO latencies (if your improvements is on > the order of few percent). I meant create/readdir/remove as metadata intensive operations -- blogbench is very good for it. fsx creates single file. Most people will only notice changes in vfs_cache.c and UFS' dirhash, that's 600 Mb/s vs 613 Mb/s improvement I've written about above. I'd appreciate if someone could benchmark if_lagg, it was using hash32 for binary data, which could result in poor hash table usage, which could possibly make most of the data go on single interface. But there would be hardly any performance improvement due to limited network bandwidth. Besides old hash32 is faster than new SFH. ___ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
Re: [rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash
On 26 December 2010 14:24, Gleb Kurtsou wrote: > On (25/12/2010 20:29), Ivan Voras wrote: >> On 23.12.2010 23:46, Gleb Kurtsou wrote: >> >> > For testing I've used dbench with 16 processes on 1 Gb swap back md >> > device, UFS + SoftUpdates: >> > Old hash (Mb/s): 599.94 600.096 599.536 >> > SFH hash (Mb/s): 612.439 612.341 609.673 >> > >> > It's just ~1% improvement, but dbench is not a VFS metadata intensive >> > benchmark. Subjectively it feels faster accessing maildir mailboxes >> > with ~10.000 messages : ) >> >> Try blogbench if you need metadata-intensive operations, or even fsx. > blogbench should be good, but I've always had hard time interpreting its > results. Besides results tend to very a lot, there is no way to set seed > value like in fsx, so that I could run exactly the same test in different > configurations. I think the exact sequence of blogbench operations depends on duration of previous operations (it's multithreaded) so from that angle you are right - you can't do a repeatable run except in the trivial cases. On the other hand, it uses rand() without seeding it with srand()/sranddev() so this part is actually very repeatable :) > fsx is a different beast, it reads/writes/truncates at random offsets - > great tool for debugging mmap/truncate issues. Patch doesn't improve it > in any way. It depends on what metadata operations you require - blogbench will create, find and write files (if we ignore atime); fsx will create a decent amount of traffic with file size and mtime changes. In your case you'll probably need to run it on a memory file system or tmpfs due to sensitivity to disk IO latencies (if your improvements is on the order of few percent). ___ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
Re: [rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash
On (25/12/2010 20:29), Ivan Voras wrote: > On 23.12.2010 23:46, Gleb Kurtsou wrote: > > > For testing I've used dbench with 16 processes on 1 Gb swap back md > > device, UFS + SoftUpdates: > > Old hash (Mb/s): 599.94 600.096 599.536 > > SFH hash (Mb/s): 612.439 612.341 609.673 > > > > It's just ~1% improvement, but dbench is not a VFS metadata intensive > > benchmark. Subjectively it feels faster accessing maildir mailboxes > > with ~10.000 messages : ) > > Try blogbench if you need metadata-intensive operations, or even fsx. blogbench should be good, but I've always had hard time interpreting its results. Besides results tend to very a lot, there is no way to set seed value like in fsx, so that I could run exactly the same test in different configurations. I prefer to use blogbench for stability testing. fsx is a different beast, it reads/writes/truncates at random offsets - great tool for debugging mmap/truncate issues. Patch doesn't improve it in any way. > > ___ > freebsd-hackers@freebsd.org mailing list > http://lists.freebsd.org/mailman/listinfo/freebsd-hackers > To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org" ___ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
Re: [rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash
On 23.12.2010 23:46, Gleb Kurtsou wrote: > For testing I've used dbench with 16 processes on 1 Gb swap back md > device, UFS + SoftUpdates: > Old hash (Mb/s): 599.94 600.096 599.536 > SFH hash (Mb/s): 612.439 612.341 609.673 > > It's just ~1% improvement, but dbench is not a VFS metadata intensive > benchmark. Subjectively it feels faster accessing maildir mailboxes > with ~10.000 messages : ) Try blogbench if you need metadata-intensive operations, or even fsx. ___ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
Re: [rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash
On (24/12/2010 00:46), Gleb Kurtsou wrote:
> Hi,
>
> I've recently noticed that hash table use in nullfs was inefficient, 1/3
> to half of buckets remained unused. I've started investigating it
Nullfs patch I've forgotten to attach before.
It adds vfs.nullfs.buckets tunable to change number of hash table
buckets, vfs.nullfs.nodes sysctl to get number of active vnodes, and
increases default number of buckets from 16 to 32. Note that nullfs
nodes - are currently opened vnodes, so number is so low, one may want
to further increase it only if nullfs is heavily used (lots of null
mounts and active clients).
The patch requires SFH, but might be useful without it if
null_hash_mixptr() changed accordingly.
> further and came across SuperFastHash hashing function, SFH
> (SuperFastHash) has BSD license, used in WebKit and other open source
> projects. Detailed description and Comparision with FNV and Bob Jenkin's
> hash can be found here:
> http://www.azillionmonkeys.com/qed/hash.html
>
> In my tests SFH (SuperFastHash) was 1.3 to 4 times faster than FNV (it
> depends on size of data being hashed) e.g. performance of hashing 56
> bytes struct (Core i5 CPU, 2 cores + 2 hyperthreads):
> SFH -- 1339.79 MB/s
> FNV -- 330.27 MB/s
>
> I've prepared a patch to change FNV and hash32 with SFH in the tree.
>
> For testing I've used dbench with 16 processes on 1 Gb swap back md
> device, UFS + SoftUpdates:
> Old hash (Mb/s): 599.94 600.096 599.536
> SFH hash (Mb/s): 612.439 612.341 609.673
>
> It's just ~1% improvement, but dbench is not a VFS metadata intensive
> benchmark. Subjectively it feels faster accessing maildir mailboxes
> with ~10.000 messages : )
>
> I'd also wish hash32 (often called Bernstein hash) to be replaced with
> better function (it might be FNV if not SFH). Hash32 is inappropriate
> for binary data that results in poor distribution.
>
> Thanks,
> Gleb.
commit dd778e797cbfd821fc43ff74a8d5681ed2b93da1
Author: Gleb Kurtsou
Date: Thu Dec 16 08:13:58 2010 +0200
nullfs: Use SFH. Add sysctls to control hash table size
Add vfs.nullfs sysctls and tunable to change number hash table buckets
Increase default number of buckets to 32 (was 16)
diff --git a/sys/fs/nullfs/null_subr.c b/sys/fs/nullfs/null_subr.c
index 5717a01..2acd85b 100644
--- a/sys/fs/nullfs/null_subr.c
+++ b/sys/fs/nullfs/null_subr.c
@@ -36,18 +36,21 @@
#include
#include
+#include
#include
#include
#include
#include
#include
#include
+#include
#include
#include
-#define LOG2_SIZEVNODE 8 /* log2(sizeof struct vnode) */
-#defineNNULLNODECACHE 16
+#defineNULL_BUCKETS_MIN16
+#defineNULL_BUCKETS_DEFAULT32
+#defineNULL_BUCKETS_TUNABLE"vfs.nullfs.buckets"
/*
* Null layer cache:
@@ -58,7 +61,7 @@
*/
#defineNULL_NHASH(vp) \
- (&null_node_hashtbl[(((uintptr_t)vp)>>LOG2_SIZEVNODE) & null_node_hash])
+ (&null_node_hashtbl[null_hash_mixptr(vp) & null_node_hash])
static LIST_HEAD(null_node_hashhead, null_node) *null_node_hashtbl;
static u_long null_node_hash;
@@ -70,6 +73,15 @@ MALLOC_DEFINE(M_NULLFSNODE, "nullfs_node", "NULLFS vnode
private part");
static struct vnode * null_hashget(struct mount *, struct vnode *);
static struct vnode * null_hashins(struct mount *, struct null_node *);
+static u_long null_nodes;
+static u_long null_buckets = NULL_BUCKETS_DEFAULT;
+
+SYSCTL_NODE(_vfs, OID_AUTO, nullfs, CTLFLAG_RW, 0, "null file system");
+SYSCTL_ULONG(_vfs_nullfs, OID_AUTO, nodes, CTLFLAG_RD, &null_nodes, 0,
+"Allocated nodes");
+SYSCTL_ULONG(_vfs_nullfs, OID_AUTO, buckets, CTLFLAG_RD, &null_buckets, 0,
+"Allocated node hash table buckets");
+
/*
* Initialise cache headers
*/
@@ -77,10 +89,15 @@ int
nullfs_init(vfsp)
struct vfsconf *vfsp;
{
-
NULLFSDEBUG("nullfs_init\n"); /* printed during system boot */
- null_node_hashtbl = hashinit(NNULLNODECACHE, M_NULLFSHASH,
&null_node_hash);
+ TUNABLE_ULONG_FETCH(NULL_BUCKETS_TUNABLE, &null_buckets);
+ if (null_buckets < NULL_BUCKETS_MIN)
+ null_buckets = NULL_BUCKETS_MIN;
+ else if (null_buckets > desiredvnodes)
+ null_buckets = NULL_BUCKETS_DEFAULT;
+ null_node_hashtbl = hashinit(null_buckets, M_NULLFSHASH,
&null_node_hash);
mtx_init(&null_hashmtx, "nullhs", NULL, MTX_DEF);
+ null_nodes = 0;
return (0);
}
@@ -94,6 +111,12 @@ nullfs_uninit(vfsp)
return (0);
}
+static __inline uint32_t
+null_hash_mixptr(void *ptr)
+{
+ return (hash_sfh_buf(&ptr, sizeof(ptr), 33554467UL));
+}
+
/*
* Return a VREF'ed alias for lower vnode if already exists, else 0.
* Lower vnode should be locked on entry and will be left locked on exit.
@@ -164,6 +187,7 @@ null_hashins(mp, xp)
}
}
LIST_INSERT_HEAD(hd, xp, null_hash);
+ null_nodes++;
mtx_unlock(&null_hashmtx);
[rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash
Hi,
I've recently noticed that hash table use in nullfs was inefficient, 1/3
to half of buckets remained unused. I've started investigating it
further and came across SuperFastHash hashing function, SFH
(SuperFastHash) has BSD license, used in WebKit and other open source
projects. Detailed description and Comparision with FNV and Bob Jenkin's
hash can be found here:
http://www.azillionmonkeys.com/qed/hash.html
In my tests SFH (SuperFastHash) was 1.3 to 4 times faster than FNV (it
depends on size of data being hashed) e.g. performance of hashing 56
bytes struct (Core i5 CPU, 2 cores + 2 hyperthreads):
SFH -- 1339.79 MB/s
FNV -- 330.27 MB/s
I've prepared a patch to change FNV and hash32 with SFH in the tree.
For testing I've used dbench with 16 processes on 1 Gb swap back md
device, UFS + SoftUpdates:
Old hash (Mb/s): 599.94 600.096 599.536
SFH hash (Mb/s): 612.439 612.341 609.673
It's just ~1% improvement, but dbench is not a VFS metadata intensive
benchmark. Subjectively it feels faster accessing maildir mailboxes
with ~10.000 messages : )
I'd also wish hash32 (often called Bernstein hash) to be replaced with
better function (it might be FNV if not SFH). Hash32 is inappropriate
for binary data that results in poor distribution.
Thanks,
Gleb.
commit 6e19401826b6769fa95b1e4f9e561dec7101082b
Author: Gleb Kurtsou
Date: Thu Dec 16 08:05:14 2010 +0200
Import Paul Hsieh's SuperFastHash.
Replace FNV and Bernstein hash uses with SFH.
In most cases Bernstein is simply inappropriate choice.
diff --git a/lib/libkvm/kvm_minidump_amd64.c b/lib/libkvm/kvm_minidump_amd64.c
index 15630b1..7c9c4dd 100644
--- a/lib/libkvm/kvm_minidump_amd64.c
+++ b/lib/libkvm/kvm_minidump_amd64.c
@@ -35,7 +35,7 @@ __FBSDID("$FreeBSD$");
#include
#include
#include
-#include
+#include
#include
#include
#include
@@ -74,26 +74,26 @@ static void
hpt_insert(kvm_t *kd, vm_paddr_t pa, int64_t off)
{
struct hpte *hpte;
- uint32_t fnv = FNV1_32_INIT;
+ uint32_t hash;
- fnv = fnv_32_buf(&pa, sizeof(pa), fnv);
- fnv &= (HPT_SIZE - 1);
+ hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa));
+ hash &= (HPT_SIZE - 1);
hpte = malloc(sizeof(*hpte));
hpte->pa = pa;
hpte->off = off;
- hpte->next = kd->vmst->hpt_head[fnv];
- kd->vmst->hpt_head[fnv] = hpte;
+ hpte->next = kd->vmst->hpt_head[hash];
+ kd->vmst->hpt_head[hash] = hpte;
}
static int64_t
hpt_find(kvm_t *kd, vm_paddr_t pa)
{
struct hpte *hpte;
- uint32_t fnv = FNV1_32_INIT;
+ uint32_t hash;
- fnv = fnv_32_buf(&pa, sizeof(pa), fnv);
- fnv &= (HPT_SIZE - 1);
- for (hpte = kd->vmst->hpt_head[fnv]; hpte != NULL; hpte = hpte->next) {
+ hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa));
+ hash &= (HPT_SIZE - 1);
+ for (hpte = kd->vmst->hpt_head[hash]; hpte != NULL; hpte = hpte->next) {
if (pa == hpte->pa)
return (hpte->off);
}
diff --git a/lib/libkvm/kvm_minidump_arm.c b/lib/libkvm/kvm_minidump_arm.c
index d48c1bc..f42f4ca 100644
--- a/lib/libkvm/kvm_minidump_arm.c
+++ b/lib/libkvm/kvm_minidump_arm.c
@@ -38,7 +38,7 @@ __FBSDID("$FreeBSD$");
#include
#include
#include
-#include
+#include
#include
#include
#include
@@ -77,26 +77,26 @@ static void
hpt_insert(kvm_t *kd, uint64_t pa, int64_t off)
{
struct hpte *hpte;
- uint32_t fnv = FNV1_32_INIT;
+ uint32_t hash;
- fnv = fnv_32_buf(&pa, sizeof(pa), fnv);
- fnv &= (HPT_SIZE - 1);
+ hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa));
+ hash &= (HPT_SIZE - 1);
hpte = malloc(sizeof(*hpte));
hpte->pa = pa;
hpte->off = off;
- hpte->next = kd->vmst->hpt_head[fnv];
- kd->vmst->hpt_head[fnv] = hpte;
+ hpte->next = kd->vmst->hpt_head[hash];
+ kd->vmst->hpt_head[hash] = hpte;
}
static int64_t
hpt_find(kvm_t *kd, uint64_t pa)
{
struct hpte *hpte;
- uint32_t fnv = FNV1_32_INIT;
+ uint32_t hash;
- fnv = fnv_32_buf(&pa, sizeof(pa), fnv);
- fnv &= (HPT_SIZE - 1);
- for (hpte = kd->vmst->hpt_head[fnv]; hpte != NULL; hpte = hpte->next)
+ hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa));
+ hash &= (HPT_SIZE - 1);
+ for (hpte = kd->vmst->hpt_head[hash]; hpte != NULL; hpte = hpte->next)
if (pa == hpte->pa)
return (hpte->off);
diff --git a/lib/libkvm/kvm_minidump_i386.c b/lib/libkvm/kvm_minidump_i386.c
index 0d31705..343d70e 100644
--- a/lib/libkvm/kvm_minidump_i386.c
+++ b/lib/libkvm/kvm_minidump_i386.c
@@ -35,7 +35,7 @@ __FBSDID("$FreeBSD$");
#include
#include
#include
-#include
+#include
#include
#include
#include
@@ -76,26 +76,26 @@ static void
hpt_insert(kvm_t *kd, uint64_t pa, int64_t off)
{
struct hpte *hpte;
- uint32_t fnv = FNV1_32_INIT;
+ uint32_t hash;
- fnv =
