heap exhausted

[Rainer Joswig]

This is SBCL on a Mac running macOS 10.14.3

I'm running some kind of MAPPEND function three times in a row. Then the heap is exhausted. The results retained in the listener shouldn't be too large. The intermediate lists created by the test are 5000 x 5000 elements. Should the GC be able to reclaim the memory?

bash-3.2$ sbcl
This is SBCL 1.5.0, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (setf *print-length* 40)

(defun mappend (function lists)
  (loop with arg = (make-list (length lists))
        and lists1 = (make-array (length lists) :initial-contents lists)
        while (aref lists1 0)
        do (loop for i below (length lists1)
                 for l on arg
                 do (setf (first l) (first (aref lists1 i))))
        append (funcall function arg)
        do (loop for i below (length lists1) do (pop (aref lists1 i)))))

(defun test (n)
  (let ((l (loop for i below n collect (loop repeat n collect i))))
    (time (mappend (lambda (e) (list :a (car e) :b (cadr e))) l))))
40
* MAPPEND
* TEST
* (test 5000)
Evaluation took:
  0.342 seconds of real time
  0.342000 seconds of total run time (0.341912 user, 0.000088 system)
  100.00% CPU
  1,091,655,274 processor cycles
  737,168 bytes consed

(:A 0 :B 1 :A 0 :B 1 :A 0 :B 1 :A 0 :B 1 :A 0 :B 1 :A 0 :B 1 :A 0 :B 1 :A 0 :B
 1 :A 0 :B 1 :A 0 :B 1 ...)
* (test 5000)
Evaluation took:
  0.335 seconds of real time
  0.335355 seconds of total run time (0.335271 user, 0.000084 system)
  100.00% CPU
  1,070,441,555 processor cycles
  764,304 bytes consed

(:A 0 :B 1 :A 0 :B 1 :A 0 :B 1 :A 0 :B 1 :A 0 :B 1 :A 0 :B 1 :A 0 :B 1 :A 0 :B
 1 :A 0 :B 1 :A 0 :B 1 ...)
* (test 5000)
Heap exhausted during garbage collection: 0 bytes available, 16 requested.
Gen Boxed Unboxed LgBox LgUnbox Pin Alloc Waste Trig WP GCs Mem-age
 0 0 0 0 0 0 0 0 10737418 0 0 0.0000
 1 16397 1 0 0 7 537162864 166800 332832602 16398 1 1.3994
 2 15548 42 0 0 14 510702224 150896 2000000 15590 0 0.2263
 3 0 0 0 0 0 0 0 2000000 0 0 0.0000
 4 0 0 0 0 0 0 0 2000000 0 0 0.0000
 5 0 0 0 0 0 0 0 2000000 0 0 0.0000
 6 449 220 64 47 0 24788416 770624 2000000 780 0 0.0000
 7 0 0 0 0 0 0 0 2000000 0 0 0.0000
           Total bytes allocated = 1072653504
           Dynamic-space-size bytes = 1073741824
GC control variables:
   *GC-INHIBIT* = true
   *GC-PENDING* = true
   *STOP-FOR-GC-PENDING* = false
fatal error encountered in SBCL pid 4747(tid 0xf4af5c0):
Heap exhausted, game over.

Welcome to LDB, a low-level debugger for the Lisp runtime environment.
ldb>

[Paul F. Dietz (paul-f-dietz)]

For N = 5000, the list of lists L is ~25 million cons cells, occupying about 400M bytes of memory (on X86-64). If I recall correctly, the default build for sbcl has a maximum heap size of 500M. So it shouldn't be surprising you've run out of memory here, since GC needs some room for copying.

You aren't seeing this because your call to TIME does not include the loops where you are building L.

You can rebuild sbcl with a large heap size by specifying the --dynamic-space-size argument in the build script.

[Rainer Joswig (joswig-k)]

It happens after the third call. The memory of the first two calls won't be reclaimed or is it the memory retained from the result?

[Paul F. Dietz (paul-f-dietz)]

You're skating close enough to the edge, I think, that it blowing up only on the third call shouldn't be taken as indicating a bug.

You might try a call to SB-EXT-GC (and also try a call with :full t) between tests to see if the problem still occurs. If it does with the former but not the latter then maybe some garbage is going into an older generation and isn't getting collected soon enough.

Also, is the Mac OS build using the conservative collector? If so, maybe there's a false pointer into that list that's keeping it from being collected.

I think SBCL's design philosophy is to not worry too much about a bit of extra memory usage if that makes GC faster.

[Rainer Joswig (joswig-k)]

The error persists with calls to (GC) but not with calls to (GC :full t).

When such an 'Heap exhausted during garbage collection' appears, could SBCL abandon that GC, do a full GC and then retry the allocation? Or alternatively, could it resize its heap?