Re: [PATCH v9 3/3] read-cache: speed up add_index_entry during checkout

[Jeff Hostetler <git@jeffhostetler.com>]

On 4/11/2017 11:12 PM, Junio C Hamano wrote:
> git@jeffhostetler.com writes:
>
>> From: Jeff Hostetler <jeffhost@microsoft.com>
>>
>> Teach add_index_entry_with_check() and has_dir_name()
>> to see if the path of the new item is greater than the
>> last path in the index array before attempting to search
>> for it.
>>
>> During checkout, merge_working_tree() populates the new
>> index in sorted order, so this change will save at least 2
>> binary lookups per file.
>
> Smart and simple.
>
>> diff --git a/read-cache.c b/read-cache.c
>> index 97f13a1..a8ef823 100644
>> --- a/read-cache.c
>> +++ b/read-cache.c
>> @@ -918,9 +918,24 @@ static int has_dir_name(struct index_state *istate,
>>  	int stage = ce_stage(ce);
>>  	const char *name = ce->name;
>>  	const char *slash = name + ce_namelen(ce);
>> +	size_t len_eq_last;
>> +	int cmp_last = 0;
>> +
>> +	if (istate->cache_nr > 0) {
>> +		/*
>> +		 * Compare the entry's full path with the last path in the index.
>> +		 * If it sorts AFTER the last entry in the index and they have no
>> +		 * common prefix, then there cannot be any F/D name conflicts.
>> +		 */
>> +		cmp_last = strcmp_offset(name,
>> +			istate->cache[istate->cache_nr-1]->name,
>
> Style?  "istate->cache[istate->cache_nr - 1]->name"
>
>> +			&len_eq_last);
>> +		if (cmp_last > 0 && len_eq_last == 0)
>> +			return retval;
>> +	}
>
> Let me follow the logic aloud.  Say the last entry in the cache is
> "x/y".  If we came here with ce->name == "x", we need to worry about
> nuking the existing entry "x/y".  But if we have "zoo", that cannot
> possibly overlap and we can safely return 0.
>
> That sounds correct, except that it might be playing overly safe.
> If we came here with "xx", we still are safe, but len_eq_last would
> be non-zero.  Probably it is not worth the extra complexity to catch
> it here (rather than letting the loop below to handle it).
>
>>  	for (;;) {
>> -		int len;
>> +		size_t len;
>>
>>  		for (;;) {
>>  			if (*--slash == '/')
>> @@ -930,6 +945,24 @@ static int has_dir_name(struct index_state *istate,
>>  		}
>>  		len = slash - name;
>
> Mental note: cmp_last may be 0, >0 or <0 at this point in the very
> first iteration of the loop.  It is not updated in the loop.  The
> variable len_eq_last are used to carry the information about the
> last entry we learned at the beginning of this function---the new
> special case happens only when the path we are adding sorts later
> than the last existing entry (i.e. cmp_last > 0).
>
>> +		if (cmp_last > 0) {
>> +			/*
>> +			 * If this part of the directory prefix (including the trailing
>> +			 * slash) already appears in the path of the last entry in the
>> +			 * index, then we cannot also have a file with this prefix (or
>> +			 * any parent directory prefix).
>> +			 */
>> +			if (len+1 <= len_eq_last)
>
> Style?  "len + 1".
>
>> +				return retval;
>> +			/*
>> +			 * If this part of the directory prefix (excluding the trailing
>> +			 * slash) is longer than the known equal portions, then this part
>> +			 * of the prefix cannot collide with a file.  Go on to the parent.
>> +			 */
>> +			if (len > len_eq_last)
>> +				continue;
>
> Hmph, is the reasoning used in the two conditionals above sound?
> Does this work correctly even when the last existing entry in the
> cache is marked with CE_REMOVE?

I'll double check my math here.  I also want to think about
the "too conservative" comment above.

WRT if the last entry is CE_REMOVE, I think we are still OK
because we are asking if the given ce is strictly greater than
the last entry so that we can append it rather than searching
for a collision or insertion point.

Thanks,
Jeff