Re: fast-import's hash table is slow

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

Am 31.03.20 um 21:14 schrieb René Scharfe:
> Am 31.03.20 um 11:45 schrieb Jeff King:
>> diff --git a/fast-import.c b/fast-import.c
>> index 202dda11a6..6ebac665a0 100644
>> --- a/fast-import.c
>> +++ b/fast-import.c
>> @@ -39,12 +39,25 @@
>>
>>  struct object_entry {
>>  	struct pack_idx_entry idx;
>> -	struct object_entry *next;
>>  	uint32_t type : TYPE_BITS,
>>  		pack_id : PACK_ID_BITS,
>>  		depth : DEPTH_BITS;
>>  };
>>
>> +static inline unsigned int object_entry_hash(struct object_entry *oe)
>> +{
>> +	return oidhash(&oe->idx.oid);
>> +}
>> +
>> +static inline int object_entry_equal(struct object_entry *a,
>> +				     struct object_entry *b)
>> +{
>> +	return oideq(&a->idx.oid, &b->idx.oid);
>> +}
>> +
>> +KHASH_INIT(object_entry_set, struct object_entry *, int, 0,
>> +	   object_entry_hash, object_entry_equal);
>> +
>>  struct object_entry_pool {
>>  	struct object_entry_pool *next_pool;
>>  	struct object_entry *next_free;
>> @@ -178,7 +191,7 @@ static off_t pack_size;
>>  /* Table of objects we've written. */
>>  static unsigned int object_entry_alloc = 5000;
>>  static struct object_entry_pool *blocks;
>> -static struct object_entry *object_table[1 << 16];
>> +static kh_object_entry_set_t object_table;
>>  static struct mark_set *marks;
>>  static const char *export_marks_file;
>>  static const char *import_marks_file;
>> @@ -455,44 +468,45 @@ static struct object_entry *new_object(struct object_id *oid)
>>
>>  static struct object_entry *find_object(struct object_id *oid)
>>  {
>> -	unsigned int h = oid->hash[0] << 8 | oid->hash[1];
>> -	struct object_entry *e;
>> -	for (e = object_table[h]; e; e = e->next)
>> -		if (oideq(oid, &e->idx.oid))
>> -			return e;
>> +	/*
>> +	 * this cast works because we only look at the oid part of the entry,
>> +	 * and it comes first in the struct
>> +	 */
>> +	khiter_t pos = kh_get_object_entry_set(&object_table,
>> +					       (struct object_entry *)oid);
>
> Dirty, but I can believe the comment.
>
>
>> +	if (pos != kh_end(&object_table))
>> +		return kh_key(&object_table, pos);
>>  	return NULL;
>>  }
>>
>>  static struct object_entry *insert_object(struct object_id *oid)
>>  {
>> -	unsigned int h = oid->hash[0] << 8 | oid->hash[1];
>> -	struct object_entry *e = object_table[h];
>> +	struct object_entry *e;
>> +	int was_empty;
>> +	khiter_t pos;
>>
>> -	while (e) {
>> -		if (oideq(oid, &e->idx.oid))
>> -			return e;
>> -		e = e->next;
>> -	}
>> +	pos = kh_put_object_entry_set(&object_table, (struct object_entry *)oid, &was_empty);
>
> Now this looks illegal.  khash is surely reading a full object_entry from oid,
> which only is a mere object_id, no?

No, it's a set of pointers, and khash only accesses the referenced objects
via the hash and comparison functions.

Storing the objects directly in the set and getting rid of new_object()
could improve performance due to reduced dereferencing overhead -- or
make it slower because more data has to be copied when the hashmap needs
to grow.  Worth a shot.  Later.

René