• 12
• 27
• 9
• 9
• 20

GC scheme for a new language/runtime

This topic is 3659 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I'm well on my way to completing a commercial/production grade language (compiler and runtime environment), but I'm stuck deciding what the final GC scheme should be. Right now I'm using a mixture of lazy reference counting without cyclic reference detection (so it is possible for garbage to accumulate without ever being considered garbage in some cases). I'm hoping others will have some interesting avenues of research or flat out suggestions for different or better schemes to use. Keep in mind that the final scheme needs to provide very high concurrency in the face of very large heaps (with potentially both large live heaps and large amounts of garbage), which ultimately means that the scheme itself will need to be able to release garbage in parallel on up to hundreds of threads at once.

Share on other sites
My current project (also designed for very high concurrency) relies on static analysis to generate garbage collection calls, combined with a reference-counting copy-on-write optimization of copy semantics. It uses an extension of the ML type system combined with region-based ownership analysis to determine the need for ownership transferral.

The reference-counting system is provably correct (the language does not allow mutation semantics and thus never generates cyclical values), and the rule set for ownership analysis also guarantees that garbage collection calls (those which add or remove references to objects) are correctly performed. Reference-counters will use a lock-less implementation for greater performance.

Share on other sites
Quote:
 Original post by ToohrVykMy current project (also designed for very high concurrency) relies on static analysis to generate garbage collection calls, combined with a reference-counting copy-on-write optimization of copy semantics. It uses an extension of the ML type system combined with region-based ownership analysis to determine the need for ownership transferral.

Heh; I actually wrote up a draft for something nearly identical a while back, but never got the time to play with it. I'd appreciate it if you could share how you merge all the cases of reference states at the end of a loop (normal termination immediately after test, or any number of early breaks); that's one thing I felt confident about in my model, but had a very hard time proving its correctness.

Share on other sites
Quote:
 Original post by WyrframeI'd appreciate it if you could share how you merge all the cases of reference states at the end of a loop (normal termination immediately after test, or any number of early breaks); that's one thing I felt confident about in my model, but had a very hard time proving its correctness.

The language contains no built-in loops. The while-loop is defined as:

public while = { c f i -> if c i then while c f (f i) else i }

So, typical rules for functions apply here as well. So, the region-type of the while function is:

public while : ('a{A} -> bool{B}){C} -> ('a{D*} -> 'a{E*}){F} -> 'a{G*} -> 'a{H*}

Where {X} denotes the argument belonging to a region parameter X which is read-only and does not outlive the function call, and {X*} denotes a parameter which is transferred (and thus may be modified as an optimization of a non-mutating operation, such as a swap or assignment).

Applied to the practical case (an insertion sort algorithm):
public isort = { v ->  Xh.for (2,size v) { i v ->     Xh.while { j,v -> j > 1 & v[j] < v[j-1] }             { j,v -> j - 1, Xh.swap j (j-1) v }              (i,v) } v }

[Edited by - ToohrVyk on February 16, 2008 12:33:34 PM]