From: Chuck Lever Date: Wed, 14 Sep 2005 22:28:09 GMT Subject: Re: [PATCH 21/22] teach the merge algorithm about cache iterators Message-ID: <4328A3F9.1010506@citi.umich.edu> In-Reply-To: Daniel Barkalow wrote: > 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