From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Mon, 21 May 2012 08:13:33 GMT
Subject: remove_duplicates() in builtin/fetch-pack.c is O(N^2)
Message-ID: <4FB9F92D.8000305@alum.mit.edu>

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.

I know that 100k heads is kindof absurd.  Perhaps handling this many 
heads is unrealistic for other reasons.  But I vaguely recall numbers 
like this being mentioned on the mailing list.

It would be pretty trivial to reduce the work to O(N) by using a hash 
set to keep track of the references that have already been seen.

I don't plan to work on this, but I thought I would point it out in case 
it is causing somebody pain.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/