search

rainwoodman / tinypy

tpy, a pet python forked from tinypy
Other
21 stars 5 forks source link

Review Garbage Collection algorithm #16

Open Wiguwbe opened 3 years ago

Wiguwbe commented 3 years ago

@rainwoodman please explain more in detail what is the issue

rainwoodman commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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.