Search code examples
lispcommon-lispcollatzlispworks

Why does this blow up the heap in Lispworks?

I'm trying to solve Problem 14 in Project Euler (find the longest Collatz sequence between 1 and 1000000).

My code consists of a recursive, memoized function to calculate the length of Collatz sequences followed by a loop to find the maximum. Please see the code below:

(defparameter *collatz* (make-hash-table))
(setf (gethash 1 *collatz*) 0)

(defun n-collatz (n)
  (if (gethash n *collatz*)
      (gethash n *collatz*)
      (setf (gethash n *collatz*)
            (if (evenp n)
                (1+ (n-collatz (/ n 2)))
                (1+ (n-collatz (1+ (* n 3))))))))

(loop for i from 1 to 1000000 maximize (n-collatz i))

This worked fine in Clozure, but caused a heap overflow in Lispworks. As it exited ungracefully, I couldn't find out what happened. Actually, I don't understand why this consumes so much heap space—the biggest recursion sequence is 300-something calls. Did I miss some inefficiency in the code?

Any input is appreciated. Further comments on the code are appreciated as well.

PS: I'm using Lispworks Personal Edition, which imposes a limit on heap size.

UPDATE I did try compiling as Rainer Joswig suggested, but it didn't help.

Regarding coredump's and sds's comments, or is indeed better than if in this case, but I can't substitute the hash table for a vector because the collatz sequence goes up about 50% of the time. After running the code, the hash table has some 2.5 million entries.

Finally, and strangely, I managed to reproduce the bug while testing the syntax of a longish loop (a million iterations) that just juggled some variables and didn't collect anything at all. I lost the code unfortunately—LispWorks just went poof, alas. My best guess is that there's some leak or other memory management glitch in LispWorks' entrails.

Solution

  • I see two inefficiencies here:

    1. You are using a hash table indexed by a contiguous integer sequence. You should probably be using an (extensible) vector instead.

    2. Your recursion is not tail-recursion; you might prefer to optimize that.

    Admittedly, none of these could explain a heap exhaustion.