Date: Sat, 24 Feb 2007 06:09:37 +0100
From: Nick Piggin <npiggin@suse.de>
To: William Lee Irwin III <wli@holomorphy.com>
Cc: Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Subject: Re: [rfc][patch] dynamic resizing dentry hash using RCU
Message-ID: <20070224050937.GA16601@wotan.suse.de>
References: <20070223153743.GA26141@wotan.suse.de> <20070224042444.GU21484@holomorphy.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20070224042444.GU21484@holomorphy.com>
User-Agent: Mutt/1.5.9i
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1810
Lines: 35

On Fri, Feb 23, 2007 at 08:24:44PM -0800, William Lee Irwin III wrote:
> On Fri, Feb 23, 2007 at 04:37:43PM +0100, Nick Piggin wrote:
> > The dentry hash uses up 8MB for 1 million entries on my 4GB system is
> > one of the biggest wasters of memory for me. Because I rarely have
> > more than one or two hundred thousand dentries. And that's with
> > several kernel trees worth of entries. Most desktop and probably even
> > many types of servers will only use a fraction of that.
> > So I introduce a new method for resizing hash tables with RCU, and apply
> > that to the dentry hash.
> > The primitive heuristic is that the hash size is doubled when the number of
> > entries reaches 150% the hash size, and halved when the number is 50%.
> > It should also be able to shrink under memory pressure, and scale up as
> > large as we go.
> 
> You would be better served by a data structure different from a hashtable.

Possibly. Note that I wasn't intending to rewrite the dcache hash
specifically, but just demonstrate my lockless dynamic data structure
switch, and the dentry hash was the most obvious candidate.

But considering that it is lockless, and basically free in the fastpath
(ie. a single easily-predicted branch), then I'm better served by an
dynamically sized dynamic hash table than an inappropriately sized one.

Well, almost. The vmalloc issue is the downside, of course. But if I'm
on a NUMA that is doing vmalloc hashes anyway, then there is little
downside.

Out of curiosity, what better data structure do you have in mind for
the dentry hash?
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/