Re: What's cooking in git.git (topics)

From: David Kastrup <dak@gnu.org>
Date: Sep 27, 2007, 13:46 UTC
Message-ID: <868x6sgr1g.fsf@lola.quinscape.zz>
In-Reply-To: <20070927133056.GA29674@coredump.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 13 quoted lines

> On Thu, Sep 27, 2007 at 08:08:44AM +0200, David Kastrup wrote:
>
>> In itself, it does not look like there is all too much room for
>> optimization.  One can remove the temporary pointer "optimization" and
>> see whether this makes strength reduction possible for the compiler.
>> Making this an endless loop wrapped around a loop on bucket might also
>> help the compiler in that effect.
>
> I am considering reworking the data structure to be a hash table
> whose buckets never overflow. However, Junio indicated that he tried
> something similar at one point and was not successful. So we will
> see. I haven't had time to play with it yet, but I will post numbers
> when I do.

Linear probing is pretty efficient with regard to keeping memory access locality. With a reasonable table filling ratio (not more than something like 75%, for which it is necessary to know the maximum number of hashable entries in advance), there is no gain to be expected in either speed or even memory usage (the waste of 25% is offset by not needing space for link pointers) with escape lists. Linear probing hashes are quite hard to resize: if the maximum member count is _not_ to be guessed in advance, things might look different.

I don't have the time to look at the code right now, so I don't know whether resizing or unknown maximum size is a relevant factor.

-- 
David Kastrup