From: Linus Torvalds Date: Thu, 08 Sep 2005 20:59:54 GMT Subject: Re: [PATCH 0/2] A new merge algorithm, take 3 Message-ID: In-Reply-To: <432089D8.4060507@citi.umich.edu> On Thu, 8 Sep 2005, Chuck Lever wrote: > > > > 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