Garbage collectors

[helios]

Are there any languages out there with reference counting that also optionally perform what might be called "non-global garbage collections"? For example,

var tree = load_directory("/");
var subtree = tree.subdir("/etc");

Suppose tree points to a graph with reference-counted nodes and possibly some cycles. Rather than dealing with weak references and the like, I'd like to just do

delete tree;

And that would perform a collection only on the objects that are reachable from tree, but will ensure that subtree still points to something valid.

Does anything like this exist?

[LB]

Strangely, when learning new languages, the resource model and especially the memory model are often left undiscussed. If there is, you'll have to dig to find out.

[rapidcoder]

And that would perform a collection only on the objects that are reachable from tree, but will ensure that subtree still points to something valid.

Why would you ever need it? It would have to analyze all the other references from outside of the tree, to check which subtrees can be freed and which not.

[helios]

With reference counting, it's possible to check that any reachable object is not referenced by any unreachable object.

[NoXzema]

Sounds slow.

[helios]

Compared to what?

[LB]

I don't understand how it's different from in Java setting tree to null and then trying your hardest to force the garbage collector to run.

[helios]

Even if you manage to trigger the GC, there's no guarantee that any objects will actually be deallocated, even if they're not referenced by anything. I want deterministic destructors.

[LB]

If you want this kind of behavior for everything, your magic-delete operator will have significant overhead. If you just want to consider your special tree types, you're best off "dealing with weak references and the like".

[helios]

The point of having an explicit deallocation call is that the algorithm is too expensive to be used everywhere. However, it's only really needed to release cyclic structures. Reference counting works just fine with the other 90% of objects.

[Disch]

I want deterministic destructors.

Deterministic destructors and garbage collection seem mutually exclusive to me.

They only way they wouldn't be is if the programmer is in control of the GC... which defeats the entire point of having GC in the first place.

[LB]

You can make tree and subtree anchors and in the anchor destructors you can examine the underlying structure to detect cycles and the like and properly delete only the things which are no longer referenced by anchors. E.g. helios::cyclic_ptr and helios::cyclic_anchor.

[helios]

They only way they wouldn't be is if the programmer is in control of the GC... which defeats the entire point of having GC in the first place.

The idea I'm developing is a semi-automated memory management scheme where reference counting is used everywhere, but you can mark objects that may be able to see cycles. When marked objects have their refcount decremented, an alternative algorithm is used to detect which, if any, objects reachable from that object may be safely released. This algorithm is the algorithm used by tricolor marking GCs, with a variation to initially paint objects white.
It's not quite a GC, but it's related.
Order of destruction is deterministic relative to entire structures (i.e. the destructions of two non-overlapping graphs will not be overlapped). Internal objects may be destructed non-deterministically.

You can make tree and subtree anchors and in the anchor destructors you can examine the underlying structure to detect cycles and the like and properly delete only the things which are no longer referenced by anchors. E.g. helios::cyclic_ptr and helios::cyclic_anchor.

That's pretty much exactly it.

[rapidcoder]

Reference counting works just fine with the other 90% of objects.

Reference counting is a bad idea, because it doesn't scale on multicore architectures, contrary to mark-sweep or mark-compact GCs. Every pointer assignment is an interlocked increment/decrement, which is cache unfriendly and takes a significant amount of time compared to a simple (cached) memmove operation (taking typically less than 1 CPU cycle). Reference counting is good only for managing big objects whose references don't change very often.

Another problem, as noted above, reference counting does not reclaim cycles and for reclaiming cycles, you have to do some kind of a full-GC.

[helios]

it doesn't scale on multicore architectures

Don't care. My problem doesn't work with parallelism. That is, it's not parallelizable.
I'm willing to sacrifice that in exchange for determinism.

Every pointer assignment is an interlocked increment/decrement

Not exactly. In reality you can optimize away many refcount updates if you can prove the references to the left of the assignment have a shorter lifetime than an assumed original reference.
For example,

foreach (var obj in container){
    obj.foo();
}

There's no need to update obj.refcount twice every loop. The references in container won't just suddenly stop existing halfway through the loop (again, single thread. And either way it's the programmer's fault if they're modifying a structure as it's iterated).
On the other hand,

foreach (var obj in container){
    if (obj.foo())
        return () => obj.bar();
}

obj's refcount will need an update when obj is passed to the closure constructor, as will the closure's refcount.

Another problem, as noted above, reference counting does not reclaim cycles and for reclaiming cycles, you have to do some kind of a full-GC.

Yes, it does, and no, you don't.
http://c2.com/cgi/wiki?ReferenceCountingCanHandleCycles
My algorithm is a user-assisted version of this. Python does something similar, but since it's not user-assisted, a full GC is needed and collection of cyclic structures is no longer deterministic.

[helios]

As it turns out, it seems I've spent the last week designing Nimrod.
http://nimrod-lang.org/
Check it out. It seems to have most of the features I was looking for in a game scripting language.
* Statically typed.
* Deferred reference counting + optional, user-assisted cycle collection.
* Functional programming.
* Metaprogramming.
* Compiles to C (not entirely ideal, but still nice).
It's only missing better type inference, but it's otherwise very nice. I'll have to see what its FFI is like.