Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project!

## Re: [Sbcl-help] large functions

 Re: [Sbcl-help] large functions From: Tamas Papp - 2011-12-05 09:18:06 ```On Mon, 05 Dec 2011, Nikodemus Siivola wrote: > On 5 December 2011 10:27, Tamas Papp wrote: > > > (defcrazy 5000) > > You can request a larger control stack by doing eg. > > sbcl --control-stack-size 128 > > which nets you 128 megabytes of stack, enough to compiler this monster. Is there a simple heuristic that would allow me to estimate the required control stack, eg as a function of elementary operations or anything else? Saying that it is O(n^a) with some a would be enough, I just need it for intuition. I am asking because some problems that I am working on are actually even more complex when translated into elementary operations (~1e5), _but_ there may be a way to break them up (called "checkpointing" in the AD literature, essentially I would just break up the function using knowledge on the structure of the problem), but I need to know how far need to go with that approach. Tamas ```

### Thread view

 [Sbcl-help] large functions From: Tamas Papp - 2011-12-05 08:28:24 ```Hi, I am working on AD (automatic differentiation) code in SBCL, and ran into a problem with implementing it. This is how it works at the moment: I take a graph of elementary operations --- think of it as a long let*, eg (let* ((var1 x) (var2 y) (var3 (+ var1 var2)) ...)) an turn it into another list of elementary operations. I thought I could just put it in a LAMBDA and compile, but I get Control stack exhausted (no more space for function call frames). This is probably due to heavily nested or infinitely recursive function calls, or a tail call that SBCL cannot or has not optimized away. PROCEED WITH CAUTION. [Condition of type SB-KERNEL::CONTROL-STACK-EXHAUSTED] errors when I try to compile it (toy example at the end of the message). I am looking for advice on how to do this some other way that 1. works, 2. gives reasonably fast code -- hints are enough, I will benchmark it anyway 3. allows me to leverage the existing CL facilities to a large extent. My fallback solution would be allocating a large array, and implementing elementary operations as (let ((v (make-array size :element-type 'double-float))) (setf (aref v 0) x) (setf (aref v 1) y) (setf (aref v 2) (+ (aref v 0) (aref v 1))) ... but then I lose a lot of advantages. Best, Tamas PS.: Contrived toy example: (defmacro defcrazy (n) "Contrived example." `(defun crazy (x) (check-type x double-float) (let* ,(loop repeat n collecting '(x (1+ x))) x))) (defcrazy 500) ; works (defcrazy 5000) ; control stack exhausted ```
 Re: [Sbcl-help] large functions From: Nikodemus Siivola - 2011-12-05 08:33:51 ```On 5 December 2011 10:27, Tamas Papp wrote: > (defcrazy 5000) You can request a larger control stack by doing eg. sbcl --control-stack-size 128 which nets you 128 megabytes of stack, enough to compiler this monster. Cheers,  -- Nikodemus ```
 Re: [Sbcl-help] large functions From: Nikodemus Siivola - 2011-12-05 08:35:02 ```On 5 December 2011 10:33, Nikodemus Siivola wrote: >  sbcl --control-stack-size 128 I should probably also mention that /all/ threads have the same size control stack at the moment, so spawner beware. Cheers, -- nikodemus ```
 Re: [Sbcl-help] large functions From: Tamas Papp - 2011-12-05 09:18:06 ```On Mon, 05 Dec 2011, Nikodemus Siivola wrote: > On 5 December 2011 10:27, Tamas Papp wrote: > > > (defcrazy 5000) > > You can request a larger control stack by doing eg. > > sbcl --control-stack-size 128 > > which nets you 128 megabytes of stack, enough to compiler this monster. Is there a simple heuristic that would allow me to estimate the required control stack, eg as a function of elementary operations or anything else? Saying that it is O(n^a) with some a would be enough, I just need it for intuition. I am asking because some problems that I am working on are actually even more complex when translated into elementary operations (~1e5), _but_ there may be a way to break them up (called "checkpointing" in the AD literature, essentially I would just break up the function using knowledge on the structure of the problem), but I need to know how far need to go with that approach. Tamas ```
 Re: [Sbcl-help] large functions From: Paul Khuong - 2011-12-05 17:17:26 ```In article <20111205084920.GA16906@...>, Tamas Papp wrote: > On Mon, 05 Dec 2011, Nikodemus Siivola wrote: > > > On 5 December 2011 10:27, Tamas Papp wrote: > > > > > (defcrazy 5000) > > > > You can request a larger control stack by doing eg. > > > > sbcl --control-stack-size 128 > > > > which nets you 128 megabytes of stack, enough to compiler this monster. > > Is there a simple heuristic that would allow me to estimate the > required control stack, eg as a function of elementary operations or > anything else? Saying that it is O(n^a) with some a would be enough, > I just need it for intuition. I'm pretty sure that the maximum recursion depth is O(n). Compilation time, however, I'm also pretty sure is at least quadratic (even with speed optimisations disabled). Not flattening nested scopes might help a bit here, i.e.: (let ((x (let ((y ...)) ...))) ...) instead of (let* ((y ...)) (x ...)) ...) If multiple values are needed, multiple-value-bind should work just the same. ISTM that'll be closer to the original expression as well. > I am asking because some problems that I am working on are actually > even more complex when translated into elementary operations (~1e5), > _but_ there may be a way to break them up (called "checkpointing" in > the AD literature, essentially I would just break up the function > using knowledge on the structure of the problem), but I need to know > how far need to go with that approach. In that case, something else that could help is putting broken-up pieces in notinline local functions. That'll easily get you specialised calling conventions (everything unboxed, a la C, but with better support for multiple return values), but should still keep the compiler from having enough static information to derive further information for eons. Paul Khuong ```