From: Jeff King <peff@peff.net>
Date: Fri, 20 May 2011 07:42:09 GMT
Subject: Re: [PATCH 3/3] receive-pack: eliminate duplicate .have refs
Message-ID: <20110520074209.GB3663@sigill.intra.peff.net>
In-Reply-To: <7vaaei5avn.fsf@alter.siamese.dyndns.org>

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