So I'm still playing with ways to (a) lower reference count overheads and (b) make more continuous trades between various sorts of expense and (c) provide ways for programmers to say what they want. I had a whacky idea that may not work, but here it is.
Observation 1: RC-immix doesn't really collect objects. It collects blocks. The reference counting mechanism causes counts on the objects to go up and down, and the RC decrements in turn cause counts on the lines to go down, but at the end of the day a block doesn't go back into the recycled or free allocation queues without being considered as a block. Nursery blocks are a special case exception to that statement. Observation 2: If we choose to do so, tracing a 32KB block can be done pretty quickly. So for just a moment, I want to play with the idea that we can set a collection policy on a block-by-block basis. Some blocks are traced and some are reference counted. Here is how this would work: 1. The deferred RC mechanism proceeds as described in RC-immix. Allocating an object proceeds in exactly the same way, and objects are migrated to blocks in the same way. 2. When an object in block B1 is integrated, we check each reference to see if the target object lives in some other block B2. If so: - We mark the source object as a BLOCK LEAF of B1 - We mark the target object as a BLOCK ROOT of B2. In practice, we would probably mark the lines as opposed to the objects. The point is: if we track the block leaves and block roots, we get a bunch of useful consequences: 1. We can do internal tracing of blocks as a separate (and potentially incremental) problem on a block-by-block basis. 2. Two blocks can have different reclamation policies (tracing or RC or deferred-RC or whatever). 3. If a block contains no modified objects - which we can track at integration time - we need not consider any "interior" object during tracing. 4. Similarly, we can implement a two-tier cycle detection algorithm. An object-level cycle is only possible within a block-level cycle. 5. This *may* give us a coherent account of how policies can safely be mixed in a system like URC, for example mixing counted allocation pools and traced allocation pools in a single runtime. I may be over-optimizing and/or over-thinking here. I suspect that I've just gone and re-invented cross-generation reference tracking in an RC framework. I also suspect that something like this would motivate using a larger block size. Reactions?
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
