Re: What's cooking in git.git (Oct 2013, #06; Fri, 25)

From: Vicent Martí <tanoku@gmail.com>
Date: Oct 28, 2013, 16:16 UTC
Message-ID: <CAFFjANSnuS6_+uAd43AayojJyK-wj2wMxQ6DBD6JyN=A7xh2_A@mail.gmail.com>
In-Reply-To: <xmqq61shgzvn.fsf@gitster.dls.corp.google.com>

On Mon, Oct 28, 2013 at 4:48 PM, Junio C Hamano <gitster@pobox.com> wrote:

Show 6 quoted lines

>> jk/pack-bitmap adds khash.h, which from a first glance looks like yet
>> another hash table implementation. I was just wondering if kb's new
>> hash tables can cover the need of pack-bitmap.c too so we can remove
>> khash.h later..
>
> Good thinking ;-).

We use the khash tables to map:

    - sha1 (const char *) to (void *)
    - sha1 (const char *) to int

The new `hashmap.c` covers the first case quite well (albeit slightly more verbosely than I'd like), but in the second case it doesn't quite work. Since the new hash needs to embed the "struct hashmap_entry" on all its values (to allow for separate chaining), having it map to `int` keys requires a struct like this:

    struct sha1_position {
        struct hashmap_entry {
            struct hashmap_entry *next;
            unsigned int hash;
        };
        int position;
    }

khash on the other hand is capable of storing the position values as part of the hash table itself (i.e. `int **buckets`), and saves us from thousands of bytes of allocations + indirection.

I am not sure whether the consistency of having a single hash map warrants the performance and memory hits when operating on the extended index.

Please advice.

luv, vmg