Re: [PATCH 0/2] A new merge algorithm, take 3

From: Linus Torvalds <torvalds@osdl.org>
Date: Sep 8, 2005, 20:59 UTC
Message-ID: <Pine.LNX.4.58.0509081357480.3039@g5.osdl.org>
In-Reply-To: <432089D8.4060507@citi.umich.edu>

On Thu, 8 Sep 2005, Chuck Lever wrote:

Show 14 quoted lines

> > 
> > Btw, in the sparse project, we have this really smart "pointer list" data
> > structure, which is extremely space- and time-efficient. It ends up
> > _looking_ like a linked list, but it batches things up in hunks of 29
> > entries (29 pointers plus overhead gives you blocks of 32 longwords, which
> > is the allocation size) and thus gives basically a cache-friendly
> > doubly-linked list. It knows how to do insertions, traversals etc very 
> > efficiently.
> > 
> > Any interest?
> 
> i'm not married to splay trees.  i think we should explore several 
> different data structures before picking one, and this one sounds 
> reasonable to try.

Actually, I just realized that one of the issues is just plain looking up a name (ie "pos = cache_name_pos(..)", and the sparse list don't make that very efficient unless you have a good starting point.

So a splay tree is probably more appropriate.

			Linus