D4505: util: lower water mark when removing nodes after cost limit reached
indygreg (Gregory Szorc)
phabricator at mercurial-scm.org
Wed Sep 12 10:53:36 EDT 2018
This revision was automatically updated to reflect the committed changes.
Closed by commit rHGf296c0b366c8: util: lower water mark when removing nodes after cost limit reached (authored by indygreg, committed by ).
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D4505?vs=10824&id=10944
REVISION DETAIL
https://phab.mercurial-scm.org/D4505
AFFECTED FILES
mercurial/util.py
tests/test-lrucachedict.py
CHANGE DETAILS
diff --git a/tests/test-lrucachedict.py b/tests/test-lrucachedict.py
--- a/tests/test-lrucachedict.py
+++ b/tests/test-lrucachedict.py
@@ -314,10 +314,10 @@
# 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.assertEqual(len(d), 2)
self.assertNotIn('a', d)
self.assertNotIn('b', d)
- self.assertIn('c', d)
+ self.assertNotIn('c', d)
self.assertIn('d', d)
self.assertIn('e', d)
diff --git a/mercurial/util.py b/mercurial/util.py
--- a/mercurial/util.py
+++ b/mercurial/util.py
@@ -1472,11 +1472,21 @@
# to walk the linked list and doing this in a loop would be
# quadratic. So we find the first non-empty node and then
# walk nodes until we free up enough capacity.
+ #
+ # If we only removed the minimum number of nodes to free enough
+ # cost at insert time, chances are high that the next insert would
+ # also require pruning. This would effectively constitute quadratic
+ # behavior for insert-heavy workloads. To mitigate this, we set a
+ # target cost that is a percentage of the max cost. This will tend
+ # to free more nodes when the high water mark is reached, which
+ # lowers the chances of needing to prune on the subsequent insert.
+ targetcost = int(self.maxcost * 0.75)
+
n = self._head.prev
while n.key is _notset:
n = n.prev
- while len(self) > 1 and self.totalcost > self.maxcost:
+ while len(self) > 1 and self.totalcost > targetcost:
del self._cache[n.key]
self.totalcost -= n.cost
n.markempty()
To: indygreg, #hg-reviewers
Cc: mercurial-devel
More information about the Mercurial-devel
mailing list