Re: [PATCH 21/22] teach the merge algorithm about cache iterators

From: Daniel Barkalow <barkalow@iabervon.org>
Date: Sep 14, 2005, 16:41 UTC
Message-ID: <Pine.LNX.4.63.0509141214490.23242@iabervon.org>
In-Reply-To: <43284368.8010004@citi.umich.edu>

On Wed, 14 Sep 2005, Chuck Lever wrote:

Show 23 quoted lines

> Daniel Barkalow wrote:
> > On Mon, 12 Sep 2005, Chuck Lever wrote:
> > 
> > 
> > >For now, we simply replace indpos with a cache cursor.  Likely more
> > >changes will be needed after we successfully replace the cache array
> > >with an abstract data type.
> > 
> > 
> > The right order is probably to add the concept of a cache that isn't the one
> > that normal functions deal with, have read_cache_unmerged return such a
> > thing, call cc_init with that, and rip out all of the removal and position
> > adjustment code. Then read_tree won't care at all about the internal
> > structure of the cache type, and it can be replaced without any problem.
> 
> ok, i've done this.  read_cache_unmerged now reads into a separate cache, and
> read-tree.c does the merge by moving the appropriate cache entries into the
> active cache.
> 
> the linked list prototype is done, and works correctly.  this validates the
> new cache cursor API.  unfortunately because finding a name is now O(n), many
> things are slower than before (but i expected this would be the case for
> lists).

The really exciting thing to do would be to have different programs use different implementations, by way of linker magic.

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.)

Another thing to try would be the original dynamic table implementation, plus a hashtable for name lookups, generated the first time a lookup is attempted (since some programs don't do any lookups by name). This has the advantage of skipping the O(n) startup.

	-Daniel
*This .sig left intentionally blank*