Out of memory in tight consing loop

[Stefan Mandl]

Dear SBCL-Team, an example is probably better than many words:

--------------------------------------------------------------------------------------
stm@t420:~$ sbcl
This is SBCL 1.0.58, 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.
* (defun cnt ()
  (let* ((back (cons 2 nil))
         (front (cons 1 back)))
    (loop do
          (progn (rplacd back (cons 3 nil))
                 (setq back (cdr back))
                 (setq front (cdr front))))))

CNT
* (cnt)
Heap exhausted during garbage collection: 0 bytes available, 8 requested.
 Gen StaPg UbSta LaSta LUbSt Boxed Unboxed LB LUB !move Alloc Waste Trig WP GCs Mem-age
   0: 0 0 0 0 0 0 0 0 0 0 0 5368709 0 0 0.0000
   1: 72561 0 0 0 39329 0 0 0 0 161083248 8336 5368709 0 0 1.0001
   2: 129917 129915 0 0 61247 212 11 0 10 251468736 312384 2000000 61248 0 0.0000
   3: 0 0 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
   4: 0 0 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
   5: 0 0 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
   6: 0 0 0 0 5706 1285 0 0 0 28635136 0 2000000 5559 0 0.0000
   Total bytes allocated = 536546168
   Dynamic-space-size bytes = 536870912
GC control variables:
   *GC-INHIBIT* = true
   *GC-PENDING* = in progress
   *STOP-FOR-GC-PENDING* = false
fatal error encountered in SBCL pid 18463(tid 3084621504):
Heap exhausted, game over.

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

--------------------------------------------------------------------------------------

I found that when adding (gc :full t) to the loop, the system seems to run ok:

(defun cnt2 ()
  (let* ((back (cons 2 nil))
         (front (cons 1 back))
         (c 0))
    (loop do
          (progn
            (incf c)
            (when (zerop (mod c 100))
              (gc :full t)
              (setq c 0))
            (rplacd back (cons 6 nil))
            (setq back (cdr back))
            (setq front (cdr front))
            ))))

Anyhow, this probably should not be necessay.
BTW, ECL has a similar problem while CLISP does fine.

My system:
Linux t420 3.2.0-39-generic-pae #62-Ubuntu SMP Wed Feb 27 22:25:11 UTC 2013 i686 i686 i386 GNU/Linux

And *features*:
(:QUICKLISP :SB-BSD-SOCKETS-ADDRINFO :ASDF2 :ASDF :ASDF-UNICODE :ANSI-CL
 :COMMON-LISP :SBCL :SB-DOC :SB-TEST :SB-LDB :SB-PACKAGE-LOCKS :SB-UNICODE
 :SB-EVAL :SB-SOURCE-LOCATIONS :IEEE-FLOATING-POINT :OS-PROVIDES-POLL
 :OS-PROVIDES-GETPROTOBY-R :OS-PROVIDES-SUSECONDS-T :OS-PROVIDES-BLKSIZE-T
 :OS-PROVIDES-PUTWC :OS-PROVIDES-DLADDR :OS-PROVIDES-DLOPEN :LITTLE-ENDIAN
 :LINKAGE-TABLE :MULTIPLY-HIGH-VOPS :MEMORY-BARRIER-VOPS :INLINE-CONSTANTS
 :CYCLE-COUNTER :ALIEN-CALLBACKS :STACK-ALLOCATABLE-FIXED-OBJECTS
 :STACK-ALLOCATABLE-LISTS :STACK-ALLOCATABLE-VECTORS
 :STACK-ALLOCATABLE-CLOSURES :RAW-INSTANCE-INIT-VOPS
 :UNWIND-TO-FRAME-AND-CALL-VOP :COMPARE-AND-SWAP-VOPS :C-STACK-IS-CONTROL-STACK
 :STACK-GROWS-DOWNWARD-NOT-UPWARD :GENCGC :LARGEFILE :SB-FUTEX :SB-THREAD
 :LINUX :ELF :UNIX :X86)

Kind regards,

Stefan Mandl

[James M. Lawrence (llmjjmll)]

This is the nature of conservative gcs; it is only related to Lisp insofar as SBCL and ECL have conservative gcs. When there is a boundlessly growing list as in your example, a cons may eventually be retained by the gc, whereupon infinite storage will be required. This is the "false positive" mentioned in

http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29#Precise_vs._conservative_and_internal_pointers

The solution is to break the chain by replacing

(setq front (cdr front))

with

(setf front (prog1 (cdr front)
              (setf (cdr front) nil)))

For performance reasons this should be probably done even in CL implementations that don't have a conservative gc, as it can significantly reduce a gc's workload.

[Stefan Mandl (stefanmandl)]

Thanks a lot for the clarification!

Probably a hint could be added to SBCL's manual in section

"2.7 History and Implementation of SBCL"

[Fredrik Tolf (fredrik-dolda2000)]

I am currently also being bitten pretty hard by this problem. I do wonder, at least, since for me as well running (gc :full t) every so often helps, is there a reason why the GC doesn't normally run a full collection when it needs more memory? It sounds to me like a full GC could just be run automatically whenever necessary rather than triggered manually.

(I have implemented list-breaking wherever I could, but there seem to be algorithms in my program that trigger this problem in less obvious ways.)

[Dima Akater (akater)]

Note: evaluating the form

(let ((large-number 36000000)) (loop :for i :from 1 :to large-number :collect i) nil)

several times causes heap exhaustion as well, even though intermediate lists are not referenced anymore. In my case, this particular large number makes 3 or even 2 evaluations in a row fatal.

I don't have much experience with GC and actually I wouldn't even expect SBCL's GC to work correctly in the case presented by original poster but I'd certainly expect to be able to safely reevaluate any form that had at least once evaluated successfully in REPL and that discarded all large structures it produced. It seems to me that (gc :full t) can always run between individual evaluations in REPL while user is ruminating over latest results, without causing the user any discomfort.

P.S. I return NIL so that the result is truly discarded and is not referenced, say, by a SLIME presentation.

[Felix Lange (lp-fjl)]

Here's another failing test case:

    (defun alloc-loop (n)
      (let (buffer)
        (dotimes (i n)
          (setf buffer (make-array (* 100 1024 1024))))
        (aref buffer 0)))

    (time (alloc-loop 100))

The (ALLOC-LOOP 100) invocation fails with SBCL. It works with other CL runtimes including
ECL, which has a conservative collector.

I'm not sure if this has anything to do with it being conservative. My expectation would
be that heap exhaustion causes the GC to run and release unused memory. For some reason,
this does not seem to happen in SBCL.

$ sbcl
This is SBCL 2.0.10, an implementation of ANSI Common Lisp. ...
* (defun alloc-loop (n)
    (let (buffer)
      (dotimes (i n)
        (setf buffer (make-array (* 100 1024 1024))))
      (aref buffer 0)))

ALLOC-LOOP
* (time (alloc-loop 100))
Heap exhausted during allocation: 153190400 bytes available, 838860816 requested.
Gen Boxed Code Raw LgBox LgCode LgRaw Pin Alloc Waste Trig WP GCs Mem-age
 1 130 1 38 25601 0 0 25608 844269840 161520 855007258 25770 1 0.0000
 2 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
 3 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
 4 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
 5 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
 6 434 2 184 55 0 10 0 21699536 746544 2000000 685 0 0.0000
           Total bytes allocated = 865969376
           Dynamic-space-size bytes = 1073741824
GC control variables:
   *GC-INHIBIT* = false
   *GC-PENDING* = true
   *STOP-FOR-GC-PENDING* = false