Subject: remove_duplicates() in builtin/fetch-pack.c is O(N^2)

From: Michael Haggerty <[email-masked]>
Date: Mon, 21 May 2012 10:13:33 +0200

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
[email-masked]
http://softwareswirl.blogspot.com/