Here comes that ever-reincarnating thread again, sorry. This is a proposal for an efficient solution to the timely destruction problem, which doesn't use refcounting, and fits in to the current scheme pretty well.
It is based on the fact that 90% of the time (or more), all objects needing timely destruction will be found live. It uses a priority method to try to find these objects quickly, and ceases if it does. This behavior is only carried out if the DOD was invoked by C<sweep 0>. There is an external list of objects needing timely destruction, which is not walked by DOD. Each object has a DOD_high_priority_FLAG. Each time an impatient object is created, its high_priority_FLAG is set. As everything is walked, if an object with this flag set is encountered, whichever thing referenced it also gets the flag set[1]. The DOD queue has two segments: high_priority and low_priority. high_priority is always drained and processed first. When this portion of the queue is completely drained, the external list of impatient objects is checked. If every object has been marked live, DOD terminates (and GC is not allowed to run, because that would result in a lot of wrongly murdered objects). If there are dead objects in that list, DOD continues and does a full sweep. When an impatient object is destructed, it might be good to reset all high_priority_FLAGs, except for other impatient objects, so there is nothing being walked at high priority that doesn't deserve it. That's it. The first few times C<sweep 0> is run, it will take just as long as C<sweep 1>, but the priorities will propogate down to things in the root set, and it will begin to speed up. And the algorithmic complexity never exceeds that of a regular sweep[2]. Luke [1] This probably has to be done when the object is enqueued, not dequeued. I don't know whether this impacts performance significantly. See [2]. [2] Although a single cycle of the algorithm becomes more complex, so it will slow things down a little when it's not doing any good. But at the expense of a little templating, these checks could be eliminated when the sweep wasn't triggered by C<sweep 0>.
