In article <20111205084920.GA16906@...>,
Tamas Papp <tkpapp@...> wrote:
> On Mon, 05 Dec 2011, Nikodemus Siivola wrote:
> > On 5 December 2011 10:27, Tamas Papp <tkpapp@...> 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 ...)) ...))) ...)
(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.