Re: [PATCH 3/3] receive-pack: eliminate duplicate .have refs

[Jeff King <peff@peff.net>]

On Thu, May 19, 2011 at 08:06:20PM -0700, Junio C Hamano wrote:

> At first I thought you are going to insert the object names into a sorted
> list and handle dups while doing so, but it makes a lot more sense to
> append first and then sort at the end, and skip the dups while scanning,
> which is what you did.

I considered doing that, but I was worried that the constant
memmove()ing to insert into the sorted array would be inefficient.  As
it is, this uses a little more memory than necessary since we store all
the duplicates temporarily in memory (but we are not talking about a
lot, and I'm pretty sure they are all stored as a linked list elsewhere,
anyway, so it's not a huge deal).

The "right" data structure would be something like a tree or a hash. But
our hash is so painful to use for simple things like this (you have to
handle collision and creation of a linked list yourself!), that I just
went with the sorted list.

-Peff