From: demerphq <demerphq@gmail.com>
Date: Mon, 21 May 2012 09:42:06 GMT
Subject: Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)
Message-ID: <CANgJU+WwA0FfwVFWO23o0wLbpXNS+RXwwx=VKZ_J3e57r1pBsQ@mail.gmail.com>
In-Reply-To: <4FB9F92D.8000305@alum.mit.edu>

On 21 May 2012 10:13, Michael Haggerty <mhagger@alum.mit.edu> wrote:
> I just noticed that the remove_duplicates() function in builtin/fetch-pack.c
> is O(N^2) in the number of heads.  Empirically, this function takes on the
> order of 25 seconds to process 100k references.

Does "heads" in this context include tags? Sorry if this is a stupid question.

Yves


-- 
perl -Mre=debug -e "/just|another|perl|hacker/"