Re: [PATCH] Properly align memory allocations and temporary buffers

From: René Scharfe <l.s.r@web.de>
Date: Jan 7, 2022, 20:56 UTC
Message-ID: <40077881-e91a-dfba-5950-cdc03719264d@web.de>
In-Reply-To: <xmqq7dbb9wcz.fsf@gitster.g>

Am 07.01.22 um 20:30 schrieb Junio C Hamano:

Show 16 quoted lines

> "brian m. carlson" <sandals@crustytoothpaste.net> writes:
>
>> I'm not opposed to a small amount of finagling for this case, but I am
>> very much opposed to defining your C ABI in an intentionally difficult
>> way.
>
> I was looking at git_qsort_s() today and thought that its use of
> "char buf[1k]" on stack is something we would write for a system
> without alloca().
>
> We already have xalloca() wrapper defined in the compat-util header.
> Perhaps it is a good idea to use it instead?
>
> Both the true alloca() and xmalloc() we use as a fallback (when
> <alloca.h> is not available) are supposed to return a block of
> memory that is suitably aligned for any use, no?

If falling back to malloc(3) is fine in general then I wonder if we can just it use always. This would save two branches and make buffer management trivial here. How much worse is malloc(3) on platforms with alloca(3)? Do we sort lots of short lists somewhere? In other words: Does this stack allocation optimization actually make a measurable difference?

Heap fragmention should not be a concern here, at least, because the pattern of requesting, using and releasing a single allocation won't leave holes.

Show 41 quoted lines

>
>  compat/qsort_s.c | 20 +++++++++++---------
>  1 file changed, 11 insertions(+), 9 deletions(-)
>
> diff --git c/compat/qsort_s.c w/compat/qsort_s.c
> index 52d1f0a73d..63660a4304 100644
> --- c/compat/qsort_s.c
> +++ w/compat/qsort_s.c
> @@ -49,21 +49,23 @@ int git_qsort_s(void *b, size_t n, size_t s,
>  		int (*cmp)(const void *, const void *, void *), void *ctx)
>  {
>  	const size_t size = st_mult(n, s);
> -	char buf[1024];
> +	char *tmp;
> +	int use_alloca;
>
>  	if (!n)
>  		return 0;
>  	if (!b || !cmp)
>  		return -1;
>
> -	if (size < sizeof(buf)) {
> -		/* The temporary array fits on the small on-stack buffer. */
> -		msort_with_tmp(b, n, s, cmp, buf, ctx);
> -	} else {
> -		/* It's somewhat large, so malloc it.  */
> -		char *tmp = xmalloc(size);
> -		msort_with_tmp(b, n, s, cmp, tmp, ctx);
> +	use_alloca = (size < 1024);
> +
> +	tmp = use_alloca ? xalloca(size) : xmalloc(size);
> +
> +	msort_with_tmp(b, n, s, cmp, tmp, ctx);
> +
> +	if (use_alloca)
> +		xalloca_free(tmp);
> +	else
>  		free(tmp);
> -	}
>  	return 0;
>  }