From: Michael Haggerty Date: Tue, 22 May 2012 13:35:22 GMT Subject: Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2) Message-ID: <4FBB961A.2030806@alum.mit.edu> In-Reply-To: On 05/22/2012 02:18 PM, Nguyen Thai Ngoc Duy wrote: > On Tue, May 22, 2012 at 12:45 AM, Jeff King wrote: >> The rails/rails network repository at GitHub (i.e., a master repo with >> all of the objects and refs for all of the forks) has about 400K refs, >> and has been the usual impetus for me finding and fixing these sorts of >> quadratic problems. > > Off topic and pure speculation. With 400k refs, each one 20 byte in > length, the pathname part only can take 7MB. Perhaps packed-refs > should learn prefix compressing too, like index v4, to reduce size > (and hopefully improve startup speed). Compressing refs/heads/ and > refs/tags/ only could gain quite a bit already. I considered this idea but put it off for now for the reasons explained in the docstring for struct ref_entry in refs.c: * Please note that the name field contains the fully-qualified * reference (or subdirectory) name. Space could be saved by only * storing the relative names. But that would require the full names * to be generated on the fly when iterating in do_for_each_ref(), and * would break callback functions, who have always been able to assume * that the name strings that they are passed will not be freed during * the iteration. Thus, all of the callers of the for_each_ref functions would have to be audited (and perhaps adjusted) before such a change could be implemented. Michael -- Michael Haggerty mhagger@alum.mit.edu http://softwareswirl.blogspot.com/