From: Chuck Lever Date: Wed, 14 Sep 2005 19:49:31 GMT Subject: Re: [PATCH 21/22] teach the merge algorithm about cache iterators Message-ID: <43287ECB.8090308@citi.umich.edu> In-Reply-To: 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. 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