Re: [PATCH 3/4] fetch-pack: match refs exactly

[Jeff King <peff@peff.net>]

On Mon, Dec 12, 2011 at 07:48:08PM -0500, Jeff King wrote:

> diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
> index 46688dc..6207ecd 100644
> --- a/builtin/fetch-pack.c
> +++ b/builtin/fetch-pack.c
> @@ -556,11 +556,16 @@ static void filter_refs(struct ref **refs, int nr_match, char **match)
>  			continue;
>  		}
>  		else {
> -			int order = path_match(ref->name, nr_match, match);
> -			if (order) {
> -				return_refs[order-1] = ref;
> -				continue; /* we will link it later */
> +			int i;
> +			for (i = 0; i < nr_match; i++) {
> +				if (!strcmp(ref->name, match[i])) {
> +					match[i][0] = '\0';
> +					return_refs[i] = ref;
> +					break;
> +				}
>  			}
> +			if (i < nr_match)
> +				continue; /* we will link it later */

Astute readers may notice that our matching scheme is now something
like:

  for ref in refs
    for match in matches
      strcmp(ref, match)

If you are fetching everything, that's O(n^2) strcmps (where n is the
number of remote refs). If we sorted the match list (the refs list is
already sorted), we could turn it into an O(n lg n) sort+merge.  This is
an optimization we couldn't do with the old suffix-matching rule.

I doubt it matters in any practical case. Even for our crazy 100K ref
cases at GitHub, we don't tend to actually fetch all of those at one
time. So it is more like O(n * m), where m is probably in the dozens at
most.

-Peff