[Zodb-checkins] CVS: ZODB3/ZEO - simul.py:1.12.8.2.18.4

[Jeremy Hylton]

Update of /cvs-repository/ZODB3/ZEO
In directory cvs.zope.org:/tmp/cvs-serv16138

Modified Files:
      Tag: Zope-2_6-branch
	simul.py 
Log Message:
Fix a bunch of major bugs in the 2Q implementation.

The restart() method was tossing the cache dict every time around, but
leaving the linked lists full.  The cache is supposed to be fully
persistent, so a restart should not toss the cache.  This change
creates a dramatic improvement in hit rate.  Without it, few things
ever got into am; now many things do.

Increase the current size of am when an object is added to it.
Otherwise, it always looks empty (doh!) and a1in uses all the cache
space.  (Thus 2Q often looked like FIFO.)

Add note about OracleSimulation.


=== ZODB3/ZEO/simul.py 1.12.8.2.18.3 => 1.12.8.2.18.4 ===
--- ZODB3/ZEO/simul.py:1.12.8.2.18.3	Tue Dec  2 22:45:00 2003
+++ ZODB3/ZEO/simul.py	Wed Dec  3 00:23:56 2003
@@ -45,7 +45,7 @@
     simclass = ZEOCacheSimulation
     omicron = None
     try:
-        opts, args = getopt.getopt(sys.argv[1:], "bflyz2cs:o:")
+        opts, args = getopt.getopt(sys.argv[1:], "bflyz2cOs:o:")
     except getopt.error, msg:
         usage(msg)
         return 2
@@ -68,6 +68,8 @@
             simclass = CircularCacheSimulation
         if o == '-o':
             omicron = float(a)
+        if o == '-O':
+            simclass = OracleSimulation
     if len(args) != 1:
         usage("exactly one file argument required")
         return 2
@@ -464,12 +466,21 @@
     # object based, so, for example, it's hard to compute the number
     # of oids to store in a1out based on the size of a1in.
 
-    extras = "evicts", "hothits"
+    extras = "evicts", "hothit"
 
-    def __init__(self, cachelimit, outlen=100000):
+    def __init__(self, cachelimit, outlen=10000):
         Simulation.__init__(self, cachelimit)
+        
+        self.am_limit = 3 * self.cachelimit / 4
+        self.a1in_limit = self.cachelimit / 4
+        
+        self.cache = {}
+        self.am_size = 0
+        self.a1in_size = 0
+        self.a1out_size = 0
+        
         self.total_evicts = 0
-        self.total_hothits = 0
+        self.total_hothit = 0
         self.a1out_limit = outlen
 
         # An LRU queue of hot objects
@@ -542,15 +553,9 @@
         if node.kind is am:
             self.am_size = self.am_size - node.size + size
             node.size = size
-            if self.am_size > self.am_limit:
-                pass
-##                print "write exceeded limit", self.am_size - self.am_limit
         else:
             self.a1in_size = self.a1in_size - node.size + size
             node.size = size
-            if self.a1in_size > self.a1in_limit:
-                pass
-##                print "write exceeded limit", self.a1in_size - self.a1in_limit
 
     def load(self, oid, size):
         node = self.cache.get(oid)
@@ -558,19 +563,20 @@
             if node.kind is am:
                 self.hits += 1
                 self.total_hits += 1
-                self.hothits += 1
-                self.total_hothits += 1
+                self.hothit += 1
+                self.total_hothit += 1
                 node.linkbefore(self.am)
             elif node.kind is a1in:
                 self.hits += 1
                 self.total_hits += 1
             elif node.kind is a1out:
                 self.makespace(node.size)
+                self.am_size += node.size
                 node.linkbefore(self.am)
         else:
             # New objects enter the cache via a1in.  If they
             # are frequently used over a long enough time, they
-            # will be promoted to am.
+            # will be promoted to am -- but only via a1out.
             self.makespace(size)
             node = Node2Q(oid, size, a1in)
             node.linkbefore(self.a1in)
@@ -579,8 +585,8 @@
 
     def inval(self, oid):
         # The original 2Q algorithm didn't have to deal with
-        # invalidations.  My own solution: Move it to the head
-        # of a1out.
+        # invalidations.  My own solution: Move it to the head of
+        # a1out.
         node = self.cache.get(oid)
         if node is None:
             return
@@ -599,14 +605,7 @@
         Simulation.restart(self)
 
         self.evicts = 0
-        self.hothits = 0
-
-        self.cache = {}
-        self.am_limit = 3 * self.cachelimit / 4
-        self.a1in_limit = self.cachelimit / 4
-        self.am_size = 0
-        self.a1in_size = 0
-        self.a1out_size = 0
+        self.hothit = 0
 
 class Node2Q(Node):
 
@@ -620,6 +619,15 @@
         if next.kind != self.kind:
             self.kind = next.kind
         Node.linkbefore(self, next)
+
+class OracleSimulation(LRUCacheSimulation):
+
+    # Not sure how to implement this yet.  This is a cache where I
+    # cheat to see how good we could actually do.  The cache
+    # replacement problem for multi-size caches is NP-hard, so we're
+    # not going to have an optimal solution.  Somehow, prime the
+    # cache with a list of objects that will be accessed more than
+    # once and only cache those objects.
 
 class CircularCacheSimulation(Simulation):