[Zodb-checkins] CVS: Packages/StorageGC - GCableGraph.py:1.8

tim@digicool.com tim@digicool.com
Mon, 23 Apr 2001 01:12:24 -0400 (EDT)


Update of /cvs-repository/Packages/StorageGC
In directory korak:/tmp/cvs-serv12474

Modified Files:
	GCableGraph.py 
Log Message:
Added some "by eyeball" tests to get an initial feel for bugs and performance.
These tests construct graphs wholly at random.  This is to prevent my biases
and blind spots from overlooking systematic mistakes.  OTOH, bad cases for
gc algorithms can be exceedingly rare and require major brainpower to provoke.
I'm working on that <wink>, but at this point I've gone over the code so
often that I *must* be blind to any flaws that remain.

Anyway, so far as it goes, good!  No bugs popped up.

No surprises in performance yet, either:  When the graph is dense (rich with
connections), CycleGC is running at about half the speed of the M&S algorithm.
This is actually very good, because M&S is looking at the graph structure directly,
while CycleGC gets all its info indirectly thru layers of function and method
calls.  So even in the worst cases CycleGC is running OK.  For random graphs
more of the sparser expected nature, CycleGC runs arbitrarily faster than M&S,
depending on how sparse the graph is and the luck of the draw.  Of course in
these cases CycleGC only finds *some* of the trash, while M&S continues to find
all of it.



--- Updated File GCableGraph.py in package Packages/StorageGC --
--- GCableGraph.py	2001/04/21 05:41:01	1.7
+++ GCableGraph.py	2001/04/23 05:12:23	1.8
@@ -99,39 +99,70 @@
 
 from CyclicGC import CycleGC
 
-g = RCGraph()
-g.addedge(1, 2)
-g.addedge(2, 3)
-g.addedge(3, 4)
-g.addedge(3, 4)
-g.addedge(3, 3)
-g.addedge(3, 3)
-g.addedge(3, 3)
-g.addedge(4, 5)
-g.addedge(5, 1)
-g.addedge(5, 6)
-g.addedge(5, 7)
-g.addedge(5, 8)
-g.addedge(6, 7)
-g.addedge(7, 6)
-g.addedge(7, 8)
-g.addedge(8, 7)
-g.addedge(8, 6)
-g.addedge(6, 8)
-#g.addedge(10, 2)  # should stop any trash collection
-g.dump()
-
-gc = CycleGC(g)
-for s in ([1], [2], [3], [], [4], [2,2], [5], [6, 7, 8], [1, 8],
-          range(1, 9)*2):
-    print
-    print "Trying", s, "as the start list."
-    g.clearTrash()
-    gc.start(s)
-    while not gc.done():
-        gc.resume(1)
-    trash = g.getTrash()
-    print "    trash found:", trash
-    alt_trash = g.altTrash(s)
-    if trash != alt_trash:
-        raise ValueError("OOPS! altTrash returned %s" % alt_trash)
+from random import choice as _choice
+
+class RandomTest:
+    def __init__(self, numnodes, edgedensity, numrootset):
+        self.nodes = range(numnodes)
+        self.edgedensity = edgedensity
+        self.numrootset = numrootset
+
+    def runone(self):
+        from time import clock
+        graph = RCGraph()
+        nodes = self.nodes
+        for n in nodes:
+            graph.addnode(n)
+        for i in xrange(int(len(nodes) * self.edgedensity * len(nodes))):
+            graph.addedge(_choice(nodes), _choice(nodes))
+        roots = []
+        for i in xrange(self.numrootset):
+            roots.append(_choice(nodes))
+
+
+        # graph.dump()
+        print "Trying", roots, "as the start list."
+        graph.clearTrash()
+        gc = CycleGC(graph)
+
+        print "    starting gc ...",
+        start = clock()
+        gc.start(roots)
+        while not gc.done():
+            gc.resume(1)
+        finish = clock()
+        print "and done with gc, in %.3f seconds" % (finish - start)
+
+        trash = graph.getTrash()
+        print "    trash found:", trash
+
+        print "    starting M&S gc ...",
+        start = clock()
+        alt_trash = graph.altTrash(roots)
+        finish = clock()
+        print "and done with M&S gc, in %.3f seconds" % (finish - start)
+
+        if trash != alt_trash:
+            print "oops!"
+            graph.dump()
+            raise ValueError("OOPS! altTrash returned %s" % alt_trash)
+
+def _test():
+    t = RandomTest(10, 0.1, 4)
+    for i in xrange(100):
+        t.runone()
+
+    t = RandomTest(100, 0.01, 10)
+    for i in xrange(100):
+        t.runone()
+
+    t = RandomTest(1000, 0.005, 50)
+    for i in xrange(20):
+        t.runone()
+
+    t = RandomTest(100000, 0.00001, 20)
+    for i in xrange(2):
+        t.runone()
+
+if __name__ == "__main__":
+    _test()