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

[Jeremy Hylton]

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

Modified Files:
      Tag: Zope-2_6-branch
	simul.py 
Log Message:
Add mechanism to change promotion policy for 2Q, and
allow subclass of 2Q to change the node class.

Changing the promotion threshold from 0 to 1 improves hit rate from
45% to 48% on the realserver01 workload.


=== ZODB3/ZEO/simul.py 1.12.8.2.18.14 => 1.12.8.2.18.15 ===
--- ZODB3/ZEO/simul.py:1.12.8.2.18.14	Fri Dec  5 00:04:55 2003
+++ ZODB3/ZEO/simul.py	Fri Dec  5 12:23:22 2003
@@ -474,6 +474,20 @@
 a1in = object()
 a1out = object()
 
+class Node2Q(Node):
+
+    __slots__ = ["kind", "hits"]
+
+    def __init__(self, oid, size, kind=None):
+        Node.__init__(self, oid, size)
+        self.kind = kind
+        self.hits = 0
+
+    def linkbefore(self, next):
+        if next.kind != self.kind:
+            self.kind = next.kind
+        Node.linkbefore(self, next)
+
 class TwoQSimluation(Simulation):
 
     # The original 2Q algorithm is page based and the authors offer
@@ -483,9 +497,16 @@
 
     extras = "evicts", "hothit", "am_add"
 
-    def __init__(self, cachelimit, outlen=10000):
+    NodeClass = Node2Q
+
+    def __init__(self, cachelimit, outlen=10000, threshold=0):
         Simulation.__init__(self, cachelimit)
 
+        # The promotion threshold: If a hit occurs in a1out, it is
+        # promoted to am if the number of hits on the object while it
+        # was in a1in is at least threshold.  The standard 2Q scheme
+        # uses a threshold of 0.
+        self.threshold = threshold
         self.am_limit = 3 * self.cachelimit / 4
         self.a1in_limit = self.cachelimit / 4
 
@@ -500,17 +521,17 @@
         self.a1out_limit = outlen
 
         # An LRU queue of hot objects
-        self.am = Node2Q(None, None, am)
+        self.am = self.NodeClass(None, None, am)
         self.am.linkbefore(self.am)
         # A FIFO queue of recently referenced objects.  It's purpose
         # is to absorb references to objects that are accessed a few
         # times in short order, then forgotten about.
-        self.a1in = Node2Q(None, None, a1in)
+        self.a1in = self.NodeClass(None, None, a1in)
         self.a1in.linkbefore(self.a1in)
         # A FIFO queue of recently reference oids.
         # This queue only stores the oids, not any data.  If we get a
         # hit in this queue, promote the object to am.
-        self.a1out = Node2Q(None, None, a1out)
+        self.a1out = self.NodeClass(None, None, a1out)
         self.a1out.linkbefore(self.a1out)
 
     def makespace(self, size):
@@ -583,26 +604,36 @@
                 self.total_hits += 1
                 self.hothit += 1
                 self.total_hothit += 1
+                node.hits += 1
                 node.linkbefore(self.am)
             elif node.kind is a1in:
                 self.hits += 1
                 self.total_hits += 1
+                node.hits += 1
             elif node.kind is a1out:
-                self.makespace(node.size)
-                self.am_size += node.size
-                node.linkbefore(self.am)
-                self.cache[oid] = node
-                self.am_add += 1
-                self.total_am_add += 1
+                self.a1out_size -= 1
+                if node.hits >= self.threshold:
+                    self.makespace(node.size)
+                    self.am_size += node.size
+                    node.linkbefore(self.am)
+                    self.cache[oid] = node
+                    self.am_add += 1
+                    self.total_am_add += 1
+                else:
+                    node.unlink()
+                    self.insert(oid, size)
         else:
-            # New objects enter the cache via a1in.  If they
-            # are frequently used over a long enough time, they
-            # will be promoted to am -- but only via a1out.
-            self.makespace(size)
-            node = Node2Q(oid, size, a1in)
-            node.linkbefore(self.a1in)
-            self.cache[oid] = node
-            self.a1in_size += node.size
+            self.insert(oid, size)
+            
+    def insert(self, oid, size):
+        # New objects enter the cache via a1in.  If they
+        # are frequently used over a long enough time, they
+        # will be promoted to am -- but only via a1out.
+        self.makespace(size)
+        node = self.NodeClass(oid, size, a1in)
+        node.linkbefore(self.a1in)
+        self.cache[oid] = node
+        self.a1in_size += node.size
 
     def inval(self, oid):
         # The original 2Q algorithm didn't have to deal with
@@ -628,19 +659,6 @@
         self.evicts = 0
         self.hothit = 0
         self.am_add = 0
-
-class Node2Q(Node):
-
-    __slots__ = ["kind"]
-
-    def __init__(self, oid, size, kind=None):
-        Node.__init__(self, oid, size)
-        self.kind = kind
-
-    def linkbefore(self, next):
-        if next.kind != self.kind:
-            self.kind = next.kind
-        Node.linkbefore(self, next)
 
 lruT = object()
 lruB = object()