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

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

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