v2unpack-trees: avoid duplicate ODB lookups during checkout

> From: Jeff Hostetler <jeffhost@microsoft.com>
> 
> Teach traverse_trees_recursive() to not do redundant ODB
> lookups when both directories refer to the same OID.
> 
> In operations such as read-tree, checkout, and merge when
> the differences between the commits are relatively small,
> there will likely be many directories that have the same
> SHA-1.  In these cases we can avoid hitting the ODB multiple
> times for the same SHA-1.
> 
> This patch handles n=2 and n=3 cases and simply copies the
> data rather than repeating the fill_tree_descriptor().
> 
> ================
> On the Windows repo (500K trees, 3.1M files, 450MB index),
> this reduced the overall time by 0.75 seconds when cycling
> between 2 commits with a single file difference.
> 
> (avg) before: 22.699
> (avg) after:  21.955
> ===============
> 
> ================
> Using the p0004-read-tree test (posted earlier this week)
> with 1M files on Linux:
> 
> before:
> $ ./p0004-read-tree.sh
> 0004.5: switch work1 work2 (1003037)       11.99(8.12+3.32)
> 0004.6: switch commit aliases (1003037)    11.95(8.20+3.14)
> 
> after:
> $ ./p0004-read-tree.sh
> 0004.5: switch work1 work2 (1003037)       11.02(7.71+2.78)
> 0004.6: switch commit aliases (1003037)    10.95(7.57+2.82)
> ================
> 
> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
> ---
>   unpack-trees.c | 23 +++++++++++++++++++----
>   1 file changed, 19 insertions(+), 4 deletions(-)
> 
> diff --git a/unpack-trees.c b/unpack-trees.c
> index 3a8ee19..143c5d9 100644
> --- a/unpack-trees.c
> +++ b/unpack-trees.c
> @@ -531,6 +531,11 @@ static int switch_cache_bottom(struct traverse_info *info)
>   	return ret;
>   }
>   
> +static inline int are_same_oid(struct name_entry *name_j, struct name_entry *name_k)
> +{
> +	return name_j->oid && name_k->oid && !oidcmp(name_j->oid, name_k->oid);
> +}
> +
>   static int traverse_trees_recursive(int n, unsigned long dirmask,
>   				    unsigned long df_conflicts,
>   				    struct name_entry *names,
> @@ -554,10 +559,20 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,
>   	newinfo.df_conflicts |= df_conflicts;
>   
>   	for (i = 0; i < n; i++, dirmask >>= 1) {
> -		const unsigned char *sha1 = NULL;
> -		if (dirmask & 1)
> -			sha1 = names[i].oid->hash;
> -		buf[i] = fill_tree_descriptor(t+i, sha1);
> +		if (i > 0 && are_same_oid(&names[i], &names[i-1])) {
> +			/* implicitly borrow buf[i-1] inside tree_desc[i] */
> +			memcpy(&t[i], &t[i-1], sizeof(struct tree_desc));

> +		} else {
> +			const unsigned char *sha1 = NULL;
> +			if (dirmask & 1)
> +				sha1 = names[i].oid->hash;
> +			buf[i] = fill_tree_descriptor(t+i, sha1);
> +		}
>   	}
>   
>   	bottom = switch_cache_bottom(&newinfo);
> 

> > +		} else if (i > 1 && are_same_oid(&names[i], &names[i-2])) {
> > +			/* implicitly borrow buf[i-2] inside tree_desc[i] */
> > +			memcpy(&t[i], &t[i-2], sizeof(struct tree_desc));
> 
> Similar case.
> 
> > +			buf[i] = NULL;
> 
> What makes the previous two entries special, or differently put: Why not
> just check *all* previous entries?  MAX_UNPACK_TREES is 8; the number of
> comparisons would just about double in the worst case and stay the same for
> three trees or less.  The order of four trees or more wouldn't matter
> anymore.

> On Sat, Apr 08, 2017 at 04:06:41PM +0200, René Scharfe wrote:
>
>>> +		} else if (i > 1 && are_same_oid(&names[i], &names[i-2])) {
>>> +			/* implicitly borrow buf[i-2] inside tree_desc[i] */
>>> +			memcpy(&t[i], &t[i-2], sizeof(struct tree_desc));
>>
>> Similar case.
>>
>>> +			buf[i] = NULL;
>>
>> What makes the previous two entries special, or differently put: Why not
>> just check *all* previous entries?  MAX_UNPACK_TREES is 8; the number of
>> comparisons would just about double in the worst case and stay the same for
>> three trees or less.  The order of four trees or more wouldn't matter
>> anymore.
>
> If I understand correctly, we've got N (up to 8) trees, and we want to
> find sets of duplicates. Adjacency doesn't matter. Aren't our options
> basically:
>
>   - look through all previous entries naively, O(N^2)
>
>   - sort the list, O(N log N); but we need the original order, so we'd
>     have to unsort at the end, too
>
>   - use a hash table, O(N) but with O(N) extra storage
>
> I know N=8 isn't very big algorithmically speaking, but it would feel
> ugly to introduce something quadratic. Especially the limit of 8 seems
> rather arbitrary. In normal cases we see at most a 3-way merge. Beyond
> that we're in octopus territory, and 8 is way too low there (I think the
> octopus strategy just unpacks one at a time and barfs if there are any
> conflicts).
>
> I assume the rationale behind "check the last 2" is just "this
> optimization will kick in reliably for all sane cases", weird octopus
> unpack-trees be damned (though reading ca885a4fe, it sounds like 4-trees
> can actually happen, but I'm not clear on how).

> Am 07.04.2017 um 17:53 schrieb git@jeffhostetler.com:
>> From: Jeff Hostetler <jeffhost@microsoft.com>
>>
>> Teach traverse_trees_recursive() to not do redundant ODB
>> lookups when both directories refer to the same OID.
>>
>> In operations such as read-tree, checkout, and merge when
>> the differences between the commits are relatively small,
>> there will likely be many directories that have the same
>> SHA-1.  In these cases we can avoid hitting the ODB multiple
>> times for the same SHA-1.
>>
>> This patch handles n=2 and n=3 cases and simply copies the
>> data rather than repeating the fill_tree_descriptor().
>>
>> ================
>> On the Windows repo (500K trees, 3.1M files, 450MB index),
>> this reduced the overall time by 0.75 seconds when cycling
>> between 2 commits with a single file difference.
>>
>> (avg) before: 22.699
>> (avg) after:  21.955
>> ===============
>>
>> ================
>> Using the p0004-read-tree test (posted earlier this week)
>> with 1M files on Linux:
>>
>> before:
>> $ ./p0004-read-tree.sh
>> 0004.5: switch work1 work2 (1003037)       11.99(8.12+3.32)
>> 0004.6: switch commit aliases (1003037)    11.95(8.20+3.14)
>>
>> after:
>> $ ./p0004-read-tree.sh
>> 0004.5: switch work1 work2 (1003037)       11.02(7.71+2.78)
>> 0004.6: switch commit aliases (1003037)    10.95(7.57+2.82)
>> ================
>>
>> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
>> ---
>>   unpack-trees.c | 23 +++++++++++++++++++----
>>   1 file changed, 19 insertions(+), 4 deletions(-)
>>
>> diff --git a/unpack-trees.c b/unpack-trees.c
>> index 3a8ee19..143c5d9 100644
>> --- a/unpack-trees.c
>> +++ b/unpack-trees.c
>> @@ -531,6 +531,11 @@ static int switch_cache_bottom(struct
>> traverse_info *info)
>>       return ret;
>>   }
>>   +static inline int are_same_oid(struct name_entry *name_j, struct
>> name_entry *name_k)
>> +{
>> +    return name_j->oid && name_k->oid && !oidcmp(name_j->oid,
>> name_k->oid);
>> +}
>> +
>>   static int traverse_trees_recursive(int n, unsigned long dirmask,
>>                       unsigned long df_conflicts,
>>                       struct name_entry *names,
>> @@ -554,10 +559,20 @@ static int traverse_trees_recursive(int n,
>> unsigned long dirmask,
>>       newinfo.df_conflicts |= df_conflicts;
>>         for (i = 0; i < n; i++, dirmask >>= 1) {
>> -        const unsigned char *sha1 = NULL;
>> -        if (dirmask & 1)
>> -            sha1 = names[i].oid->hash;
>> -        buf[i] = fill_tree_descriptor(t+i, sha1);
>> +        if (i > 0 && are_same_oid(&names[i], &names[i-1])) {
>> +            /* implicitly borrow buf[i-1] inside tree_desc[i] */
>> +            memcpy(&t[i], &t[i-1], sizeof(struct tree_desc));
>
> An assignment would be simpler:
>
>             t[i] = t[i - 1];

>
>> +            buf[i] = NULL;
>> +        } else if (i > 1 && are_same_oid(&names[i], &names[i-2])) {
>> +            /* implicitly borrow buf[i-2] inside tree_desc[i] */
>> +            memcpy(&t[i], &t[i-2], sizeof(struct tree_desc));
>
> Similar case.
>
>> +            buf[i] = NULL;
>
> What makes the previous two entries special, or differently put: Why not
> just check *all* previous entries?  MAX_UNPACK_TREES is 8; the number of
> comparisons would just about double in the worst case and stay the same
> for three trees or less.  The order of four trees or more wouldn't
> matter anymore.

>
>> +        } else {
>> +            const unsigned char *sha1 = NULL;
>> +            if (dirmask & 1)
>> +                sha1 = names[i].oid->hash;
>> +            buf[i] = fill_tree_descriptor(t+i, sha1);
>> +        }
>>       }
>>         bottom = switch_cache_bottom(&newinfo);
>>

> Am 10.04.2017 um 23:26 schrieb Jeff Hostetler:
>> On 4/8/2017 10:06 AM, René Scharfe wrote:
>>> Am 07.04.2017 um 17:53 schrieb git@jeffhostetler.com:
>>>> +            /* implicitly borrow buf[i-1] inside tree_desc[i] */
>>>> +            memcpy(&t[i], &t[i-1], sizeof(struct tree_desc));
>>>
>>> An assignment would be simpler:
>>>
>>>             t[i] = t[i - 1];
>>
>> True, but this might be a coin toss.  Maybe we should
>> see what the generated assembly looks like for each ??
>
> Clang, GCC and ICC inline that memcpy call; the assembly output is the
> same for both variants: https://godbolt.org/g/1q0YwK.  I guess you worry
> about compilers that are just bad at struct assignments (i.e. worse than
> calling memcpy)?  Do you have examples (just curious)?

>
>> I tried to hit the common cases.  This loop runs a lot
>> and I didn't want to put an O(n^2) thing in there to
>> look for any matching peer.  Most of the time we are
>> in a simple 2 or 3 way effort.  I didn't want to pay
>> for the looping/branching overhead for the obscure [4..8]
>> efforts.
>
> Makes sense, and it's a nice heuristic.  Perhaps it would be a good idea
> to document these choices in a comment?