Re: What's cooking in git.git (topics)

David Kastrup [off-list ref] writes:

Jeff King [off-list ref] writes:

quoted

On Wed, Sep 26, 2007 at 01:05:59PM -0700, Junio C Hamano wrote:

quoted

* jk/diff-rename (Tue Sep 25 15:29:42 2007 -0400) 1 commit
 + diffcore-rename: cache file deltas

Parked in 'next' for now but is 'master' material.

My tests after this patch show that spanhash_find is responsible for
a large portion of the processing time in large renames, so I am going
to look into speeding that up.

In itself, it does not look like there is all too much room for
optimization.  One can remove the temporary pointer "optimization" and
see whether this makes strength reduction possible for the compiler.
Making this an endless loop wrapped around a loop on bucket might also
help the compiler in that effect.

But there is really not all too much leeway, and it might be better
spent in the caller.  For example, the search will take something like
r/(1-r) iterations on average where r is the fill ratio of the hash
array.  So one would not want to, say, let r grow above 0.75 or
something like that.

Ok, here is some suggestion:

Here is the inner loop for this stuff:

	for (i = 0; i < ssz; i++) {
		struct spanhash *s = &(src_count->data[i]);
		struct spanhash *d;
		unsigned dst_cnt, src_cnt;
		if (!s->cnt)
			continue;
		src_cnt = s->cnt;
		d = spanhash_find(dst_count, s->hashval);
		dst_cnt = d ? d->cnt : 0;
		if (src_cnt < dst_cnt) {
			la += dst_cnt - src_cnt;
			sc += src_cnt;
		}
		else
			sc += dst_cnt;
	}

Now here is how one could optimize the data structures: The hash
structures are with linear probing, and we try to find any hash
matches from source to destination.  If we sort all hashes indexed to
a given first hash bucket by their full hash value, then one could
basically use passes similar to list merges for figuring the 1:1
relations.  That cuts down the O(l n) cost (where n is the number of
elements and l their average run length) to O(n).

Of course, making l close to 1 by keeping the hash utilization
reasonably low is much simpler.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum