Steve Fink writes: > (I am way, way behind on reading this mailing list.) > > Assuming I understand your scheme properly, it seems incorrect to me. > > An object must be finalized during the first 'sweep 0' after it is no > longer reachable from the root set. (And no object may be finalized > while it is still reachable, but your scheme preserves that most > fundamental property of GC.) > > So let's say I have objects A, B, and C, where A references B references > C. C requires timely finalization. After one DOD run, we have B and C in > the high priority set. Now A becomes unreachable and we do a 'sweep 0'. > We scan the high priority set and reach C, so we finish. But there are > no references to B, and hence no references to C, and yet we did not > finalize C. Oops. > > Am I misunderstanding something?
Yes. See below. :-) > > [back pointers] > [nevermind] > > [append high priority to front rather than back] > > Ok, that seems simple enough that either there's some huge problem with > it, or it's a standard technique that everyone besides me already knows. > Which is it? :-) It's that it's exactly the same as my proposal, but with a simpler implementation[1]. The thing you misunderstood was that the queue is emptied each DOD run. So B couldn't get in the queue, because DOD would have to visit A first, and A couldn't be reached. The reason I proposed two seperate queues is so when the high priority one was drained completely, you could check against the list of impatient objects. But as Benjamin pointed out, you only need keep a counter: how many impatient objects exist/how many have been found. So there's no need to compilicate things with two seperate queues. Also as Benjamin pointed out, we could switch to a full-blown priority queue to improve performance in the long term. I don't much like that, not because of the memory, but because heap operations are quite a bit slower than queue operations for a little optimization like that. Maybe the object could reset its high priority flag if it doesn't parent any high priority objects.... Hmm. In any case, seeing that depth first case (see the footnote) has given me even more hope that I won't be agonizing over scope exit. Luke [1] Well, not I<exactly> the same. The high priority objects are traversed depth-first rather than breadth-first, which may actually turn out to be a win. Consider there only being one impatient object: after a few DODs, the high priority flags mark a "path" down the tree, since only the parent inherits the flag. If the search is depth-first, the DOD will run directly down the path toward the object.
