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

[Daniel Barkalow <barkalow@iabervon.org>]

On Wed, 14 Sep 2005, Chuck Lever wrote:

> 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*