Re: [Toy PATCH] Avoid spilling collided entries in object hash table to the next slots

From: Junio C Hamano <gitster@pobox.com>
Date: Mar 29, 2013, 17:15 UTC
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.