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

From: Chuck Lever <cel@citi.umich.edu>
Date: Sep 14, 2005, 22:28 UTC
Message-ID: <4328A3F9.1010506@citi.umich.edu>
In-Reply-To: <Pine.LNX.4.63.0509141622340.23242@iabervon.org>

Daniel Barkalow wrote:

Show 8 quoted lines

> On Wed, 14 Sep 2005, Chuck Lever wrote:
>>[ i'm not sure why you think insert would be O(n). ]
> 
> 
> You need to find the correct location to insert in the sorted list, and 
> the hash table won't help you, because it doesn't have the new name. 
> Remember that the cursors need to go through the index in order, so the 
> list has to stay sorted.

oh, i see. the hash table won't help cache_find_name find an insertion point quickly if the name isn't already in the cache.

in fact, this will impact the other places that need an insertion point, such as ls-files and merge-index, as well as your new merge algorithm (which inserts all merged entries into the active cache one at a time via add_cache_entry).

considering that add_cache_entry can do a cache lookup several times, i think we need the "not found, returning insertion point" case to be fast too.

back to the drawring board.

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