Steel Bank Common Lisp

Stanislaw Halik wrote, On 31/5/08 6:56 PM:
> The following code leads to heap exhaustion on SBCL 1.0.16, 386 and
> amd64:
> 
> (loop
>    (with-output-to-string (*standard-output*)
>      (warn "loop")
>      (loop repeat (* 1024 1024 10) do
>           (write-char #\Null))))
> 

The output is less confusing if you don't use *standard-output* which in 
the above code is still bound to the string output when you enter the 
heap exhaustion handler causing recursive errors trying to output the 
error information.

(loop
    (with-output-to-string (s)
      (warn "loop")
      (loop repeat (* 1024 1024 50) do
           (write-char #\Null s))))

BTW, on my first gen MacBook (2GHz Intel Core Duo) with 2GB RAM, I had 
to increase the number of iterations in the inner loop as shown above to 
get the error, ten million wasn't enough.

The above form of the test also allows you to precede it with something like

(setf *after-gc-hooks*
   (push #'(lambda()
        (format t "blah~%")) *after-gc-hooks*))

which makes it clear that GC is being called multiple times within the 
inner loop but the heap still ends up being exhausted.

I also tried inserting (gc :full t) after the (warn "loop") and the heap 
  did not get exhausted.

  -- sidney

I don't know if this is practical, but running the following to force 
every gc to be a full gc allows the loop to run without exhausting the heap.

(setf *after-gc-hooks*
    (push #'(lambda()
              (let ((*after-gc-hooks* nil))
                 (gc :full t)))
          *after-gc-hooks*))

I think the problem has been discussed before that in the general case 
once a heap exhaustion condition is detected it really is too late to do 
anything about it, especially with a copying GC that can nearly double 
the amount of memory that is being used before it reclaims the space 
used by garbage.

If I were writing a real-world application that used such large data 
structures, I think the practical solution would be to have an explicit 
call to (gc :full t) after releasing instances of the big data 
structure, or else use some sort of object pool to explicitly manage the 
use of instances of the object.

  -- sidney

Part of the issue is that we don't have a properly documented GC
tuning interface.

What I believe happens in the string-output-stream case is that the
vectors constructed to hold the output end up being promoted to higher
generations, and so survive minor GC -- and by the time we're
seriously running out of space it is too late, as you note.

Controlling the number of bytes consed between GCs is one solution.
Another would be something like

 (with-garbage ...)

hinting to the GC that most of the things consed inside the dynamic
extent for the body end up as garbage, so tenuring should be avoided,
and a deeper collection after the body might be in oder.

...of course, the best thing would be to have a more flexible heap, as
in David Lichteblau's work in this area...

Cheers,

 -- Nikodemus

"Nikodemus Siivola" <nikodemus@...> writes:

> Part of the issue is that we don't have a properly documented GC
> tuning interface.
> 
> What I believe happens in the string-output-stream case is that the
> vectors constructed to hold the output end up being promoted to higher
> generations, and so survive minor GC -- and by the time we're
> seriously running out of space it is too late, as you note.
> 
> Controlling the number of bytes consed between GCs is one solution.
> Another would be something like
> 
>  (with-garbage ...)
> 
> hinting to the GC that most of the things consed inside the dynamic
> extent for the body end up as garbage, so tenuring should be avoided,
> and a deeper collection after the body might be in oder.
> 
> ...of course, the best thing would be to have a more flexible heap, as
> in David Lichteblau's work in this area...

No, the best thing would be to have a GC that doesn't die horribly
when there is too much data in old generations.

Allowing the heap to grow just sweeps the problem under the rug for a
while, but it'll resurface once the heap will not be able to grow any
more. Either due to killing your machine by to eating all the physical
memory and swap, or due to running out of address space.

Likewise GC tuning is not the answer, since nobody actually has any
intuition about what the effect of tweaking some GC knob will really
be. And in any case it'd be completely unreasonable to require people
to do such tuning in order to have a stable system.

-- 
Juho Snellman

Hi Juho,

Would your patch address, the following issue mentioned in
http://article.gmane.org/gmane.lisp.steel-bank.devel/10194/?
 
* how to explain why Lisp lets itself get into a place where it  
cannot recover memory. All of the memory allocated during the call to  
parse-text is garbage; it can all be freed. But both SBCL and Allegro  
are unable to freed the memory without running out of memory during  
the process.

Cheers,
David

On Mon, Jun 02, 2008 at 07:00:13AM +0300, Juho Snellman wrote:
> Juho Snellman <jsnell@...> writes:
> > No, the best thing would be to have a GC that doesn't die horribly
> > when there is too much data in old generations.
> 
> Given that it doesn't look like anybody is currently fixing the
> problem for real, but reports of this problem are becoming more and
> more frequent, I wonder if we should just put in some kludge for
> now. For example like the attached one, which forces a full GC if
> before a GC it looks like the heap is getting too full (the exact
> definition of too full depends on the size of the heap, and the
> breakdown between allocated data needs to be copied vs. data that
> doesn't).
> 

> diff --git a/src/code/gc.lisp b/src/code/gc.lisp
> index e6abbb1..3e119e6 100644
> --- a/src/code/gc.lisp
> +++ b/src/code/gc.lisp
> @@ -196,6 +196,51 @@ run in any thread.")
>  (declaim (type cons *gc-epoch*))
>  (defvar *gc-epoch* (cons nil nil))
>  
> +(defconstant +max-gen+ 6)
> +(defvar *min-free-heap-factor* 16)
> +
> +;;; Possibly trigger a full GC even if only a minor GC was requested,
> +;;; if it looks like the heap is too full. This is just a kludge to
> +;;; work around the way gencgc is unable to deal gracefully with
> +;;; running out of heap during GC, and worse yet tends to cause heap
> +;;; exhaustion due to not GCing old generations frequently enough on
> +;;; some workloads.
> +;;;
> +;;; This is a horribly kludge. It's not foolproof, and it raises data
> +;;; into the oldest generation way too eagerly (since that's the
> +;;; result of a full GC). But the bug reports about this known issue
> +;;; are becoming more and more frequent, so it seems that even a
> +;;; kludge is better than nothing. -- JES, 2008-06-01
> +(defun force-full-gc-p ()
> +  #!-gencgc
> +  nil
> +  #!+gencgc
> +  (let ((movable-count 0)
> +        (immovable-count 0))
> +    ;; Count the number of pages in use currently.
> +    (dotimes (i sb!vm::last-free-page)
> +      (symbol-macrolet ((page (deref sb!vm::page-table i)))
> +        (let* ((gen (slot page 'sb!vm::gen))
> +               (flags (slot page 'sb!vm::flags))
> +               (free-p (zerop (ldb (byte 3 2) flags)))
> +               (large-p (logbitp 6 flags)))
> +          (unless free-p
> +            (if (or large-p
> +                    (eql gen 6))
> +                (incf immovable-count)
> +                (incf movable-count))))))
> +    (< sb!vm::page-table-pages
> +       (+ immovable-count
> +          movable-count
> +          ;; Account for the GC being copying. Any moveable data might
> +          ;; use up double the storage during GC. If there aren't that
> +          ;; many moveable pages around, but the heap is instead
> +          ;; filling up with large objects, still try to ensure that
> +          ;; we keep 1/16th (arbitrary) of the heap free for further
> +          ;; allocations.
> +          (max movable-count
> +               (truncate sb!vm::page-table-pages *min-free-heap-factor*))))))
> +
>  (defun sub-gc (&key (gen 0))
>    (unless (eq sb!thread:*current-thread*
>                (sb!thread:mutex-value *already-in-gc*))
> @@ -214,9 +259,10 @@ run in any thread.")
>                 (let ((old-usage (dynamic-usage))
>                       (new-usage 0))
>                   (unsafe-clear-roots)
> -
>                   (gc-stop-the-world)
>                   (let ((start-time (get-internal-run-time)))
> +                   (when (force-full-gc-p)
> +                     (setf gen +max-gen+))
>                     (collect-garbage gen)
>                     (setf *gc-epoch* (cons nil nil))
>                     (incf *gc-run-time*
> @@ -224,7 +270,6 @@ run in any thread.")
>                   (setf *gc-pending* nil
>                         new-usage (dynamic-usage))
>                   (gc-start-the-world)
> -
>                   ;; In a multithreaded environment the other threads will
>                   ;; see *n-b-f-o-p* change a little late, but that's OK.
>                   (let ((freed (- old-usage new-usage)))
> @@ -258,7 +303,7 @@ run in any thread.")
>    #!+(and sb-doc (not gencgc))
>    "Initiate a garbage collection. GEN may be provided for compatibility with
>    generational garbage collectors, but is ignored in this implementation."
> -  (sub-gc :gen (if full 6 gen)))
> +  (sub-gc :gen (if full +max-gen+ gen)))
>  
>  (defun unsafe-clear-roots ()
>    ;; KLUDGE: Do things in an attempt to get rid of extra roots. Unsafe
> diff --git a/src/code/print.lisp b/src/code/print.lisp
> index e235f4b..69c0e78 100644
> diff --git a/src/code/room.lisp b/src/code/room.lisp
> index 87770c1..029564d 100644
> --- a/src/code/room.lisp
> +++ b/src/code/room.lisp
> @@ -222,6 +222,8 @@
>                (gen (signed 8))))
>    (declaim (inline find-page-index))
>    (define-alien-routine "find_page_index" long (index long))
> +  (define-alien-variable "page_table_pages" long)
> +  (define-alien-variable "last_free_page" long)
>    (define-alien-variable "page_table" (* (struct page))))
>  
>  ;;; Iterate over all the objects allocated in SPACE, calling FUN with

> 
> -- 
> Juho Snellman

> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2008.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> Sbcl-devel mailing list
> Sbcl-devel@...
> https://lists.sourceforge.net/lists/listinfo/sbcl-devel

"David J. Neu" <davidjneu@...> writes:
> Hi Juho,
> 
> Would your patch address, the following issue mentioned in
> http://article.gmane.org/gmane.lisp.steel-bank.devel/10194/?
> 
> * how to explain why Lisp lets itself get into a place where it  
> cannot recover memory. All of the memory allocated during the call to  
> parse-text is garbage; it can all be freed. But both SBCL and Allegro  
> are unable to freed the memory without running out of memory during  
> the process.

No. The GC would still be copying, which means that in the worst case
(no garbage, memory being used by "small" objects of less than 16kB
each) you need to have double the heap compared to the working set.
And given UCS-4 strings, the problem being discussed in that thread
would have approximately a 1GB working set -> it'd run out of memory
unless you have at least a 2GB heap.

-- 
Juho Snellman

On Mon, Jun 2, 2008 at 7:00 AM, Juho Snellman <jsnell@...> wrote:
>> No, the best thing would be to have a GC that doesn't die horribly
>> when there is too much data in old generations.
>
> Given that it doesn't look like anybody is currently fixing the
> problem for real, but reports of this problem are becoming more and
> more frequent, I wonder if we should just put in some kludge for
> now. For example like the attached one, which forces a full GC if
> before a GC it looks like the heap is getting too full (the exact
> definition of too full depends on the size of the heap, and the
> breakdown between allocated data needs to be copied vs. data that
> doesn't).

I think this sounds like a good idea. Additionally, I'm wondering if
BYTES-CONSED-BETWEEN-GCS should not be proportional to the size of
dynamic space.

Cheers,

 -- Nikodemus