search

evincarofautumn / kitten

A statically typed concatenative systems programming language.
http://kittenlang.org/
Other
1.09k stars 39 forks source link

Explore GC strategies #131

Open evincarofautumn opened 9 years ago

evincarofautumn commented 9 years ago

The C backend currently uses naïve reference counting. This works reasonably well, because Kitten is cycle-free. However, there are many dynamic checks for uniqueness in order to enable local mutation. Putting linear or affine references in the language would help with this, though these require support from the type system to prevent sharing and cycles.

The reclamation strategy could be tweaked as well. At the moment, dropping a reference may pause for arbitrarily long while the tree of references is traversed. For a deep hierarchical object, this could induce unacceptable variation in GC times.

One strategy to explore would be incremental reference counting—dropping a unique reference adds it to a mark queue, and allocation sweeps the queue up to a user-specified limit on number of references or time spent.

Another thing to try is making reference updates explicit in the IR, and optimising away unnecessary retains and releases.

strager commented 9 years ago

Another solution: don't generate garbage. =]

Another another solution: allocation zones.

typesanitizer commented 5 years ago

Close this issue (in light of #193)? Or are you planning to bundle in an optional GC?

evincarofautumn commented 5 years ago

Yeah, I guess I should close or update this to reflect how my thinking and the actual implementation have been evolving.

By “GC strategies”, I meant any strategy for collecting garbage, including both reference-counting and the tracing garbage collection that’s commonly called just “GC”. I’d like to avoid ruling out shipping a tracing GC as a library, but there’s a lot of work there, so I have no concrete plans yet to build that.