[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: Using qsort(3) in the kernel
On Mon, 17 Nov 2008 01:00:18 +0100
Johnny Billquist <bqt%softjar.se@localhost> wrote:
> 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.
Agreed, but we sometimes run very close to the limit. I've had kernel
stack space problems in the past; we don't need to create situations
where some people will run into troubles that the developer who added
some code couldn't anticipate or test.
--Steve Bellovin, http://www.cs.columbia.edu/~smb
Main Index |
Thread Index |