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

From: Jeff King <peff@peff.net>
Date: May 20, 2011, 07:42 UTC
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