From: Daniel Barkalow <barkalow@iabervon.org>
Date: Wed, 14 Sep 2005 20:40:28 GMT
Subject: Re: [PATCH 21/22] teach the merge algorithm about cache iterators
Message-ID: <Pine.LNX.4.63.0509141622340.23242@iabervon.org>
In-Reply-To: <43287ECB.8090308@citi.umich.edu>

On Wed, 14 Sep 2005, Chuck Lever wrote:

> Daniel Barkalow wrote:
> > The really exciting thing to do would be to have different programs use
> > different implementations, by way of linker magic.
> 
> yes, i've been considering that, but i'm not sure it is really worth the
> effort.  see below -- the right data structure should be good for just about
> any git workload.
> 
> > My guess for the ideal is to have a linked list with a hashtable for finding
> > entries by looking up names, because we don't look things up by index. This
> > combination gives O(1) in-order iteration, O(1) lookup by name, O(1) append,
> > O(n) insert, and O(1) remove. This means that git-update-cache --add would
> > be slow, but everything else would be fast. (Except, of course, for the
> > overhead of actually reading and writing the index file, rather than mmaping
> > it.)
> 
> [ i'm not sure why you think insert would be O(n). ]

You need to find the correct location to insert in the sorted list, and 
the hash table won't help you, because it doesn't have the new name. 
Remember that the cursors need to go through the index in order, so the 
list has to stay sorted.

> keeping the linked list for O(1) next/prev and delete, and augmenting it with
> a hash table to allow O(m/n) insert and find would be ideal.  with a fairly
> large hash table, we do better than a tree for any reasonably sized repository
> i can imagine.
> 
> and, i believe simply adding a hash table to my list implementation will be
> easy, and simpler overall than a tree implementation.  famous last words.

I've written a nice hash table which should work well, if you want to make 
the coding style suitable.

> mmapping the index file is still OK.  i haven't changed the cache_entry
> structure at all.

Oh, right, I forgot that the orgnaizational structure isn't the array of 
structs, but an array of pointers.

	-Daniel
*This .sig left intentionally blank*