Mercurial > hg

--- a/contrib/perf.py	Fri Sep 07 12:14:42 2018 -0700
+++ b/contrib/perf.py	Thu Sep 06 14:04:46 2018 -0700
@@ -1869,18 +1869,23 @@
     fm.end()

 @command(b'perflrucachedict', formatteropts +
-    [(b'', b'size', 4, b'size of cache'),
+    [(b'', b'costlimit', 0, b'maximum total cost of items in cache'),
+     (b'', b'mincost', 0, b'smallest cost of items in cache'),
+     (b'', b'maxcost', 100, b'maximum cost of items in cache'),
+     (b'', b'size', 4, b'size of cache'),
      (b'', b'gets', 10000, b'number of key lookups'),
      (b'', b'sets', 10000, b'number of key sets'),
      (b'', b'mixed', 10000, b'number of mixed mode operations'),
      (b'', b'mixedgetfreq', 50, b'frequency of get vs set ops in mixed mode')],
     norepo=True)
-def perflrucache(ui, size=4, gets=10000, sets=10000, mixed=10000,
-                 mixedgetfreq=50, **opts):
+def perflrucache(ui, mincost=0, maxcost=100, costlimit=0, size=4,
+                 gets=10000, sets=10000, mixed=10000, mixedgetfreq=50, **opts):
     def doinit():
         for i in xrange(10000):
             util.lrucachedict(size)

+    costrange = list(range(mincost, maxcost + 1))
+
     values = []
     for i in xrange(size):
         values.append(random.randint(0, sys.maxint))
@@ -1899,16 +1904,34 @@
             value = d[key]
             value # silence pyflakes warning

+    def dogetscost():
+        d = util.lrucachedict(size, maxcost=costlimit)
+        for i, v in enumerate(values):
+            d.insert(v, v, cost=costs[i])
+        for key in getseq:
+            try:
+                value = d[key]
+                value # silence pyflakes warning
+            except KeyError:
+                pass
+
     # Set mode tests insertion speed with cache eviction.
     setseq = []
+    costs = []
     for i in xrange(sets):
         setseq.append(random.randint(0, sys.maxint))
+        costs.append(random.choice(costrange))

     def doinserts():
         d = util.lrucachedict(size)
         for v in setseq:
             d.insert(v, v)

+    def doinsertscost():
+        d = util.lrucachedict(size, maxcost=costlimit)
+        for i, v in enumerate(setseq):
+            d.insert(v, v, cost=costs[i])
+
     def dosets():
         d = util.lrucachedict(size)
         for v in setseq:
@@ -1923,12 +1946,14 @@
         else:
             op = 1

-        mixedops.append((op, random.randint(0, size * 2)))
+        mixedops.append((op,
+                         random.randint(0, size * 2),
+                         random.choice(costrange)))

     def domixed():
         d = util.lrucachedict(size)

-        for op, v in mixedops:
+        for op, v, cost in mixedops:
             if op == 0:
                 try:
                     d[v]
@@ -1937,14 +1962,36 @@
             else:
                 d[v] = v

+    def domixedcost():
+        d = util.lrucachedict(size, maxcost=costlimit)
+
+        for op, v, cost in mixedops:
+            if op == 0:
+                try:
+                    d[v]
+                except KeyError:
+                    pass
+            else:
+                d.insert(v, v, cost=cost)
+
     benches = [
         (doinit, b'init'),
-        (dogets, b'gets'),
-        (doinserts, b'inserts'),
-        (dosets, b'sets'),
-        (domixed, b'mixed')
     ]

+    if costlimit:
+        benches.extend([
+            (dogetscost, b'gets w/ cost limit'),
+            (doinsertscost, b'inserts w/ cost limit'),
+            (domixedcost, b'mixed w/ cost limit'),
+        ])
+    else:
+        benches.extend([
+            (dogets, b'gets'),
+            (doinserts, b'inserts'),
+            (dosets, b'sets'),
+            (domixed, b'mixed')
+        ])
+
     for fn, title in benches:
         timer, fm = gettimer(ui, opts)
         timer(fn, title=title)
--- a/mercurial/util.py	Fri Sep 07 12:14:42 2018 -0700
+++ b/mercurial/util.py	Thu Sep 06 14:04:46 2018 -0700
@@ -1240,8 +1240,14 @@
     Items in the cache can be inserted with an optional "cost" value. This is
     simply an integer that is specified by the caller. The cache can be queried
     for the total cost of all items presently in the cache.
+
+    The cache can also define a maximum cost. If a cache insertion would
+    cause the total cost of the cache to go beyond the maximum cost limit,
+    nodes will be evicted to make room for the new code. This can be used
+    to e.g. set a max memory limit and associate an estimated bytes size
+    cost to each item in the cache. By default, no maximum cost is enforced.
     """
-    def __init__(self, max):
+    def __init__(self, max, maxcost=0):
         self._cache = {}

         self._head = head = _lrucachenode()
@@ -1250,6 +1256,7 @@
         self._size = 1
         self.capacity = max
         self.totalcost = 0
+        self.maxcost = maxcost

     def __len__(self):
         return len(self._cache)
@@ -1279,6 +1286,10 @@
             node.cost = cost
             self.totalcost += cost
             self._movetohead(node)
+
+            if self.maxcost:
+                self._enforcecostlimit()
+
             return

         if self._size < self.capacity:
@@ -1301,6 +1312,9 @@
         # is already self._head.prev.
         self._head = node

+        if self.maxcost:
+            self._enforcecostlimit()
+
     def __setitem__(self, k, v):
         self.insert(k, v)

@@ -1331,7 +1345,7 @@

         self._cache.clear()

-    def copy(self, capacity=None):
+    def copy(self, capacity=None, maxcost=0):
         """Create a new cache as a copy of the current one.

         By default, the new cache has the same capacity as the existing one.
@@ -1343,7 +1357,8 @@
         """

         capacity = capacity or self.capacity
-        result = lrucachedict(capacity)
+        maxcost = maxcost or self.maxcost
+        result = lrucachedict(capacity, maxcost=maxcost)

         # We copy entries by iterating in oldest-to-newest order so the copy
         # has the correct ordering.
@@ -1445,6 +1460,13 @@
         self._size += 1
         return node

+    def _enforcecostlimit(self):
+        # This should run after an insertion. It should only be called if total
+        # cost limits are being enforced.
+        # The most recently inserted node is never evicted.
+        while len(self) > 1 and self.totalcost > self.maxcost:
+            self.popoldest()
+
 def lrucachefunc(func):
     '''cache most recent results of function calls'''
     cache = {}
--- a/tests/test-lrucachedict.py	Fri Sep 07 12:14:42 2018 -0700
+++ b/tests/test-lrucachedict.py	Thu Sep 06 14:04:46 2018 -0700
@@ -133,6 +133,22 @@
         for key in ('a', 'b', 'c', 'd'):
             self.assertEqual(d[key], 'v%s' % key)

+        d = util.lrucachedict(4, maxcost=42)
+        d.insert('a', 'va', cost=5)
+        d.insert('b', 'vb', cost=4)
+        d.insert('c', 'vc', cost=3)
+        dc = d.copy()
+        self.assertEqual(dc.maxcost, 42)
+        self.assertEqual(len(dc), 3)
+
+        # Max cost can be lowered as part of copy.
+        dc = d.copy(maxcost=10)
+        self.assertEqual(dc.maxcost, 10)
+        self.assertEqual(len(dc), 2)
+        self.assertEqual(dc.totalcost, 7)
+        self.assertIn('b', dc)
+        self.assertIn('c', dc)
+
     def testcopydecreasecapacity(self):
         d = util.lrucachedict(5)
         d.insert('a', 'va', cost=4)
@@ -217,5 +233,93 @@
         d['a'] = 'va'
         self.assertEqual(d.popoldest(), ('b', 'vb'))

+    def testmaxcost(self):
+        # Item cost is zero by default.
+        d = util.lrucachedict(6, maxcost=10)
+        d['a'] = 'va'
+        d['b'] = 'vb'
+        d['c'] = 'vc'
+        d['d'] = 'vd'
+        self.assertEqual(len(d), 4)
+        self.assertEqual(d.totalcost, 0)
+
+        d.clear()
+
+        # Insertion to exact cost threshold works without eviction.
+        d.insert('a', 'va', cost=6)
+        d.insert('b', 'vb', cost=4)
+
+        self.assertEqual(len(d), 2)
+        self.assertEqual(d['a'], 'va')
+        self.assertEqual(d['b'], 'vb')
+
+        # Inserting a new element with 0 cost works.
+        d['c'] = 'vc'
+        self.assertEqual(len(d), 3)
+
+        # Inserting a new element with cost putting us above high
+        # water mark evicts oldest single item.
+        d.insert('d', 'vd', cost=1)
+        self.assertEqual(len(d), 3)
+        self.assertEqual(d.totalcost, 5)
+        self.assertNotIn('a', d)
+        for key in ('b', 'c', 'd'):
+            self.assertEqual(d[key], 'v%s' % key)
+
+        # Inserting a new element with enough room for just itself
+        # evicts all items before.
+        d.insert('e', 've', cost=10)
+        self.assertEqual(len(d), 1)
+        self.assertEqual(d.totalcost, 10)
+        self.assertIn('e', d)
+
+        # Inserting a new element with cost greater than threshold
+        # still retains that item.
+        d.insert('f', 'vf', cost=11)
+        self.assertEqual(len(d), 1)
+        self.assertEqual(d.totalcost, 11)
+        self.assertIn('f', d)
+
+        # Inserting a new element will evict the last item since it is
+        # too large.
+        d['g'] = 'vg'
+        self.assertEqual(len(d), 1)
+        self.assertEqual(d.totalcost, 0)
+        self.assertIn('g', d)
+
+        d.clear()
+
+        d.insert('a', 'va', cost=7)
+        d.insert('b', 'vb', cost=3)
+        self.assertEqual(len(d), 2)
+
+        # Replacing a value with smaller cost won't result in eviction.
+        d.insert('b', 'vb2', cost=2)
+        self.assertEqual(len(d), 2)
+
+        # Replacing a value with a higher cost will evict when threshold
+        # exceeded.
+        d.insert('b', 'vb3', cost=4)
+        self.assertEqual(len(d), 1)
+        self.assertNotIn('a', d)
+
+    def testmaxcostcomplex(self):
+        d = util.lrucachedict(100, maxcost=100)
+        d.insert('a', 'va', cost=9)
+        d.insert('b', 'vb', cost=21)
+        d.insert('c', 'vc', cost=7)
+        d.insert('d', 'vc', cost=50)
+        self.assertEqual(d.totalcost, 87)
+
+        # Inserting new element should free multiple elements so we hit
+        # low water mark.
+        d.insert('e', 'vd', cost=25)
+        self.assertEqual(len(d), 3)
+        self.assertNotIn('a', d)
+        self.assertNotIn('b', d)
+        self.assertIn('c', d)
+        self.assertIn('d', d)
+        self.assertIn('e', d)
+
 if __name__ == '__main__':
     silenttestrunner.main(__name__)