[Openmcl-devel] How to increate the temp-stack size

[Gary Byers]

If you're doing something like:

(objc:defmethod #/floodfill (...)
   ...
  (#/floodfill ...)
  ...)

you'll be doing a lot of foreign function calls to callbacks (lisp functions
intended to be called by foreign code.)  Each of those callbacks will establish
lisp-level condition handlers (via  HANDLER-BIND or HANDLER-CASE, I never remember);
in the 32-bit ObjC runtime, the foreign function calls use a combination of
#_setjmp and CATCH to handle ObjC exceptions that occur in the foreign code.
All of these things (establishing Lisp and ObjC condition handlers) use some
stack space; in CCL, the stack that's (mostly) used for these things is called
the thread's temp stack.

A simple recursive lisp function:

(defun countdown (n)
   (when (> n 0)
     (countdown (1- n))))

can be made to run in bounded stack space: the recursive call is tail-recursive
(nothing would need to be done after the call returns except for the caller to
return to its caller ...) and most compilers will generally try to ensure that
that function runs in constant stack space.  (Eliminating tail recursion interferes
with some people's expectations and makes debugging/reading backtraces harder for
them, so whether or not that occurs may depend on DEBUG and other optimization
settings.)  If that tail-call elimination occurs, it'd be possible to use this
funtion to count down to 0 from arbitrarily large numbers while using a small and
bounded amount of stack space.  (To be honest, the thrill of doing so may wear
off after a while.)

Making that stupid example even more stupid:

(defun countdown (n)
   (ignore-errors
     (when (> n 0)
       (countdown (1- n)))))

the condition handler established by the IGNORE-ERRORS has to remain in effect
until after the recursive call returns.  It's much harder to arrange in bounded
stack space (that might involve having the IGNORE-ERRORS not establish a handler
if it can tell that an "equivalent handler" is already in place; I don't know
if that's generally possible and tend to believe that anyone who writes code
like this fully deserves whatever happens to them.

Sadly, our new COUNTDOWN function uses stack space that's proportional to N
(to maintain the dynamically-allocated data structures used by the condition
system.)  For large enough values of N, we'll exhaust available stack space
while trying to establish a condition handler.

It might be reasonable to ask how to get more stack space, but we'd never
be able to count down from arbitrarily large values of N (without arranging
that we had proportionally arbitrarily large amounts of stack space.)

It's hard to know in this bad example what benefit the IGNORE-ERRORS offers
us, but we might decide that that the benefit of having errors ignored on
every call is no greater than that of having them ignored throughout the
execution of the outermost call.  A simple way of separating those things
would be to split the function into two parts:

(defun countdown (n)
   (labels ((countdown-aux (n)
              (when (> n 0)
                (countdown-aux (1- n)))))
     (ignore-errors
       (countdown-aux n))))

Whether the -aux function is defined via LABELS or via DEFUN or other means
isn't really relevant here.

Or:

(objc:defmethod #/floodfill (...)
   (lablels ((floodfill (...)
               ...
               (floodfill ...)))
     (floodfill ...)))


The general answer to the question "how do I get more stack space?" is "create
a larger stack when the thread was created."  That's generally possible but
can be somewhat awkward.

If the question is "how do I avoid a runtime stack overflow ?", one answer is
"use less stack space."

If your flood fill operation is logically tail recursive but the exception-
handling stuff done by OBJC:DEFMETHOD interferes with tail-call optimization,
then using a separate -aux function is one way of avoiding that interference.

If it's not logically tail-recursive ... well, I'd personally want to avoid
conversations like this:

Me: I've arranged for sufficient stack space to be able to count down from
     1 BAZILLION!
Other guy:  I can count down in bounded stack space and counted down from
     1 BAZILLION + 1 the other day!
Me: D'oh!






On Fri, 23 Sep 2011, Michael Minerva wrote:

> I'm doing a recursive flood fill operation that could put up to 1024 calls on the temp-stack (worse case scenario) but it seems that I am a little short, what would be the best way to increase the size of the temp stack in ccl?
>
>
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel
>
>