This is the mail archive of the
newlib@sourceware.org
mailing list for the newlib project.
Re: [PATCH 2/2] Reduce qsort stack consumption
- From: Eric Blake <eblake at redhat dot com>
- To: Håkan Lindqvist <hakan dot lindqvist at enea dot com>, "newlib at sourceware dot org" <newlib at sourceware dot org>
- Date: Mon, 12 Mar 2018 14:10:10 -0500
- Subject: Re: [PATCH 2/2] Reduce qsort stack consumption
- Authentication-results: sourceware.org; auth=none
- References: <HE1PR07MB317703076584A58FABD5480E9FD30@HE1PR07MB3177.eurprd07.prod.outlook.com>
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