From owner-freebsd-hackers@FreeBSD.ORG Fri Dec 24 08:45:09 2010 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 97E84106567A for ; Fri, 24 Dec 2010 08:45:09 +0000 (UTC) (envelope-from gleb.kurtsou@gmail.com) Received: from mail-ew0-f54.google.com (mail-ew0-f54.google.com [209.85.215.54]) by mx1.freebsd.org (Postfix) with ESMTP id 324E38FC15 for ; Fri, 24 Dec 2010 08:45:07 +0000 (UTC) Received: by ewy24 with SMTP id 24so3642222ewy.13 for ; Fri, 24 Dec 2010 00:45:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:date:from:to:subject :message-id:references:mime-version:content-type:content-disposition :in-reply-to:user-agent; bh=ZALWCMiq4WOLL926U9gevj4qQfHRhjcYy9mmSvWEgNc=; b=LkXuRCHtkIVKMM634nkk+tU936XdyaKq+/CYHVziMYfQbC9DWDWMwnjQ7qx+inF/oS zoZN7fpOwco5ZZiU3aaY/eETo6Fsz6u8VEystm+FKsPyfOaAkGvwKi3dc7C4sL/jEzHN cvXuAPrSN+K34Dnupif/GuUH9uXc88c5QgAAM= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=date:from:to:subject:message-id:references:mime-version :content-type:content-disposition:in-reply-to:user-agent; b=u26A3G8M6G/keVN+E1beqyaWZhK+7oXOOQp/2WZIqYxQjawI6cSERl3rDyOCZnNjwW eMty0hyjHxzTOlSahxWHiYmKnqkizItTMANIZdY5k+tgBkGwSW39rzNXlOoB5tJcGT0B H6TzZlTmIV3I9JRe5stM6PH2oY77BJmE324k0= Received: by 10.14.119.129 with SMTP id n1mr5532055eeh.13.1293180306532; Fri, 24 Dec 2010 00:45:06 -0800 (PST) Received: from localhost ([212.98.186.134]) by mx.google.com with ESMTPS id t50sm6268017eeh.12.2010.12.24.00.45.05 (version=TLSv1/SSLv3 cipher=RC4-MD5); Fri, 24 Dec 2010 00:45:05 -0800 (PST) Date: Fri, 24 Dec 2010 10:44:37 +0200 From: Gleb Kurtsou To: freebsd-hackers@freebsd.org Message-ID: <20101224084437.GA11619@tops> References: <20101223224619.GA21984@tops> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="GvXjxJ+pjyke8COw" Content-Disposition: inline In-Reply-To: <20101223224619.GA21984@tops> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 24 Dec 2010 08:45:09 -0000 --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 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) */ -#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--