search

metaeducation / rebol-issues

6 stars 1 forks source link

Crash R3 using a "deep block" - Garbage Collector problem #2072

Open rebolbot opened 10 years ago

rebolbot commented 10 years ago

Submitted by: Ladislav

In R3 the stack depth is limited. Also, R3 uses a "classic" (non-coloured) Mark&Sweep alorithm. The combination of these factors causes the crash below.

Possible fix: can be fixed updating to a more modern tri-colour marking not using the stack space.

a: copy []
loop 200000 [a: append/only copy [] a]
recycle

CC - Data [ Version: r3 master Type: Bug Platform: All Category: Native Reproduce: Always Fixed-in:none ]

rebolbot commented 10 years ago

Submitted by: Ladislav

in the core-tests suite
rebolbot commented 10 years ago

Submitted by: Ladislav

#876 describes a similar problem
rebolbot commented 9 years ago

Submitted by: abolka

This bug is most likely a duplicate of #1776. However, this bug has a more detailed/accurate description.

To (more verbosely) add my findings to Ladislav's concise remark: the crash stems from a C stack overflow in the garbage collector. The collector (src/core/m-gc.c) is currently a straight-forward recursive implementation. That is, it recursively scans over all children of any scanned R3 value. The deeply-nested R3 value above causes this recursive implementation to overflow the stack.

For those not versed with garbage collection theory: The current recursive collector can be considered a simple two-coloured "black/white" mark-sweep collector: black means "alive" (in use, must not be collected), white means "dead" (free to collect during the sweep phase). The "gray" in a tri-colouring implementation adds an "alive but children not yet scanned" state.

http://www.memorymanagement.org/glossary/t.html#tri-color.marking

Typically, tri-colouring is employed to make a garbage collector incremental. Initially, we would not primarily switch to tri-colouring to make the GC incremental, but solely to avoid above stack overflow.

hostilefork commented 6 years ago

This particular bug is resolved in Ren-C...but not by tri-color marking. For entities that might be cyclic (e.g. blocks) it queues things for GC rather than recursing on the spot. Simple series that don't themselves hold references (like STRING!) can be marked without queueing. Implementing an incremental garbage collector is a desired further goal.