much lower recursion depth with memoization

[John Lawrence Aspden]

Hi Guys, 

I'm trying to memoize a fairly complicated double recursion, and it's blowing stack after not terribly many calls.

I've reduced the problem to a simple test case, summing from 1 to n :

user=> (clojure-version) 

"1.5.1"

user=> (def gauss-recurse (fn [n] (if (< n 1) 0 (+ n (gauss-recurse (dec n))))))

#'user/gauss-recurse

user=> (gauss-recurse 3500)

6126750

user=> (def gauss-memoized (memoize (fn [n] (if (< n 1) 0 (+ n (gauss-memoized (dec n)))))))

#'user/gauss-memoized

user=> (gauss-memoized 160)

StackOverflowError   clojure.lang.RT.boundedLength (RT.java:1654)

user=> 

Does anyone know why this would happen? Do I just have to give up on memoization and find another way to do dynamic programming?

Cheers, John.

[Mark Engelberg]

Check out my blog article from last year and search for the spot where I describe the "priming the pump" trick:
http://programming-puzzler.blogspot.com/2012/11/coin-change-kata-in-racket-and-clojure.html

If the simplest way to write the solution to your problem is to use a top-down form of memoization, you can still avoid blowing the stack by running it in a bottom-up fashion a la traditional dynamic programming.

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[John Lawrence Aspden]

Nice, but it won't work for me, since I'm trying to avoid computing all the values in the table, and so I can't use the pump-priming approach. I don't know what values I'm going to need primed!

I'm sure there are ways round it, but I think they're all complicated and ugly. 

I think I'll translate my program into python, where presumably it will just work. Or actually you've reminded me about Racket. I used to like that when it was PLT scheme.

This recursion limit really is quite nasty. I could probably live with 4000, but 200? And why would memoization make it worse anyway?

Is it possible to increase the stack size somehow? Or would that use up all the memory?

Cheers, John.

[John Lawrence Aspden]

Ah, it turns out that adding this

  :jvm-opts ["-Xss50M"] 

to project.clj

gets me about 25000 memoized self-calls, so that will do.

Last time I had to worry about stack size I was programming an 8051 . I'd forgotten!

Cheers, John.

[James Reeves]

On 23 September 2013 00:28, John Lawrence Aspden <asp...@googlemail.com> wrote:

Nice, but it won't work for me, since I'm trying to avoid computing all the values in the table, and so I can't use the pump-priming approach. I don't know what values I'm going to need primed!

I'm sure there are ways round it, but I think they're all complicated and ugly. 

I think I'll translate my program into python, where presumably it will just work. Or actually you've reminded me about Racket. I used to like that when it was PLT scheme.

As far as I can tell, the code you have will generate a stack overflow in any language. It's not tail recursive, and the first time you run the function it can't draw from the cache.

- James

[Armando Blancas]

With memoize there are additional calls (the new function and apply) per recursion, so I guess that will produce the stack overflow to happen sooner. You can use memoization once you remove the stack issue with iteration:

(defn gauss-iter [n]

  (letfn [(f [n acc]

            (if (< n 1)

              acc

              (recur (dec n) (+ acc (dec n)))))]

    (f n n)))

(def gauss-memo (memoize gauss-iter))

[Mark Engelberg]

James:

It's extremely difficult to overflow the stack in Racket, because the stack isn't arbitrarily limited to some small value -- it does some tricks so that the stack is only limited by your total available memory.

For me, having to worry about stack overflows is definitely one of the biggest pain points in Clojure.  Clojure provides a few workarounds for the common cases (recur, trampoline, lazy-seq), but there are some scenarios where you really just need ample stack. 

John:

When you're doing memoization and you have a lot of "holes" in the inputs, one option is to have two phases to your function.  The first phase takes the initial input and then computes a collection of all the inputs that are dependencies and need to be computed ahead of time.  Then in phase two, you can "prime the pump" with that particular sequence of inputs.  If you need help on this, I can give you a concrete example of how to do this.

 

Another option to consider:

I wrote a blog entry about how to use core.async to convert a stack-consuming computation into stackless with minimal transformation to your program.  I haven't tried this technique yet in any serious program, but it's worth investigating:

http://programming-puzzler.blogspot.com/2013/07/stackless-clojure-with-coreasync_7.html

[Mark Engelberg]

On Sun, Sep 22, 2013 at 8:54 PM, Mark Engelberg <mark.en...@gmail.com> wrote:

When you're doing memoization and you have a lot of "holes" in the inputs, one option is to have two phases to your function.  The first phase takes the initial input and then computes a collection of all the inputs that are dependencies and need to be computed ahead of time.  Then in phase two, you can "prime the pump" with that particular sequence of inputs.  If you need help on this, I can give you a concrete example of how to do this.

OK, here's a concrete example.  Let's say you have a recursive function f that, for every n>5, is dependent on (f (- n 5)) and (f (quot n 2)).  We'll assume that the formula is not recursive for inputs in (range 5) and that these are the base cases.

It's not obvious how to prime the pump here, so we need to compute it.

First, we express the dependencies:

(defn dependencies [n]
  (if (< n 5) [] [(- n 5) (quot n 2)]))

