Maybe, but does it support separate heaps for each thread? I've heard quite a bit about it but not seen the overall design.
Currently my (unimplemented) plan is, memory is kept in managed heaps, which are handled by a mark-and-sweep collector (can't use semispace or variants for reasons below; at least, I don't think I can use semispace). If a message is passed to another thread, the memory of that message (and every other managed area it refers to) is moved from "managed" space to "shared" space, which is reference counted (the references counted are from threads to shared objects, so circular references are impossible). Objects in "shared" space are immutable (and can thus be accessed lock-free). If a thread attempts to mutate a shared object, instead all shared objects still referenced by that thread are copied to managed space (copy-on-write), the shared objects are released (decrement refcount by 1, free if zero), and the managed copy is mutated (we copy all of them because other shared objects might refer to the shared object being mutated).
Note that "managed" space and "shared" space are not separate areas of memory: they are actually two sets of pointers, so moving an area of memory is just moving a pointer from one set to the other (very cheap). The reason I think I can't use a copy collector is that a shared memory object might end up being located between two managed objects, and the shared object can't be moved without disturbing all the other threads that might be referring to it.
Shared objects are OK to refcount because we're refcounting from threads to shared objects. A thread might have 1000 references to a shared object, but it just counts as 1. Only when the thread GC's and determines that the shared object is not marked does it actually decrement the refcount.
Marks are normally kept in a bool with the memory area, if the memory is managed. If it's shared, then the marking information is kept by membership in a marked_and_shared set while marking (in order to preserve the invariant that shared objects are immutable). Sweeping involves traversing both the managed and the shared set; if the managed set memory area is not marked, then it is freed and removed from the set, etc. If the shared set memory area is not in the marked_and_shared set, then it is released (decrement refcount, free if zero) and removed from the set, etc.
There is also a "light" GC which just sweeps the managed set. Crucially, because shared objects are immutable, they cannot point to managed objects, so mark-and-sweep on only managed objects won't have the overhead of referring to marked_and_shared objects.
(and, err, that's pretty much most of my thinking with regards to having separate heaps being used by various threads. I actually have some of the messier details written down in a text file, anyone interested can post their email addresses ^^)
Personally, I think we need more shared-nothing VM's, not more shared-memory VM's.
Okay, now I've been looking at things, and it seems my solution is actually quite suboptimal.
Basically the main thing I'm trying to solve is the copying of memory of messages when an object is sent across processes. Hence my use of shared immutable data, which is only copied if necessary.
However the problem is really something like this:
; process A
(let v (some-value)
(==> B v)
(==> B v))
Conceptually, process B receives two messages that are separate from each other (i.e. two different copies of v). This will allow process B to mutate and do anything to its copy, without worrying that the next message it receives gets mutated also, just because process A happened to send the same data again.
This can actually happen more often than you think. Consider the case where a process serves as an STM-style container:
(def container (state)
(while t
(<==
('put obj)
(= state obj)
('query pid)
(==> pid state))))
Now suppose process A sends an object to process B for storage in the container held by B. Then it queries B, expecting to receive a copy of the object it receives:
A ==> object ==> B
A ==> query ==> B
A <== object <== B
This means that B might send an object which A already has (instead of a copy of the object, as we expected), if we're going to use the "shared" concept I had above.
My solution to this was to check the destination's shared set and see if the message to be sent was in the destination's shared set, and to send a copy the object if it is in the destination's shared set. Unfortunately this checking takes O(N log M) if sets are red-black trees, with N = number of objects in the message and M = number of objects in the destination's shared set, plus an optional additional O(N) to copy if the checking shows that the destination already has a copy of an object to be sent. As opposed to O(N) if we just copy it anyway.
Direct (deep-)copy seems a better solution then: it will also let you use a copying garbage collector or anything else without worrying about immutable shared copies. You could even use different GC strategies on a per-thread basis (I don't know how much this would be helpful, though...).
The bit that's bothering me about copy collectors is that it's somewhat difficult to handle cleanup/finalization. For example, it would be neat if the VM automatically closed any file handles you happened to have dropped, or to automatically terminate processes that are waiting for a message (without a timeout) and whose pid's have been dropped (so that you can return a pid as a "data structure" with impunity, and still have the process be garbage collected when the data structure loses scope).
I think I've hit upon a possible way of handling this though. A copy collector needs to put up to-pointers anyway; I think it may be possible to have the to-pointers as part of the object. The to-pointers default to NULL. When a heap is released (i.e. after its contents have been copied to another heap), the heap inspects its held objects. Any objects whose to-pointers are NULL are finalized/deleted; in effect, the to-pointers become really expensive mark bits.
> You could even use different GC strategies on a per-thread basis (I don't know how much this would be helpful, though...).
Hey, that's an idea... ^^! Possibly make things generational too, if the heap size grows (I think this is how the Erlang BEAM VM does it)
Do you think to-pointers are expensive in terms of space or of runtime(i.e. scanning the entire heap to look for them)? In term of space they aren't really expensive because you can reuse the space allocated by the object: as an example if you move a cons cell (2 words) you can use its first word to hold the new address of the cell.
I've implemented a simple copying GC in C, if you want to have a look at it: http://github.com/stefano/tush/tree/master/gc.c
Actually the other problem I'm thinking of is the "size" of an object in the heap under management. I'm currently using C++ for the memory management stuff, and the base type Generic requires a virtual getsize() member function which just returns sizeof(Type); most C++ implementations just allocate a single vtable for all virtuals, and of course I also have recursive marking as virtual functions of Generic. Basically I am overloading the vtable of the objects to also encode the size of individual types.
(the vtable also serves as my "type code", and is probably better thought of that way)
So I can't safely replace a Generic object on the heap with a ToPointer object, because I'd lose access to the size (i.e. I lose the type code, which I'm using to determine the size). This means I can't sweep and finalize afterwards. The alternative is to keep the size separate from the type code/vtable, but then for each object I end up storing a size_t, which on most systems is probably the same size as a Generic* - so I don't save it either.
So basically my options are:
type code (automagically inserted by C++ as the vtable)
to-pointer
data
or:
size
type code
data
Reusing the space of the object is possible, but to differentiate a to-pointer from a "real" object, I need to replace the type-code anyway, so I lose the size information.
Edit: Okay, I've been trying to hack through your posted GC. I don't quite get how the type code is encoded - is the heap split into regions? You seem to be masking the pointer itself to get the type.
Okay, I've figured bits of your GC out after sleeping, it seems that the pointer is a typed pointer. A pointer with a type of extended_tag (?) includes the type with the memory area, and this type is overwritten with a broken_heart type to turn it into a to-pointer.
However I intend to use the same copy-algorithm for message passing, so I can't overwrite the tag/type code and the data just because I've copied it, since the original could be reused.
Or maybe I should actually use a different routine for message passing and GC.
> However I intend to use the same copy-algorithm for message passing
In this case, as you've already said, you can't overwrite the orginal type and you have to reserve extra space for the to-pointer (this means one extra word for every allocated object). This way another problem arises: you have to be sure that the to-pointer is clear every time you start a copy this is automatic after a GC, but not after a copy for message passing. This means that after every message passing, the whole heap must be scanned.
> Or maybe I should actually use a different routine for message passing and GC.
I think this is the best solution: passing a message and copying an object during garbage collection are enough different to make them distinct.
Yes, you're right. Looks like I'll end up having the message-passing use a std::map<> instead (which has O(log N) for each lookup, averaging O(N log N) for all memory areas involved in the message), and leave the to-pointers for the semispace destructor to determine which objects need to be cleaned up. Overhead either way.
Or again use a mark and sweep with copying instead of sharing of objects ^^. Well, not much different.
