Re: [PATCH] tree-diff: avoid alloca for large allocations

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 8, 2016, 00:36 UTC
Message-ID: <xmqq8tygo6s4.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <20160607225300.GA2285@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 14 quoted lines

> An alternative to this would be implement something like:
>
>   struct tree *tp, tp_fallback[2];
>   if (nparent <= ARRAY_SIZE(tp_fallback))
>           tp = tp_fallback;
>   else
> 	  ALLOC_ARRAY(tp, nparent);
>   ...
>   if (tp != tp_fallback)
> 	  free(tp);
>
> That would let us drop our xalloca() portability code
> entirely. But in my measurements, this seemed to perform
> slightly worse than the xalloca solution.

It indeed is curious why this "obvious" alternative performed worse.

Show 10 quoted lines

> +#define FAST_ARRAY_ALLOC(x, nr) do { \
> +	if ((nr) <= 2) \
> +		(x) = xalloca((nr) * sizeof(*(x))); \
> +	else \
> +		ALLOC_ARRAY((x), nr); \
> +} while(0)
> +#define FAST_ARRAY_FREE(x, nr) do { \
> +	if ((nr) > 2) \
> +		free((x)); \
> +} while(0)

An obvious and clean implementation of the idea.

The only slight worry I have is that nr must stay constant until the time the caller calls FREE(), but for the only three callsite pairs it is clear nparent will stay constant and this is local to the file.

Thanks.

Show 42 quoted lines

>  static struct combine_diff_path *ll_diff_tree_paths(
>  	struct combine_diff_path *p, const unsigned char *sha1,
> @@ -265,7 +275,7 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
>  	if (recurse) {
>  		const unsigned char **parents_sha1;
>  
> -		parents_sha1 = xalloca(nparent * sizeof(parents_sha1[0]));
> +		FAST_ARRAY_ALLOC(parents_sha1, nparent);
>  		for (i = 0; i < nparent; ++i) {
>  			/* same rule as in emitthis */
>  			int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);
> @@ -277,7 +287,7 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
>  		strbuf_add(base, path, pathlen);
>  		strbuf_addch(base, '/');
>  		p = ll_diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);
> -		xalloca_free(parents_sha1);
> +		FAST_ARRAY_FREE(parents_sha1, nparent);
>  	}
>  
>  	strbuf_setlen(base, old_baselen);
> @@ -402,8 +412,8 @@ static struct combine_diff_path *ll_diff_tree_paths(
>  	void *ttree, **tptree;
>  	int i;
>  
> -	tp     = xalloca(nparent * sizeof(tp[0]));
> -	tptree = xalloca(nparent * sizeof(tptree[0]));
> +	FAST_ARRAY_ALLOC(tp, nparent);
> +	FAST_ARRAY_ALLOC(tptree, nparent);
>  
>  	/*
>  	 * load parents first, as they are probably already cached.
> @@ -531,8 +541,8 @@ static struct combine_diff_path *ll_diff_tree_paths(
>  	free(ttree);
>  	for (i = nparent-1; i >= 0; i--)
>  		free(tptree[i]);
> -	xalloca_free(tptree);
> -	xalloca_free(tp);
> +	FAST_ARRAY_FREE(tptree, nparent);
> +	FAST_ARRAY_FREE(tp, nparent);
>  
>  	return p;
>  }