Hi, It seems to me that this doubles the memory requirements for any > aggregate compared to (1).
Not quite, There is only 1 word more (the pointer to the untagged aggregate data, aka Implementation<Foo>). Besides, solution 1 is not acceptable for Mozart, because sometimes data must mutate, and change their type. And sometimes the mutated type occupies more memory than the previous one. So, following me, it does not make sense to compare our model to model 1. > It also means that the tag for an aggregate > is repeated everywhere it is referenced. No because only one node is allowed to point to a given Implementation<T>. Other nodes that wish to point to that Implementation<T> have to be a Reference to the former node. However, well, yes, you have those extra Reference types everywhere. So in some sense the tag for an aggregate is indeed repeated everywhere it is referenced. > Also, since you allow pointers > into an aggregate, copying garbage collection may well end up being > inflationary: if GC reaches a word hosted in an aggregate before the > aggregate is itself GCed, it will create a non-hosted copy of that word > in the TO heap; then when the aggregate is GCed, the embedded word in > question will somehow have to refer to the copy previously made; but the > net result, is that GC has created a TO heap with 1 more word that the > FROM heap. IIRC, mozart (the old generation) also had this issue, but > only for optimized unbound variables; it solved it by detecting > embedding in an aggregate by scanning backwards for the aggregate's > initial tag, and gcing the aggregate. But, since your aggregates are > untagged, that option is not open to you. > This is true. Though I'm sure that the old VM did better. To mitigate this problem, we implement the GC with some "heuristics" that help to prevent this issue. Here is how our GC works. The GC owns 4 lists of "things remaining to GC": a list of threads (Runnable's, to be precise), one of StableNodes, one of UnstableNode, and one of "StableRefs", aka StableNode*. We call them threadsToGC, stableNodesToGC, unstableNodesToGC and stableRefsToGC. Each element of this list contains two information: where the data comes from (from) and where the data must be copied to (to). Initially, the lists are empty. We populate them with roots of garbage collection. In Mozart, the roots of GC are the list of *runnable* threads. So we duplicate the list of runnable threads in the new memory space. Then populate the list threadsToGC with all the pairs (old thread, entry in the new list of runnable threads). Now, the GC algorithm works as follows. It repeats the following steps until all four lists ToGC are empty: - If threadsToGC is not empty, then pop an item, and create a new Thread with its GC constructor, giving it the old thread as a parameter. This will, as a side effect, add elements in unstableNodesToGC for all the registers, and stableRefsToGC for all the references to the Abstractions in the stack frames. This step never inflates memory. - Otherwise, if stableNodesToGC is not empty, pop an item, and use make<T> on the TO node to use its GC constructor. For aggregate types, this GC constructor will add elements in the ToGC lists (all four lists are concerned here; for example a Cell will add unstableNodesToGC, a Cons will add stableNodesToGC, a Variable will add threadsToGC, and maybe one day we'll have a type that adds stableRefsToGC). This step never inflates memory, because if we need to make there a Reference to an UnstableNode, the new StableNode we're creating will acquire the contents of the UnstableNode, and make that UnstableNode a Reference to itself. - Otherwise, if unstableNodesToGC is not empty, we do exactly the same as for stableNodesToGC. However, this time, if we have to copy a non-copiable UnstableNode inside this one, then we have to make a reference to it. But we have two UnstableNodes, so neither can be a Reference to the other. At that point we need indeed to inflate the memory with a new StableNode, and make the two UnstableNodes be Reference to that new StableNode. - Otherwise, stableRefsToGC is not empty. If the pointed StableNode has already been GCed (because we reached it earlier from another path in the graph), then we can simply update the StableNode* to point to the new StableNode. However, if the StableNode had not been already GCed, then we need to create a new StableNode for it now, point to that StableNode, and execute the same as in step 2. Hence, only the last two steps can inflate memory. By giving a higher priority to the first two steps (and most importantly the second one), we hope that things that must be referenced will be acquired by StableNodes before they are referenced by two UnstableNodes, and before we reach a StableRef to them. We have no guarantee on that, of course. And actually we know that sometimes the GC *will* inflate memory in some places. But I do not think we can do better, without performing a big first pass on the graph only to register all nodes that must be GCed (i.e., populate the four lists ToGC), and only afterwards doing a second pass with the algorithm above. Sébastien
_________________________________________________________________________________ mozart-hackers mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-hackers
