Better still, the two schemes appear to be usable in parallel, which means that even in a lock-based runtime we can elect to use the zero-retag-copy protocol for small objects where the cost of an interlocked operation to aquire the lock might be excessive.
Just to document it before I forget why it's okay, there is a race in the zero, retag, rewrite protocol. The problem is that the collector may still be traversing under the old tag while new references are being written under the new tag. The reason this is okay is that the race is inherent. Even if the tag is not changing, the collector may be looking while the mutator is writing, and may thereby pick up pointers that are already stale by the time the object is marked. The usual solution for this is for the mutator to keep some sort of list of objects it is mutating, and for the collector perform a "copy-then-check-for-mutate" protocol. If the collector discovers a racing mutate, it re-starts the copy. The thing to notice is that under these conditions the initial copy becomes non-live before it is (recursively) traced. Any other policy might result in missed objects during the tracing phase. This means, in particular, that any old copy of the tag likewise becomes non-live, with the consequence that the concurrent race management protocol extends naturally to the zero-retag-copy approach. The change is that the collector must now consider the possibility of changes to the tag itself and re-copy the tag. In the absence of embedded discriminator tags that are relevant to GC, this was not previously necessary. DEFREPR, however, presents some novel challenges, because the tag is not contiguous, and portions of the tag in one variant may overlap with references in another variant. One consequence is that it may not be possible to zero out the references in both the old and the new variant. It is straightforward (though a nuisance) to analyze those cases of DEFREPR leg pairs for which transition is possible. If a sequence of transitions can be constructed from any leg to any other leg, then we can still use these tricks. Now that I think on it, there is a similar problem with the lock strategy. As I say, the analysis is feasible. The challenge is to describe, as a matter of specification, what the constraints are on the legal DEFREPR shapes. shap
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
