Re: Using qsort(3) in the kernel

[Johnny Billquist <bqt%softjar.se@localhost>]

Martin S. Weber wrote:
> On Sun, Nov 16, 2008 at 08:34:38PM +0100, Anders Magnusson wrote:
> > Martin S. Weber wrote:
> > > On Sun, Nov 16, 2008 at 01:41:34PM -0500, Steven M. Bellovin wrote:
> > > > (...)
> > > > The kernel stack is limited in size; if the recursion is too deep, it
> > > > can exceed that limit.  It's only safe to do recursion if you can (a)
> > > > guarantee the maximum depth; and (b) show that for all uses of this
> > > > routine, the total stack consumption will be low enough.
> > > Doesn't gcc 4 in the meantime finally support that 70s technique of
> > > tail call optimization? Thought I had read about that somewhen.. could
> > > be mistaken tho.
> > Yes, gcc does, but that doesn't mean that it can use it for the qsort 
> > recursions.
> > Not all recursive calls can be optimized away.
>
> Yes that's obvious. Given my background in functional languages I'm just
> intrigued by the statement 'recursive is bad, imperative for/while loops are 
> good'.

I think that was reading a bit much into it. What was said was that 
recursion is potentially problematic if you have very little stack space.
That's not the same as "recursive is bad".

Or atleast that's how I read it.

(Oh, and I love functional programming... Works with it every day...)

        Johnny