Re: [PATCH] add b+tree library

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

On Sun, Jan 11, 2009 at 09:30:34AM +0100, Jörn Engel wrote:
> On Sun, 11 January 2009 00:57:20 +0100, Peter Zijlstra wrote:
> > 
> > B-tree's however have one thing over RB-trees, B-trees can be made
> > RCU-safe whereas RB-trees cannot be -- the only problem is that Joern's
> > doesn't do that.
> 
> And yours doesn't support multiple key sizes afaics.  I don't mind
> using your version as a basis, so long as my^Wboth requirements get
> fulfilled. ;)
> 
> Do you see a problem combining rcu with keys being an array of unsigned
> long?

There is a theory vs. practice issue here.  In theory, you could make any
dynamically allocated search structure RCU-searchable by copy-updating
the entire structure on each update.  In many cases, you only have to
replace a fairly small part.  In practice, the question is whether your
read-to-update ratio is large enough to make it a win.

The main potential issue with keys being an array of unsigned long is
that it is no longer possible to atomically rewrite a given key in place.
The usual ways to work around this are:

1.	Replace each key entry with a pointer to the array of unsigned
	longs, so that you can atomically rewrite the pointer.  The
	downside of this approach is the extra cache line accessed per
	key scanned.  The upside of this approach is that you might
	be able to share code with Peter's tree by using a comparison
	function (if NULL, just compare the entries directly) or some
	other similar trick.

2.	Place the array of unsigned longs directly in the structure, but
	copy-update the entire node rather than rewriting keys in place.
	This has better cache locality, but makes it more difficult to
	share code with the small-key variant.

There are probably other tricks as well.

							Thanx, Paul