Review Garbage Collection algorithm

[Wiguwbe]

@rainwoodman please explain more in detail what is the issue

[rainwoodman]

Thanks for creating the ticket.

The existing source code appears to be implementing a tri-color incremental tracing garbage collector.
And I do not fully understand how it works. Making the issue more precarious is that I have also threw in a few 'fixes' here and there, making it less consistent with the standard algorithm, of which I haven't find a reference implementation for the incremental variant. The bottom line: when I read the current implementation, I cannot convince myself it is bugfree (and bugs keep showing up), and I also cannot convince myself its performance is acceptable.

The only documentation I could find about the tinypy garbage collection is this post:
https://www.philhassey.com/blog/2008/02/05/64k-tinypy-garbage-collection-is-tough/

The GoLang Garbage collector appears to be in the same algorithm family(tri-color):
https://blog.golang.org/ismmkeynote
https://stackoverflow.com/questions/7823725/what-kind-of-garbage-collection-does-go-use

I am hoping to adopt some ideas from them. Of course we won't need the very fancy concurrency feature of the Go GC.
tinypy is not thread friendly anyway. Perhaps starting with the object traversal, incrementalness, and the color side-bits.

[rainwoodman]

Related to #24. Some of the memory related crashes were because the compiler producing incorrect REGS instruction such that certain stack variables are missing from the grey list after a full step.

[rainwoodman]

The convention when to use tp_track still need some clarification.
Part of the blame was my addition of the _t variants of object constructors that automatically calls tp_track.
As we only run gc between VM instructions, I feel may be we should minimize the use of tp_track on temps produced during the C land, and use tp_delete to properly clean up the temps.

[ferdnyc]

@rainwoodman Sorry for the necromancy. I think one of the issues with the GC may be that a particular commit you made early on introduced what looks like a fundamental breakage, and I don't think it's ever been addressed since because it's still in the current code.

That commit reworked tp_full() and tp_gcinc() together into tp_gc_run(), and replaced the tp_gcinc() condition:

void tp_gcinc(TP) {
    if (tp->gcmax == 0 || (tp->steps % tp->gcmax == 0)) {
        tp_full(tp);
        tp->steps += 1;
        return;

with this tp_gc_run() condition:

void tp_gc_run(TP, int full) {
    if (full || tp->gcmax == 0 || (tp->steps % tp->gcmax == 0)) {
        tp_mark(tp, -1);
    } else {
        /* mark 2 items from the grey list every step */
        tp_mark(tp, 2);
    }

But it also turned tp_scan_grey() into tp_mark() with an extra condition on the while loop that checks its new (second) argument, max:

- void tp_scan_grey(TP) {
-     while (tp->grey->len) {
+ void tp_mark(TP, int max) {
+     while (tp->grey->len && max > 0) {
          tp_obj v;
          /* pick a grey object */
          v = tpd_list_pop(tp, tp->grey, tp->grey->len-1, "_tp_gcinc");
          if(v.gc.gci->black) {
              abort();
          }
          /* color it as black. */
          v.gc.gci->black = 1;
          v.gc.gci->grey = 1;
          tpd_list_appendx(tp, tp->black, v);

          /* put children to grey. */
          tp_follow(tp,v);
          if(max > 0) max--;
      }
  }

I think the intention was that when max is passed in as -1, tp_mark() wouldn't limit the number of iterations and would instead mark the entire grey list.

But what actually happens is, when it's passed -1 the while (tp->grey->len && max > 0) test immediately fails (the second half is false), so it never even enters the loop, and tp_mark() returns without having done anything at all... right? Or am I missing something?

[ferdnyc]

(I would have assumed it's intentional, except... why call tp_mark(___, -1) at all, if it's not meant to do anything? Having the call in there makes no sense, if that's how it was truly intended to work.)

[rainwoodman]

Thanks for investigating this. Your reasoning looked quite plausible but I have not touched this code base for a while to tell if this is actually the case. Is it possible to verify your assertion by adding some logging and observe the intended marking never happens when we run the tests? Any recommendations how to fix this?

…

On Wed, Sep 24, 2025 at 1:00 AM Frank Dana ***@***.***> wrote: *ferdnyc* left a comment (rainwoodman/tinypy#16) <#16 (comment)> (I would have assumed it's intentional, except... why call tp_mark(___, -1) at all, if it's not meant to do anything? Having the call in there makes no sense, if that's how it was truly intended to work.) — Reply to this email directly, view it on GitHub <#16 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AABBWTHUEOWFDXPUSWFTQBD3UJFQFAVCNFSM6AAAAACHLD6JD6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTGMRXGA4TCNZZGM> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[ferdnyc]

@rainwoodman

Is it possible to verify your assertion by adding some logging and
observe the intended marking never happens when we run the tests?

Yes, and the draft PR I just opened (#45) does that. (Both the add-some-logging part, and the verify my assertion part.)

Note that I had to make some unrelated changes to modules/re/regexpr.h to get the code to compile. Modern GCCs no longer let you declare a function without its arguments in a header, they complain now that the declaration doesn't match the definition. So, the first commit fixes that by adding the argument types to the declarations.