xfs
[Top] [All Lists]

Re: [PATCH 06/14] repair: use a btree instead of a radix tree for thepre

To: Christoph Hellwig <hch@xxxxxxxxxxxxx>
Subject: Re: [PATCH 06/14] repair: use a btree instead of a radix tree for theprefetch queue
From: Dave Chinner <david@xxxxxxxxxxxxx>
Date: Fri, 13 Nov 2009 10:46:43 +1100
Cc: Alex Elder <aelder@xxxxxxx>, Barry Naujok <bnaujok@xxxxxxxxxxxxxxx>, xfs@xxxxxxxxxxx
In-reply-to: <20091112100408.GA25058@xxxxxxxxxxxxx>
References: <20090902175840.740632507@xxxxxxxxxxxxxxxxxxxxxx> <1AB9A794DBDDF54A8A81BE2296F7BDFE83ADEB@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> <20091112100408.GA25058@xxxxxxxxxxxxx>
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@xxxxxxxxxxxxx

<Prev in Thread] Current Thread [Next in Thread>