Date: Fri, 24 Dec 2010 10:44:37 +0200 From: Gleb Kurtsou <gleb.kurtsou@gmail.com> To: freebsd-hackers@freebsd.org Subject: Re: [rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash Message-ID: <20101224084437.GA11619@tops> In-Reply-To: <20101223224619.GA21984@tops> References: <20101223224619.GA21984@tops>
next in thread | previous in thread | raw e-mail | index | archive | help
--GvXjxJ+pjyke8COw Content-Type: text/plain; charset=utf-8 Content-Disposition: inline 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. --GvXjxJ+pjyke8COw Content-Type: text/plain; charset=utf-8 Content-Disposition: attachment; filename="nullfs-sfh.patch.txt" commit dd778e797cbfd821fc43ff74a8d5681ed2b93da1 Author: Gleb Kurtsou <gleb.kurtsou@gmail.com> 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 <sys/param.h> #include <sys/systm.h> +#include <sys/hash_sfh.h> #include <sys/kernel.h> #include <sys/lock.h> #include <sys/mutex.h> #include <sys/malloc.h> #include <sys/mount.h> #include <sys/proc.h> +#include <sys/sysctl.h> #include <sys/vnode.h> #include <fs/nullfs/null.h> -#define LOG2_SIZEVNODE 8 /* log2(sizeof struct vnode) */ -#define NNULLNODECACHE 16 +#define NULL_BUCKETS_MIN 16 +#define NULL_BUCKETS_DEFAULT 32 +#define NULL_BUCKETS_TUNABLE "vfs.nullfs.buckets" /* * Null layer cache: @@ -58,7 +61,7 @@ */ #define NULL_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); return (NULLVP); } @@ -264,6 +288,7 @@ null_hashrem(xp) mtx_lock(&null_hashmtx); LIST_REMOVE(xp, null_hash); + null_nodes--; mtx_unlock(&null_hashmtx); } --GvXjxJ+pjyke8COw--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20101224084437.GA11619>