recursive function: heap exhausted in the second call ?

[arademaker]

I didn't really understand the documentation:

Beware that function was declared NOTINLINE, callers are not guaranteed to see the memoized function rather than have inlined the original one. Moreover, if the function is self-recursive, this (declaim (notinline SYMBOL)) must have happened before it was defined.

What is the special care for recursive functions? In my case, the strange behaviour is that after memorization, the first call works but the second one cause a heap exhausted!

I am using the fragment below, note that K is recursive:

(declaim (notinline K)) 
(defun K (w j items)
  ...)

(memoize 'K)

(defun knapsack (filename)
  (multiple-value-bind (meta items)
      (read-file filename)
    (K (car meta) (cadr meta) items)))

[fare]

I don't know what compiler or settings you are using, but:

• If the compiler directly compiles the self-recursive call into a jump, then the recursive calls don't get to be memoized. The (notinline) declaration is supposed to prevent that.
• If computing the result recursively depends on a call to the function with the same parameters, you have an infinite loop, just as with any recursive function.

Maybe you should use tracing and/or some other debugging method to figure out what's going on.

[arademaker]

Sorry, SBCL 1.4.6! The function K is not tail recursive.

[arademaker]

OK, trying to figure out the problem. It looks like the heap error is the lack of memory before a garbage collector can free space. Does it make sense? The memorization seems to work:

First, I make my code have explicit control of the memo TABLE with:

(defun knapsack (filename &key (memo (make-hash-table :test #'equal))) 
  (multiple-value-bind (meta items)
      (read-file filename)
    (let ((*items* items))
      (memoize 'K :table memo)
      (values (K (car meta) (cadr meta))
          memo))))

As expected, the first execution takes some time:

* (multiple-value-list (knapsack "/Users/ar/Sites/ED-2018-1/lista-7/knapsack_big.txt"))
(4243395 #<HASH-TABLE :TEST EQUAL :COUNT 10629293 {1008CD4383}>)

The next one instantly returns:

* (multiple-value-list (knapsack "/Users/ar/Sites/ED-2018-1/lista-7/knapsack_big.txt" :memo (cadr *)))
(4243395 #<HASH-TABLE :TEST EQUAL :COUNT 10629293 {1008CD4383}>)

[fare]

What's K ?