Re: [PATCH v2 09/12] remote: use strmap for match_explicit_refs()

[Junio C Hamano <gitster@pobox.com>]

Jon Simons <jon@jonsimons.org> writes:

> Optimize match_explicit_refs() by replacing two linear refs traversals
> with strmap lookups.

Ahh, an obvious thing to do for performance.  And the ...

>
> Before this change, matching R explicit refspecs against N local refs
> and M remote refs in match_explicit() entails O(R * N) and O(R * M)
> calls to refname_match() for sources and destinations respectively.
>
> After this change, we build a strmap for local refs O(N), a strmap for
> remote refs O(M), and use them for O(R * rules) lookups of the refspecs.
>
> Refspecs are resolved using count_refspec_match_in_map() introduced
> earlier in the series, which issues one strmap lookup for each candidate
> rules pattern generated with expand_ref_prefix().
>
> The match_explicit_lhs_map() function introduced in a previous commit
> has now been recombined into match_explicit_lhs(): all call sites are
> now using the new strmap variation.
>
> Timings show benefit where one or both of the client and remote have
> many refs, and multiple refspecs are specified:
>
>   Test                           HEAD~1            HEAD
>   -----------------------------------------------------------------------
>   5516.3: empty:refspecs:1       0.13(0.07+0.10)   0.14(0.07+0.10) +7.7%
>   5516.5: empty:refspecs:10      0.17(0.10+0.11)   0.14(0.07+0.11) -17.6%
>   5516.7: empty:refspecs:100     0.47(0.41+0.10)   0.15(0.08+0.10) -68.1%
>   5516.9: mirror:refspecs:1      0.17(0.10+0.11)   0.17(0.10+0.11) +0.0%
>   5516.11: mirror:refspecs:10    0.23(0.16+0.11)   0.17(0.10+0.11) -26.1%
>   5516.13: mirror:refspecs:100   0.87(0.80+0.11)   0.18(0.11+0.11) -79.3%

... numbers do look promising.

> -static int match_explicit_lhs_count(const int count,
> -				    struct refspec_item *rs,
> -				    struct ref **match,
> -				    int *allocated_match)
> +static int match_explicit_lhs(struct strmap *src,
> +			      struct refspec_item *rs,
> +			      struct ref **match,
> +			      int *allocated_match)
>  {
> -	switch (count) {
> +	switch (count_refspec_match_in_map(rs->src, src, match)) {
>  	case 1:
>  		if (allocated_match)
>  			*allocated_match = 0;
> @@ -1239,24 +1239,6 @@ static int match_explicit_lhs_count(const int count,
>  	}
>  }
>  
> -static int match_explicit_lhs(struct ref *src,
> -			      struct refspec_item *rs,
> -			      struct ref **match,
> -			      int *allocated_match)
> -{
> -	return match_explicit_lhs_count(count_refspec_match(rs->src, src, match),
> -					rs, match, allocated_match);
> -}

It is a bit unsatisfactory that we lose the callers to the linear
count_refspec_match() in this file, but still need to retain the
function itself for external callers.  It may be outside the scope
of this series, but are these external callers also benefit from
having access to the _in_map() variant (which would probably need to
expose not just that function but the ref_map_init() machinery)?