Luke Palmer wrote:
>
> 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.
All this, I understand so far.
> 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
This, I don't understand. Why do we stop DoD here? Shouldn't we try
and free up some of the non-impatient objects?
[insert sound of gears turning]
OIC... if this is only for "sweep 0", then we haven't really *asked* to
try and free up the impatient objects; we've only asked to free up those
objects needing timely destruction.
> (and GC is not allowed to run, because that would result
> in a lot of wrongly murdered objects).
I don't understand this, though. Why would GC murder something, if that
something has been marked as live? Or do you mean, "if we stoped DoD in
the middle, then obviously don't follow it with the GC that normally
follows a DOD." That makes sense, though I think that skipping GC after
an *incomplete* DOD is a sufficiently obvious thing that it needn't be
mentioned ;)
> If there are dead objects in that list,
> DOD continues and does a full sweep.
When you say, "DOD continues," I assume you mean that we now drain the
"low priority" queue. I assume that it's *this* part of the DOD, when,
if we now encounter something with a high_priority flag set, we set the
high_priority flag of the object which can reach it. (Certainly not
when we're draining the high priority queue: all the things doing the
reaching there already have the high_priority flag set on them).
> 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.
Or, set a global (per-interpreter) flag indicating that an impatient
object has been destructed, and all high_priority_FLAGs need to be reset
at the beginning of the next DoD run.
> 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].
I do see a potential problem: Suppose that a highly visible PMC (one
reachable through lots of objects) is able to reach a PMC needing timely
destruction, and then a sweep 0 is done, and afterwards that highly
visible PMC changes so it no longer can reach the object needing timely
destruction. It still has it's high_priority flag set, and this will
propogate into the many things which will reach it, eventually going
into the root set.
And the more things which (incorrectly) end up in the high priority
queue instead of the low priority queue, the closer it's speed will be
to a regular sweep.
I can think of a workaround, but it would cost more memory.
Specifically, make the "priority" an actual number, which decreases with
the distance away from an object needing timely destruction (e.g., one
less than the max of the priorities of the objects we can reach). If an
object needs timely destruction, it's priority is fixed at MAX_INT.
PMCs which used to be able to reach things needing timely destruction,
but no longer can, will thus no longer have high priorities.
An advantage of this is that if an object needing timely destruction is
destructed, then we no longer need to clear the priorities of all PMCs;
most of the priorities (the ones leading to other objects needing timely
destruction) are still good, and the priorities going to the destructed
PMc will eventually decrease.
An improvment that can be made, if numeric priorities are used, would be
to make the "high priority queue" into an actual priority queue.
Although the algorithmic complexity will be higher than that of a
regular sweep, the objects needing timely destruction will be reached
faster, since the search is directed straight at them.
================
For any scheme (yours scheme, my suggested modification, or anything
else), a potential improvment to the speed of "sweep 0" would be to keep
a counter of the number of objects which need timely destruction that
have been marked as alive. Once this number reaches the total number of
objects needing timely destruction, we can abort the DOD.
--
$a=24;split//,240513;s/\B/ => /for@@=qw(ac ab bc ba cb ca
);{push(@b,$a),($a-=6)^=1 for 2..$a/6x--$|;print "[EMAIL PROTECTED]
]\n";((6<=($a-=6))?$a+=$_[$a%6]-$a%6:($a=pop @b))&&redo;}
