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.
