Sign in to follow this  

GC scheme for a new language/runtime

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
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.


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 this post


Link to post
Share on other sites
Quote:
Original post by Wyrframe
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.


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]

Share this post


Link to post
Share on other sites
ToohrVyk: ah, that does it. Loops via tail recursion. I was targetting a language that had Java-like language semantics, with some further restrictions, and while I did not have to support arbitrary-break from a switch clause (switch/case was disallowed with these restrictions), I did have to support arbitrary-break from inside loops in order to support the break statement itself, but more importantly to support exception throwing.

However, adding lifetime analysis to the type system seems like a natural step, considering we both did it. I think I like your notation better, though.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this