Re: [PATCH 1/3] sha1_name: Create perf test for find_unique_abbrev()

From: Junio C Hamano <gitster@pobox.com>
Date: Sep 19, 2017, 00:51 UTC
Message-ID: <xmqqr2v3se7m.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <960c73e2-6909-6894-a9ab-a191426aeda9@gmail.com>

Derrick Stolee <stolee@gmail.com> writes:

Show 16 quoted lines

>> But I do not think we want this "clever" optimization that involves
>> 'n' in the first place.
>>>> +	while (count++ < 100000) {
>>> +		for (i = 0; i < n; i++)
>>> +			((unsigned int*)oid.hash)[i] = hash_base;
>>
>> Does it make sense to assume that uint is always 4-byte (so this
>> code won't work if it is 8-byte on your platform) and doing this is
>> faster than using platform-optimized memcpy()?
>
> I'm not sure what you mean by using memcpy to improve this, because
> it would require calling memcpy in the inner loop, such as
>
> 	for (i = 0; i < n; i++)
> 		memcpy(oid.hash + i * sizeof(unsigned), &hash_base,
> 		       sizeof(unsigned));

Sorry, I left it without saying as I thought it was obvious, but what I meant was to use a whole "struct oid", not just a single unsigned (repeated), as the hash that is tested. If you have an array of object names you use in the test, then

	for (count = 0; count < limit; count++) {
		hashcpy(&oid.hash, &samples[count]);

		... do the probing ...
	}

> First, this doesn't just measure the time it takes to determine non-
> existence,

Sorry, my phrasing was indeed misleading. I know the time we spend to see if we have or do not have the object is the largest cycle spender in these codepaths (and even if it were, I do not think that is what you are trying to optimize in these patches anyway).

But if I recall correctly, the way we come up with the unique abbreviation for an object that exists and an object that does not exist are different? And because most of the time (think: "git log -p" output) we would be finding abbreviation for objects that we do have, benchmarking and tweaking the code that comes up with an object that does not exist is not optimizing for the right case.

Back when I wrote that initial response, I didn't check how different the code was between the two cases, but now I did. It seems that in both cases we start from the shortest-allowed length and then extend the same way, and the only difference between these two cases is that we return immediately when our candidate name is long enough not to match any existing object when the full name refers to an object we do not have, while we return only when disambiguity is resolved. I _think_ these amount to the same computation (i.e. when an object with the full name we have exists, the amount of computation we need to come up with its unique abbreviation is the same as the computation we need to find the unique abbreviation for the same name in another repository that has identical set of objects, minus that single object), so from that point of view, throwing random hashes, most of which would not name any existing object, and measuring how much time it takes to run get_short_oid() to compute the minimum length of the unique prefix should be sufficient.

Thanks.