From: Junio C Hamano <gitster@pobox.com>
Date: Fri, 29 Mar 2013 17:15:19 GMT
Subject: Re: [Toy PATCH] Avoid spilling collided entries in object hash table to the next slots
Message-ID: <7vd2uip1p4.fsf@alter.siamese.dyndns.org>
In-Reply-To: <1364568469-2250-1-git-send-email-pclouds@gmail.com>

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> If a position in object hash table is taken, we currently check out
> the next one. This could potentially create long object chains. We
> could create linked lists instead and leave the next slot alone.

In the current code, not just the logic in lookup_object(), but the
logic to enforce load factor when create_object() decides to call
grow_object_hash() and object enumeration implemented by
get_max_object_index() and get_indexed_object() are closely tied to
the open addressing scheme.  If you want to switch to any other
method (e.g. separate chaining) these need to be updated quite a
bit.

I do not see get_max_object_index() and get_indexed_object() updated
at all.  Do fsck, index-pack, name-rev and upload-pack still work?

This particular implementation that uses a fake "union" is a bit
ugly, but in general, it may be worth rethinking the object hash
implementation.  I vaguely recall trying cuckoo in the vicinity of
this code.