[Zodb-checkins] CVS: Packages/StorageGC - CyclicGC.py:1.16 GCableGraph.py:1.10
tim@digicool.com
tim@digicool.com
Thu, 26 Apr 2001 18:11:05 -0400 (EDT)
Update of /cvs-repository/Packages/StorageGC
In directory korak:/tmp/cvs-serv9685
Modified Files:
CyclicGC.py GCableGraph.py
Log Message:
Monster increase in the potential "suspendability" of CycleGC, i.e.
.resume's "effort" argument is now pretty potent. Effort counts the
number of objects visited internally (including repetitively by loops
in different phases of the algorithm). But in order to avoid running
pig-slow and making the code *completely* inscrutable, the remaining
effort isn't checked more often than once per visiting all the
immedediate successors of a single object. So it's a crude hint, not at
all a guaranteed upper bound.
--- Updated File CyclicGC.py in package Packages/StorageGC --
--- CyclicGC.py 2001/04/24 22:24:18 1.15
+++ CyclicGC.py 2001/04/26 22:11:03 1.16
@@ -83,13 +83,21 @@
# "effort" is a measure of how much work the caller wants .resume()
# to do before returning. A value <= 0 means .resume() should not
# return until analysis is complete (i.e., until .done() returns true).
+# When effort > 0, it's a crude hint to CycleGC about how much work the
+# storage wants to endure before regaining control. "effort" is taken
+# to be "the number of objects visited", whether internally or via
+# calling GCable.gcReferences(). When the number of objects visited
+# reaches "effort", CycleGC strives to suspend itself and return soon
+# after. *Some* phases of the algorithm cannot be suspended midstream,
+# though. For example, obtaining refcount info for the objects passed
+# to .start() completes entirely no matter how small effort may be, and
+# so does the final internal linear pass to collect garbage. So
+# "effort" cannot be viewed as any sort of guaranteed upper bound. Most
+# of the time, the granularity is no finer than the number of
+# immediate successors of whichever object CycleGC is examining at the
+# time.
# It's OK to call .resume() when .done() returns true, although there's
# no point to doing so.
-# XXX TODO "effort" has a very crude meaning now: # of internal stages
-# XXX TODO Define what effort *means*; e.g., perhaps an approximation
-# XXX to the maximum number of .gcReferences() calls the storage
-# XXX wants to endure before regaining control? milliseconds
-# XXX elapsed? Not yet clear what would be most useful.
#
# CycleGC.done() -> bool
# Return true when analysis is complete, of all objects ever passed to
@@ -119,11 +127,33 @@
# cyclic RC algorithms. Its main advantage over the latter is that it can
# be written in a natural way without recursion. Recursion is expensive in
# Python, and much harder to rework into an incremental framework.
-# XXX This isn't incremental either, yet -- that's a PITA even without
-# XXX recursion, and will make the algorithm 10x more brittle. Need a great
-# XXX test suite first.
###########################################################################
+# Incrementalism.
+# We're faking a coroutine approach "by hand" here, so the code is much
+# more involved than a straighforward non-stop implementation would be.
+#
+# The ability to "suspend" is implemented at two levels:
+#
+# At the top level, major phases of the algorithm are each in their own
+# method, and are considered to be "opcodes" for a very high level virtual
+# collection machine. The .resume() method works through a list of these
+# opcodes, dispatching to them one at a time, in order, via incrementing a
+# virtual instruction pointer (just an index into the _workflow list).
+# Each opcode decrements _worktodo by a measure of the amount of work it
+# has done, and .resume's eval loop returns to the caller when "enough"
+# work has been done. This approach retains *some* comprehensibility for
+# the overall strategy.
+#
+# Individual opcodes may or may not choose to suspend themselves; some do
+# and some don't. The usual suspending case is an algorithm running an
+# outer loop, that can stop itself between outer iterations. In that case
+# it saves the info it needs to resume itself in _resume, and returns
+# "false" to the eval loop to let the latter know it's not yet finished (so
+# the eval loop will invoke the *same* opcode again when .resume() is next
+# called).
+
+###########################################################################
# Indices into object descriptors.
# An object descriptor is a 3-list of the form [OBJ, RC, ADJRC].
# A list is used instead of an object to slash the space overhead; a tuple
@@ -204,9 +234,21 @@
# self._workflow.
self._stage = 0
+ # The maximum amount of "work" we want to do before suspending.
+ self._worktodo = 0
+
+ # When an opcode suspends before it's complete, it saves whatever
+ # info it needs to resume into _resume. "None" is reserved to
+ # mean "there's no resumption info -- if I'm called when _resume
+ # is None, it must be a fresh call".
+ self._resume = None
+
# Is it safe for the storage to delete objects and references?
self._is_decref_safe = 1
+###########################################################################
+# Public API methods -- the implementation of the CycleGC interface
+
def start(self, objs):
"""Objs is a list of oids that *may* be in trash cycles.
@@ -229,26 +271,32 @@
"""Resume analyzing the graph reachable from the .start() objects.
Optional arg 'effort' is an int. If <= 0 (the default), don't
- return until analysis is complete. XXX Else ...
+ return until analysis is complete. Else it's a crude measure of
+ the maximum number of objects you want CycleGC to visit before
+ returning control. This is not a guaranteed upper bound: some
+ phases of CycleGC cannot be interrupted mid-stream. But CycleGC
+ will *try* to return soon after visiting "effort" objects, if and
+ when it can.
"""
- # print "Entering", effort, self._stage
+ # print "Entering", effort, self._stage, self._worktodo
if self.done():
return
if effort <= 0:
- worktodo = _sys.maxint
+ self._worktodo = _sys.maxint
else:
- worktodo = effort
+ self._worktodo = effort
try:
- while worktodo > 0:
- worktodo -= 1
- # Bump the virtual program counter and dispatch on the next
- # "opcode".
- stage = self._stage
- self._stage = stage + 1
- self._workflow[stage]()
+ while self._worktodo > 0:
+ # Dispatch on the next opcode.
+ is_opcode_finished = self._workflow[self._stage]()
+ if is_opcode_finished:
+ self._stage += 1
+ self._resume = None
+ if effort <= 0:
+ self._worktodo = _sys.maxint
except _VM_is_done:
pass
@@ -270,7 +318,7 @@
self._back_to_stage0()
self.resume(effort <= 0 and -1 or worktodo)
- # print "Leaving", self._stage
+ # print "Leaving", self._stage, self._worktodo
def done(self):
"Return true when the analysis is complete, false if more to do."
@@ -296,38 +344,31 @@
"""
return self._is_decref_safe
-
- def _build_descriptors(self, objs):
- "Build descriptors for the passed-in objects."
- assert len(self._allobjds) == 0
- assert len(self._obj2d) == 0
- if objs:
- self._is_decref_safe = 0
- for x in objs:
- # Note that _get_initial_info() weeds out duplicates.
- self._get_initial_info(x)
-
- def _get_initial_info(self, obj):
- """Return descriptor for obj, building a new one if obj is new.
-
- Weed out duplicates. If not already seen, build descriptor, append
- to _allobjds, and map obj to it via _obj2d.
- """
-
- d = self._obj2d.get(obj)
- if d is None:
- rc = self._get_storage_rc(obj)
-
- d = [None] * NUM_DESCRIPTOR_SLOTS
- d[OBJ] = obj
- d[RC] = rc
- d[ADJRC] = rc
-
- self._obj2d[obj] = d
- self._allobjds.append(d)
-
- return d
+###########################################################################
+# VM "opcodes".
+#
+# These must decrement _worktodo by the amount of work they do, and aim
+# toward "suspending" themselves "soon after" _worktodo reaches 0.
+#
+# Except for opcodes that change the instruction pointer (_stage)
+# themselves, they should return true (1) if and only if their work is
+# complete. If an opcode needs to suspend (because _worktodo becomes <= 0),
+# it should save whatever info it needs to resume itself (in _resume), and
+# return false (0).
+#
+# Immediately upon entry, an opcode that's capabable of suspending should
+# check _resume: if it's None, this is the "first call" to the opcode,
+# else _resume contains whatever the opcode put there when it last
+# suspended.
+#
+# Note: Returning false prevents the eval loop from advancing the
+# instruction pointer, which is why an opcode that changes the ip itself
+# must return false.
+
+ # Total cost is roughly the number of objects in the transitive closure,
+ # plus the number of outgoing references from each such object.
+ # Suspendable, but only once per object in the transitive closure.
def _build_transitive_closure(self):
"""Build transitive closure; adjust internal refcounts.
@@ -338,16 +379,28 @@
in the transitive closure.
"""
+ i = self._resume or 0
+ allobjds = self._allobjds
+
# Subtle: self._allobjds grows *during* the loop, as children are
# appended the first time they're seen. This is a slick way to
# implement a non-recursive breadth-first traversal, leaving every
# reachable object exactly once in the _allobjds list.
get_initial_info = self._get_initial_info
- for d in self._allobjds:
+ while i < len(allobjds) and self._worktodo > 0:
+ d = allobjds[i]
+ i += 1
+ self._worktodo -= 1
for child in self._getkids(d[OBJ]):
dchild = get_initial_info(child)
dchild[ADJRC] -= 1
+ self._resume = i
+ return i >= len(allobjds)
+
+ # Total cost = number of nodes visited, depends on the graph structure.
+ # Suspendable, but only between examining nodes in _allobjds.
+
def _propagate_external_refs(self):
"Restore refcounts from objects that are externally reachable."
@@ -361,9 +414,17 @@
# objects, and for those objects R that are reachable from outside,
# re-increment the refcounts on R's successors.
+ i = self._resume or 0
+ allobjds = self._allobjds
+ n = len(allobjds)
+
mistakes = [] # The algorithm isn't omniscient until the end.
- for d in self._allobjds:
+ while i < n and self._worktodo > 0:
+ d = allobjds[i]
+ i += 1
+ self._worktodo -= 1
+
adjrc = d[ADJRC]
assert adjrc != ADJRC_ISFREE
@@ -374,6 +435,7 @@
# guess and incrememt its kids' refcounts too.
self._increment_children(d[OBJ], mistakes)
while mistakes:
+ self._worktodo -= 1
nottrash = mistakes.pop()
self._increment_children(nottrash, mistakes)
@@ -386,43 +448,12 @@
# refcount info. Just give up.
raise _TopologyError("Adjusted refcount %d < 0 for OID %s"
% (adjrc, repr(d[OBJ])))
-
- def _increment_children(self, obj, mistakes):
- "Increment obj's immediate successors' refcounts by 1 each."
- # Here's the subtle part: objects that _propagate_external_refs()
- # have *already* seen, that had an adjusted refcount of 0, were
- # marked ADJRC_ISFREE. But if such an object is a child of this
- # obj, it's reachable from an externally reachable object after all,
- # so calling it ADJRC_ISFREE was a mistake. Such objects are pushed
- # on the "mistakes" stack for the caller to propagate too, and we
- # set their ADJRC field back to 1 here.
+ self._resume = i
+ return i >= n
- # Note: If a child happens to have a refcount of 0, that's nothing
- # special: that just means _propagate_external_refs() hasn't gotten
- # to it yet, and, since we incrememt its refcount here,
- # _propagate_external_refs() will never know it had a zero refcount
- # (so it will never be marked ADJRC_ISFREE to begin with -- there's
- # no mistake to undo then).
-
- # Another subtlety: Since:
- # a) only objects already traversed by _propagate_external_refs()
- # can be marked ADJRC_ISFREE, and that routine visits each object
- # exactly once;
- # b) only objects marked ADJRC_ISFREE can get pushed on the mistakes
- # stack here;
- # c) when pushing an ADJRC_ISFREE object on the mistakes stack here,
- # we take away its ADJRC_ISFREE status
- # then once an object loses ADJRC_ISFREE status (#c) it can never
- # regain it (#a), so that #b guarantees an object will never be
- # pushed on the mistakes stack more than once. That property is
- # crucial, else we could be counting some object more than once.
-
- for d in self._get_kids_descriptors(obj):
- if d[ADJRC] == ADJRC_ISFREE:
- d[ADJRC] = 0
- mistakes.append(d[OBJ])
- d[ADJRC] += 1
+ # Cost = len(_allobjds).
+ # Cannot suspend.
def _extract_garbage(self):
"""Find trash in the transitive closure and pass on to gcTrash().
@@ -432,6 +463,7 @@
"""
result = []
+ self._worktodo -= len(self._allobjds)
for d in self._allobjds:
if d[ADJRC] != ADJRC_ISFREE:
continue
@@ -453,6 +485,10 @@
self._is_decref_safe = 1
if result:
self._storage.gcTrash(result)
+ return 1
+
+ # Cost = len(_pending).
+ # Cannot suspend.
def _start_next_batch(self):
"Start next batch of work (if any)."
@@ -462,30 +498,135 @@
temp = self._pending
self._pending = []
self._build_descriptors(temp)
+ return 1
+
+ # Cost = 0.
+ # Cannot suspend.
def _stop_if_finished(self):
if self.done():
raise _VM_is_done
+ return 1
+ # Cost = 0.
+ # Cannot suspend.
+
def _back_to_stage0(self):
"Restart the virtual machine."
self._stage = 0
+ self._resume = None
+ # This is a special case: despite that the opcode is finished,
+ # return false. This is because we changed the instruction
+ # pointer ourself, so don't want the VM to increment it.
+ return 0
+
+###########################################################################
+# VM helpers.
+
+
+ # Cost = len(objs).
+
+ def _build_descriptors(self, objs):
+ "Build descriptors for the passed-in objects."
+
+ assert len(self._allobjds) == 0
+ assert len(self._obj2d) == 0
+ if objs:
+ self._worktodo -= len(objs)
+ self._is_decref_safe = 0
+ for x in objs:
+ # Note that _get_initial_info() weeds out duplicates.
+ self._get_initial_info(x)
+
+
+ # Cost = 0.
+
+ def _get_initial_info(self, obj):
+ """Return descriptor for obj, building a new one if obj is new.
+
+ Weed out duplicates. If not already seen, build descriptor, append
+ to _allobjds, and map obj to it via _obj2d.
+ """
+
+ d = self._obj2d.get(obj)
+ if d is None:
+ rc = self._get_storage_rc(obj)
+
+ d = [None] * NUM_DESCRIPTOR_SLOTS
+ d[OBJ] = obj
+ d[RC] = rc
+ d[ADJRC] = rc
+
+ self._obj2d[obj] = d
+ self._allobjds.append(d)
+
+ return d
+
+ # Cost = the # of obj's successors.
+ def _increment_children(self, obj, mistakes):
+ "Increment obj's immediate successors' refcounts by 1 each."
+
+ # Here's the subtle part: objects that _propagate_external_refs()
+ # have *already* seen, that had an adjusted refcount of 0, were
+ # marked ADJRC_ISFREE. But if such an object is a child of this
+ # obj, it's reachable from an externally reachable object after all,
+ # so calling it ADJRC_ISFREE was a mistake. Such objects are pushed
+ # on the "mistakes" stack for the caller to propagate too, and we
+ # set their ADJRC field back to 1 here.
+
+ # Note: If a child happens to have a refcount of 0, that's nothing
+ # special: that just means _propagate_external_refs() hasn't gotten
+ # to it yet, and, since we incrememt its refcount here,
+ # _propagate_external_refs() will never know it had a zero refcount
+ # (so it will never be marked ADJRC_ISFREE to begin with -- there's
+ # no mistake to undo then).
+
+ # Another subtlety: Since:
+ # a) only objects already traversed by _propagate_external_refs()
+ # can be marked ADJRC_ISFREE, and that routine visits each object
+ # exactly once;
+ # b) only objects marked ADJRC_ISFREE can get pushed on the mistakes
+ # stack here;
+ # c) when pushing an ADJRC_ISFREE object on the mistakes stack here,
+ # we take away its ADJRC_ISFREE status
+ # then once an object loses ADJRC_ISFREE status (#c) it can never
+ # regain it (#a), so that #b guarantees an object will never be
+ # pushed on the mistakes stack more than once. That property is
+ # crucial, else we could be counting some object more than once.
+
+ for d in self._get_kids_descriptors(obj):
+ if d[ADJRC] == ADJRC_ISFREE:
+ d[ADJRC] = 0
+ mistakes.append(d[OBJ])
+ d[ADJRC] += 1
+
+
+ # Cost = 0.
+
def _clear_current_work(self):
"Forget everything about the current start set."
self._obj2d.clear()
self._allobjds = []
self._is_decref_safe = 1
+ # Cost = the # of obj's successors.
+
def _getkids(self, obj):
"Return list of obj's immediate successors."
- return self._storage.gcReferences(obj)
+ result = self._storage.gcReferences(obj)
+ self._worktodo -= len(result)
+ return result
+ # Cost = the # of obj's successors.
+
def _get_kids_descriptors(self, obj):
"Return list of descriptors of obj's immediate successors."
result = []
+ children = self._storage.gcReferences(obj)
+ self._worktodo -= len(children)
getd = self._obj2d.get
- for child in self._storage.gcReferences(obj):
+ for child in children:
d = getd(child)
if d:
result.append(d)
@@ -529,6 +670,8 @@
# this specific example, we'll eventually discover that B's
# refcount has changed).
return result
+
+ # Cost = 0.
def _get_storage_rc(self, obj):
"Return the storage's idea of obj's current refcount."
--- Updated File GCableGraph.py in package Packages/StorageGC --
--- GCableGraph.py 2001/04/24 22:24:18 1.9
+++ GCableGraph.py 2001/04/26 22:11:03 1.10
@@ -130,7 +130,7 @@
gc.start(roots)
assert gc.safeToDecref() == (len(roots) == 0)
while not gc.done():
- gc.resume(1)
+ gc.resume(100)
assert gc.safeToDecref()
finish = clock()
print "and done with gc, in %.3f seconds" % (finish - start)