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

From: Jeff King <peff@peff.net>
Date: Dec 13, 2011, 00:54 UTC
Message-ID: <20111213005429.GA3812@sigill.intra.peff.net>
In-Reply-To: <20111213004808.GC3699@sigill.intra.peff.net>

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

Show 22 quoted lines

> 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