Date: Fri, 13 Nov 2009 10:46:43 +1100
From: Dave Chinner <david@fromorbit.com>
To: Christoph Hellwig <hch@infradead.org>
Cc: Alex Elder <aelder@sgi.com>, Barry Naujok <bnaujok@optusnet.com.au>,
        xfs@oss.sgi.com
Subject: Re: [PATCH 06/14] repair: use a btree instead of a radix tree for
	theprefetch queue
Message-ID: <20091112234643.GJ25494@discord.disaster>
References: <20090902175840.740632507@bombadil.infradead.org> <1AB9A794DBDDF54A8A81BE2296F7BDFE83ADEB@cf--amer001e--3.americas.sgi.com> <20091112100408.GA25058@infradead.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20091112100408.GA25058@infradead.org>
User-Agent: Mutt/1.5.18 (2008-05-17)

On Thu, Nov 12, 2009 at 05:04:08AM -0500, Christoph Hellwig wrote:
> On Wed, Oct 21, 2009 at 12:12:33PM -0500, Alex Elder wrote:
> > - Related to the previous one--it would be good to have
> >   a little info about why the value 7 was chosen as the
> >   number of keys per node.  Perhaps I just don't know
> >   enough of the history (or content of the upcoming
> >   patches).

I think I can answer this one:

> +/*
> + * Maximum number of keys per node.  Must be greater than 2 for the code
> + * to work.
> + */
> +#define BTREE_KEY_MAX		7
> +#define BTREE_KEY_MIN		(BTREE_KEY_MAX / 2)
> +
> +#define BTREE_PTR_MAX		(BTREE_KEY_MAX + 1)
> +
> +struct btree_node {
> +	unsigned long		num_keys;
> +	unsigned long		keys[BTREE_KEY_MAX];
> +	struct btree_node	*ptrs[BTREE_PTR_MAX];
> +};

BTREE_KEY_MAX = 7 results in a btree_node exactly filling
a 64 byte cacheline on 32 bit, and 2 cachelines on 64 bit.
Cacheline aligned and sized nodes minimises the number of cache
misses when traversing/searching the btree....

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com