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

[Michael Haggerty <mhagger@xxxxxxxxxxxx>]

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@xxxxxxxxxxxx
http://softwareswirl.blogspot.com/
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html