Next, we do a tail-recursive breadth-first search:

   
(defn all-dependencies [n]
  (loop [stack ()
         unprocessed (conj clojure.lang.PersistentQueue/EMPTY n)
         processed #{}]
    (if (empty? unprocessed) stack
      (let [i (peek unprocessed)]
        (if (processed i)
          (recur stack (pop unprocessed) processed)
          (recur (conj stack i)
                 (into unprocessed (dependencies i))
                 (conj processed i)))))))

Now, we can run all-dependencies to get back the list of inputs to prime the pump:

=> (all-dependencies 20)
(0 3 2 5 7 10 15 20)
=> (all-dependencies 30)
(0 1 3 2 5 6 7 10 12 20 15 25 30)

[Mark Engelberg]

Sorry, I wrote that implementation off-the-cuff and then realized that breadth-first search doesn't actually give you an appropriate dependency ordering.  In the above examples I gave, I had:

=> (all-dependencies 30)
(0 1 3 2 5 6 7 10 12 20 15 25 30)

which isn't right because 20 depends on 15 which doesn't come before 20 in the list.

You want to do depth-first search, adding nodes in post-traversal order.  There are several ways of going about this; here is one way that will hopefully be clear:

(defn all-dependencies [n]
  (loop [stack []
         unprocessed [n]
         processed {}]

    (if (empty? unprocessed) stack
      (let [i (peek unprocessed)

            status (processed i)]
        (case status         
          :done (recur stack (pop unprocessed) processed),
          :seen-once (recur (conj stack i) (pop unprocessed) (assoc processed i :done)),
          (recur stack (into unprocessed (dependencies i))
                 (assoc processed i :seen-once)))))))

Items start out in `unprocessed` and eventually get added to the `stack` accumulator which holds the final dependency list.  (I called it `stack` because, essentially, you're building the "call stack" that would be built by the memoized recursive function.)  A map called `processed` tracks the status of items, marking whether they have been partially or fully processed.

The first time we see an item in `unprocessed`, we mark it as :seen-once (in the `processed` map), but keep it in `unprocessed`, adding all its dependencies to `unprocessed` as well.  The second time we see the item in `unprocessed`, we can conclude that all its dependencies have already been fully processed, and therefore can mark this item as :done and move it to the final `stack`.

Now it works:

=> (all-dependencies 30)
[3 2 7 0 5 10 15 1 6 12 20 25 30]

The important thing to note here is that all-dependencies is a general strategy (known as topological sorting), and you can just pick an implementation and use it for any sort of memoization/priming task.  All you need to do is code the `dependencies` function in a way that mirrors your recursive dependencies, and plug it into this or another similar implementation of topological sort.

[Jim - FooBar();]

as Armando pointed out unless you remove the stack-issue memoization is
not going become your friend. My take would be to simply use loop/recur
and then you can memoize 'relentlessly', as Rich likes to put it :)

(defn gauss-recurse [n]
(loop [i n acc n]
(if (zero? i) acc
(recur (dec i) (+ acc (dec i))))))

Jim :)

ps: increasing the stack-size is not a real solution, is it?btw, I love
your blog posts!

[Chris Perkins]

On Sunday, September 22, 2013 5:28:37 PM UTC-6, John Lawrence Aspden wrote:

This recursion limit really is quite nasty. I could probably live with 4000, but 200? And why would memoization make it worse anyway?

The factor of 20-or-so smaller recursion limit comes not from memoize directly, but from apply, which appears to use a relatively enormous amount of stack space.

I suspect that since AFn.applyToHelper dispatches on up to 20 arguments, that stack space for all 20 is always used, even if you only pass, say, one argument.

- Chris Perkins

[John Lawrence Aspden]

Jim, increasing the stack size solved the problem in so far as it allowed the code to run (I needed a tree depth of 2000), but then it just sat and churned for hours and ran down the battery bank on my narrowboat, so I killed it.

This morning I bit the bullet and got the clojure program to output a short C program to solve the problem. It took quarter of an hour to write and 65 seconds to run.

Thanks for you kind words! There'll almost certainly be a blog post about this at some point.

John.

[John Lawrence Aspden]

Chris, thank you! 

That looks like the explanation, which cheers me up immensely, since it should be easy to work round.

I looked at the same memoize code and it never occured to me that that was what was going on. I just thought Clojure hated me.

A combination of fixing memoize and increasing the stack size should give me as much recursion as a man could reasonably need.

John.

[John Lawrence Aspden]

Puzzler, thanks for all your excellent ideas! 

I get the impression that you're as troubled as I am by the brokenness of recursion, but it looks like it can be worked around.

A bit of memory thrown at the JVM stack combined with a better memoization technique should work in most of the cases that trampoline and recur miss.

It's obviously not ideal that the stack and heap can't coexist under one limit, but worst case that means that you need twice as much memory as you should. I can live with that.

John.

[John Lawrence Aspden]

James, it will generate a stack overflow on a sufficiently large problem, certainly.

Most of the cases where recursions are a good idea are order (n^2) and worse algorithms, though, so the question is rather 'will the stack overflow before the heap is exhausted or the processor catches fire?'.

There are usually ways of dealing with cases where the recursion is just an iteration.

A stack depth of 1000000 should be livable with. A stack depth of 200 means the machine has trouble with problems I can do in my head.

Cheers, John.

[yair]

Of course John, the reason you can do the sum of 1-200 in your head is thanks to Gauss's formula, I'm assuming you're not really recursing 200 times in your head :)

Love your blog too BTW, especially your style of presentation and the types of things you write about (i.e. non-trivial but still widely interesting).

[Mark Engelberg]

I posted an article detailing the approaches I outlined earlier in this thread:
http://programming-puzzler.blogspot.com/2013/09/defeating-stack-overflows.html