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

[Chuck Lever <cel@citi.umich.edu>]

[-- Attachment #1: Type: text/plain, Size: 1352 bytes --]

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.

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

[-- Attachment #2: cel.vcf --]
[-- Type: text/x-vcard, Size: 439 bytes --]

begin:vcard
fn:Chuck Lever
n:Lever;Charles
org:Network Appliance, Incorporated;Linux NFS Client Development
adr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA
email;internet:cel@citi.umich.edu
title:Member of Technical Staff
tel;work:+1 734 763 4415
tel;fax:+1 734 763 4434
tel;home:+1 734 668 1089
x-mozilla-html:FALSE
url:http://www.monkey.org/~cel/
version:2.1
end:vcard