From: Dave Chinner <david@fromorbit.com>
To: Christoph Hellwig <hch@infradead.org>
Cc: xfs@oss.sgi.com, Barry Naujok <bnaujok@optusnet.com.au>,
Alex Elder <aelder@sgi.com>
Subject: Re: [PATCH 06/14] repair: use a btree instead of a radix tree for theprefetch queue
Date: Fri, 13 Nov 2009 10:46:43 +1100 [thread overview]
Message-ID: <20091112234643.GJ25494@discord.disaster> (raw)
In-Reply-To: <20091112100408.GA25058@infradead.org>
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
_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs
next prev parent reply other threads:[~2009-11-12 23:46 UTC|newest]
Thread overview: 50+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-09-02 17:55 [PATCH 00/14] repair memory usage reductions Christoph Hellwig
2009-09-02 17:55 ` [PATCH 01/14] repair: merge scanfunc_bno and scanfunc_cnt Christoph Hellwig
2009-10-12 16:53 ` Eric Sandeen
2009-10-13 22:13 ` Christoph Hellwig
2009-10-13 23:36 ` Alex Elder
2009-09-02 17:55 ` [PATCH 02/14] repair: reduce byte swap operations in scanfunc_allocbt Christoph Hellwig
2009-10-12 17:18 ` Eric Sandeen
2009-10-13 23:37 ` [PATCH 02/14] repair: reduce byte swap operations inscanfunc_allocbt Alex Elder
2009-09-02 17:55 ` [PATCH 03/14] repair: kill B_IS_META flag Christoph Hellwig
2009-10-12 19:45 ` Eric Sandeen
2009-10-13 22:16 ` Christoph Hellwig
2009-10-13 22:19 ` Eric Sandeen
2009-10-13 23:38 ` Alex Elder
2009-09-02 17:55 ` [PATCH 04/14] repair: split up scanfunc_ino Christoph Hellwig
2009-10-12 20:06 ` Eric Sandeen
2009-10-13 22:19 ` Christoph Hellwig
2009-10-13 22:22 ` Eric Sandeen
2009-10-13 22:23 ` Christoph Hellwig
2009-09-02 17:55 ` [PATCH 05/14] repair: reduce byte swapping in scan_freelist Christoph Hellwig
2009-10-12 20:43 ` Eric Sandeen
2009-09-02 17:55 ` [PATCH 06/14] repair: use a btree instead of a radix tree for the prefetch queue Christoph Hellwig
2009-10-21 17:12 ` [PATCH 06/14] repair: use a btree instead of a radix tree for theprefetch queue Alex Elder
2009-11-12 10:04 ` Christoph Hellwig
2009-11-12 23:46 ` Dave Chinner [this message]
2009-09-02 17:55 ` [PATCH 07/14] repair: use single prefetch queue Christoph Hellwig
2009-10-21 17:48 ` Alex Elder
2009-11-12 10:09 ` Christoph Hellwig
2009-09-02 17:55 ` [PATCH 08/14] repair: clean up prefetch tracing Christoph Hellwig
2009-10-21 17:53 ` Alex Elder
2009-09-02 17:55 ` [PATCH 09/14] repair: track logical to physical block mapping more effeciently Christoph Hellwig
2009-10-21 19:06 ` [PATCH 09/14] repair: track logical to physical block mapping moreeffeciently Alex Elder
2009-11-12 10:18 ` Christoph Hellwig
2009-09-02 17:55 ` [PATCH 10/14] repair: cleanup helpers for tracking block usage Christoph Hellwig
2009-10-21 19:33 ` Alex Elder
2009-11-12 10:21 ` Christoph Hellwig
2009-09-02 17:55 ` [PATCH 11/14] repair: cleanup alloc/free/reset of the block usage tracking Christoph Hellwig
2009-10-21 20:22 ` [PATCH 11/14] repair: cleanup alloc/free/reset of the block usagetracking Alex Elder
2009-09-02 17:55 ` [PATCH 12/14] repair: switch block usage bitmap to a btree Christoph Hellwig
2009-10-22 16:22 ` Alex Elder
2009-11-12 10:25 ` Christoph Hellwig
2009-09-02 17:55 ` [PATCH 13/14] repair: optimize duplicate extent tracking Christoph Hellwig
2009-10-22 16:41 ` Alex Elder
2009-09-02 17:55 ` [PATCH 14/14] repair: add missing locking in scanfunc_bmap Christoph Hellwig
2009-10-22 16:42 ` Alex Elder
2009-09-03 20:49 ` [PATCH 00/14] repair memory usage reductions Geoffrey Wehrman
2009-09-04 2:57 ` Dave Chinner
2009-09-04 13:37 ` Geoffrey Wehrman
2009-09-04 14:51 ` Christoph Hellwig
2009-09-04 17:24 ` Michael Monnerie
2009-11-12 15:58 ` Christoph Hellwig
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20091112234643.GJ25494@discord.disaster \
--to=david@fromorbit.com \
--cc=aelder@sgi.com \
--cc=bnaujok@optusnet.com.au \
--cc=hch@infradead.org \
--cc=xfs@oss.sgi.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox