RE: [PATCH 2/2] Reduce qsort stack consumption

[Håkan Lindqvist <hakan dot lindqvist at enea dot com>]

> -----Original Message-----
> From: Corinna Vinschen <vinschen@redhat.com>
> Sent: den 15 mars 2018 18:46
> To: Håkan Lindqvist <hakan.lindqvist@enea.com>
> Cc: newlib@sourceware.org
> Subject: Re: [PATCH 2/2] Reduce qsort stack consumption
> 
> Hi Håkan,
> 
> On Mar 13 09:57, Håkan Lindqvist wrote:
> > From 761f70c0603a94e032bc061885250c4e4cd5a19d 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 chosen to be similar to the stack
> > frame excluding the array. Each function call recursion level can
> > handle 8 iterative recursion levels.
> >
> > Stack consumption will worsen when sorting tiny arrays that do not
> > need recursion (of 6 elements or less). It will be about equal for up
> > to 15 elements, and be an improvement for larger arrays. The best case
> > improvement is a stack size reduction down to about one quarter of the
> > stack consumption before the change.
> >
> > A design where the parameter stack array is large enough for the worst
> > case recursion level was rejected because it would worsen the stack
> > consumption when sorting arrays smaller than about 1500 elements. The
> > worst case is 31 levels on a 32-bit system.
> >
> > A design with a dynamic parameter array size was rejected because of
> > limitations in some compilers.
> > ---
> > newlib/libc/search/qsort.c | 60
> > +++++++++++++++++++++++++++++++++++++++++-----
> > 1 file changed, 54 insertions(+), 6 deletions(-)
> 
> can you please resend this patch?  It's indentation is hopelessly broken for
> some reason and so doesn't apply cleanly.  Maybe it works better as
> attachment.
> 
> Your other patch is fine, though.


Patch resent as attachment


> 
> 
> Thanks,
> Corinna
> 
> --
> Corinna Vinschen
> Cygwin Maintainer
> Red Hat

Attachment: 0002-Reduce-qsort-stack-consumption.patch
Description: 0002-Reduce-qsort-stack-consumption.patch