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

Dave Chinner
2009-11-12T23:46:30Z

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