Re: fast-import's hash table is slow

["René Scharfe" <l.s.r@web.de>]

Am 03.04.20 um 14:12 schrieb Jeff King:
> On Thu, Apr 02, 2020 at 08:40:35PM +0200, René Scharfe wrote:
>
>>>  struct object_entry {
>>>  	struct pack_idx_entry idx;
>>> -	struct object_entry *next;
>>> +	struct hashmap_entry ent;
>>
>> That uses 16 bytes more memory per entry on x64 than khash would.
>> That's 256MB for 2^24 objects -- not ideal, but bearable, I guess.
>
> Isn't it 8? We're dropping the old pointer and replacing it with the
> "next" pointer in hashmap_entry, plus our 4-byte hash code (which likely
> gets padded to 8).

That's right, so the difference to your khash version is 16, as the
latter removes the pointer without any replacement.

See https://www.godbolt.org/z/xs6CLL for a comparison.

>>> +static int object_entry_hashcmp(const void *map_data,
>>> +				const struct hashmap_entry *eptr,
>>> +				const struct hashmap_entry *entry_or_key,
>>> +				const void *keydata)
>>> +{
>>> +	const struct object_id *oid = keydata;
>>> +	const struct object_entry *e1, *e2;
>>> +
>>> +	e1 = container_of(eptr, const struct object_entry, ent);
>>
>> That's nicer that the pointer alchemy in the khash conversion for sure.
>>
>> But why const?  Can const change the layout of a structure?  Scary.
>
> No, I don't think it can. I mostly copied the "const" from the other
> container_of() hashmap sites. I don't think it matters in practice,
> because we're assigning the result to a const pointer anyway. But it
> seems a little cleaner not to momentarily cast away the constness even
> inside the macro.

Makes sense.  I disregarded the final cast in container_of when I
wrote the above.  Silly me.

René