[PATCH 2/2] Reduce qsort stack consumption

[Eric Blake]

On 03/12/2018 10:46 AM, HÃ¥kan Lindqvist wrote:
>  From 512787994fa79a91230175346764efcfc9fcd833 Mon Sep 17 00:00:00 2001
> From: Hakan Lindqvist <hakan.lindqvist@enea.com>
> Date: Mon, 12 Mar 2018 14:55:01 +0100
> Subject: [PATCH 2/2] Reduce qsort stack consumption
> 
> Classical function call recursion wastes a lot of stack space.
> Each recursion level requires a full stack frame comprising all
> local variables and additional space as dictated by the
> processor calling convention.
> 
> This implementation instead stores the variables that are unique
> for each recursion level in a parameter stack array, and uses
> iteration to emulate recursion. Function call recursion is not
> used until the array is full.
> 

> + *
> + * To ensure the stack consumption isn't worsened by this design, the size of
> + * the parameter stack array is choosen to be similar to the stack frame

chosen


>   	if (r > es) {  /* Smaller part > 1 element. Both parts need sorting. */
> -		/* Sort smaller part using recursion. */
> +		if (recursion_level < PARAMETER_STACK_LEVELS) {
> +			/*
> +			 * The smaller part needs to be recursively sorted
> +			 * before the larger part is sorted. To avoid function
> +			 * call recursion the parameters for the larger part
> +			 * are pushed on the parameter_stack array. The smaller
> +			 * part is sorted using iteration and the larger part
> +			 * will be sorted when the parameter_stack is "poped"

popped

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org