This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4503

util: teach lrucachedict to enforce a max total cost
ClosedPublic

Authored by indygreg on Sep 6 2018, 9:17 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG842cd0bdda75: util: teach lrucachedict to enforce a max total cost
Summary

Now that lrucachedict entries can have a numeric cost associated
with them and we can easily pop the oldest item in the cache, it
now becomes relatively trivial to implement support for enforcing
a high water mark on the total cost of items in the cache.

This commit teaches lrucachedict instances to have a max cost
associated with them. When items are inserted, we pop old items
until enough "cost" frees up to make room for the new item.

This feature is close to zero cost when not used (modulo the insertion
regressed introduced by the previous commit):

$ ./hg perflrucachedict --size 4 --gets 1000000 --sets 1000000 --mixed 1000000
! gets
! wall 0.607444 comb 0.610000 user 0.610000 sys 0.000000 (best of 17)
! wall 0.601653 comb 0.600000 user 0.600000 sys 0.000000 (best of 17)
! inserts
! wall 0.678261 comb 0.680000 user 0.680000 sys 0.000000 (best of 14)
! wall 0.685042 comb 0.680000 user 0.680000 sys 0.000000 (best of 15)
! sets
! wall 0.808770 comb 0.800000 user 0.800000 sys 0.000000 (best of 13)
! wall 0.834241 comb 0.830000 user 0.830000 sys 0.000000 (best of 12)
! mixed
! wall 0.782441 comb 0.780000 user 0.780000 sys 0.000000 (best of 13)
! wall 0.803804 comb 0.800000 user 0.800000 sys 0.000000 (best of 13)

$ hg perflrucachedict --size 1000 --gets 1000000 --sets 1000000 --mixed 1000000
! init
! wall 0.006952 comb 0.010000 user 0.010000 sys 0.000000 (best of 418)
! gets
! wall 0.613350 comb 0.610000 user 0.610000 sys 0.000000 (best of 17)
! wall 0.617415 comb 0.620000 user 0.620000 sys 0.000000 (best of 17)
! inserts
! wall 0.701270 comb 0.700000 user 0.700000 sys 0.000000 (best of 15)
! wall 0.700516 comb 0.700000 user 0.700000 sys 0.000000 (best of 15)
! sets
! wall 0.825720 comb 0.830000 user 0.830000 sys 0.000000 (best of 13)
! wall 0.837946 comb 0.840000 user 0.830000 sys 0.010000 (best of 12)
! mixed
! wall 0.821644 comb 0.820000 user 0.820000 sys 0.000000 (best of 13)
! wall 0.850559 comb 0.850000 user 0.850000 sys 0.000000 (best of 12)

I reckon the slight slowdown on insert is due to added if checks.

For caches with total cost limiting enabled:

$ hg perflrucachedict --size 4 --gets 1000000 --sets 1000000 --mixed 1000000 --costlimit 100
! gets w/ cost limit
! wall 0.598737 comb 0.590000 user 0.590000 sys 0.000000 (best of 17)
! inserts w/ cost limit
! wall 1.694282 comb 1.700000 user 1.700000 sys 0.000000 (best of 6)
! mixed w/ cost limit
! wall 1.157655 comb 1.150000 user 1.150000 sys 0.000000 (best of 9)

$ hg perflrucachedict --size 1000 --gets 1000000 --sets 1000000 --mixed 1000000 --costlimit 10000
! gets w/ cost limit
! wall 0.598526 comb 0.600000 user 0.600000 sys 0.000000 (best of 17)
! inserts w/ cost limit
! wall 37.838315 comb 37.840000 user 37.840000 sys 0.000000 (best of 3)
! mixed w/ cost limit
! wall 18.060198 comb 18.060000 user 18.060000 sys 0.000000 (best of 3)

$ hg perflrucachedict --size 1000 --gets 1000000 --sets 1000000 --mixed 1000000 --costlimit 10000 --mixedgetfreq 90
! gets w/ cost limit
! wall 0.600024 comb 0.600000 user 0.600000 sys 0.000000 (best of 17)
! inserts w/ cost limit
! wall 37.154547 comb 37.120000 user 37.120000 sys 0.000000 (best of 3)
! mixed w/ cost limit
! wall 4.381602 comb 4.380000 user 4.370000 sys 0.010000 (best of 3)

The functions we're benchmarking are slightly different, which could
move numbers by a few milliseconds. But the slowdown on insert is too
great to be explained by that. The slowness is due to insert heavy
operations needing to call popoldest() repeatedly when the cache is
at capacity. The next commit will address this.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

indygreg created this revision.Sep 6 2018, 9:17 PM
Closed by commit rHG842cd0bdda75: util: teach lrucachedict to enforce a max total cost (authored by indygreg). · Explain WhySep 12 2018, 10:52 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mcontrib/perf.py (65 lines)
Mmercurial/util.py (28 lines)
Mtests/test-lrucachedict.py (104 lines)

Diff 10942

contrib/perf.py

Result is the number of markers in the repo.""" Result is the number of markers in the repo."""
timer, fm = gettimer(ui) timer, fm = gettimer(ui)
svfs = getsvfs(repo) svfs = getsvfs(repo)
timer(lambda: len(obsolete.obsstore(svfs))) timer(lambda: len(obsolete.obsstore(svfs)))
fm.end() fm.end()
@command(b'perflrucachedict', formatteropts + @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'gets', 10000, b'number of key lookups'),
(b'', b'sets', 10000, b'number of key sets'), (b'', b'sets', 10000, b'number of key sets'),
(b'', b'mixed', 10000, b'number of mixed mode operations'), (b'', b'mixed', 10000, b'number of mixed mode operations'),
(b'', b'mixedgetfreq', 50, b'frequency of get vs set ops in mixed mode')], (b'', b'mixedgetfreq', 50, b'frequency of get vs set ops in mixed mode')],
norepo=True) norepo=True)
def perflrucache(ui, size=4, gets=10000, sets=10000, mixed=10000, def perflrucache(ui, mincost=0, maxcost=100, costlimit=0, size=4,
mixedgetfreq=50, **opts): gets=10000, sets=10000, mixed=10000, mixedgetfreq=50, **opts):
def doinit(): def doinit():
for i in xrange(10000): for i in xrange(10000):
util.lrucachedict(size) util.lrucachedict(size)
costrange = list(range(mincost, maxcost + 1))
values = [] values = []
for i in xrange(size): for i in xrange(size):
values.append(random.randint(0, sys.maxint)) values.append(random.randint(0, sys.maxint))
# Get mode fills the cache and tests raw lookup performance with no # Get mode fills the cache and tests raw lookup performance with no
# eviction. # eviction.
getseq = [] getseq = []
for i in xrange(gets): for i in xrange(gets):
getseq.append(random.choice(values)) getseq.append(random.choice(values))
def dogets(): def dogets():
d = util.lrucachedict(size) d = util.lrucachedict(size)
for v in values: for v in values:
d[v] = v d[v] = v
for key in getseq: for key in getseq:
value = d[key] value = d[key]
value # silence pyflakes warning 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. # Set mode tests insertion speed with cache eviction.
setseq = [] setseq = []
costs = []
for i in xrange(sets): for i in xrange(sets):
setseq.append(random.randint(0, sys.maxint)) setseq.append(random.randint(0, sys.maxint))
costs.append(random.choice(costrange))
def doinserts(): def doinserts():
d = util.lrucachedict(size) d = util.lrucachedict(size)
for v in setseq: for v in setseq:
d.insert(v, v) 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(): def dosets():
d = util.lrucachedict(size) d = util.lrucachedict(size)
for v in setseq: for v in setseq:
d[v] = v d[v] = v
# Mixed mode randomly performs gets and sets with eviction. # Mixed mode randomly performs gets and sets with eviction.
mixedops = [] mixedops = []
for i in xrange(mixed): for i in xrange(mixed):
r = random.randint(0, 100) r = random.randint(0, 100)
if r < mixedgetfreq: if r < mixedgetfreq:
op = 0 op = 0
else: else:
op = 1 op = 1
mixedops.append((op, random.randint(0, size * 2))) mixedops.append((op,
random.randint(0, size * 2),
random.choice(costrange)))
def domixed(): def domixed():
d = util.lrucachedict(size) d = util.lrucachedict(size)
for op, v in mixedops: for op, v, cost in mixedops:
if op == 0: if op == 0:
try: try:
d[v] d[v]
except KeyError: except KeyError:
pass pass
else: else:
d[v] = v 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 = [ benches = [
(doinit, b'init'), (doinit, b'init'),
]
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'), (dogets, b'gets'),
(doinserts, b'inserts'), (doinserts, b'inserts'),
(dosets, b'sets'), (dosets, b'sets'),
(domixed, b'mixed') (domixed, b'mixed')
] ])
for fn, title in benches: for fn, title in benches:
timer, fm = gettimer(ui, opts) timer, fm = gettimer(ui, opts)
timer(fn, title=title) timer(fn, title=title)
fm.end() fm.end()
@command(b'perfwrite', formatteropts) @command(b'perfwrite', formatteropts)
def perfwrite(ui, repo, **opts): def perfwrite(ui, repo, **opts):

mercurial/util.py

The head node is the newest entry in the cache. If the cache is full, The head node is the newest entry in the cache. If the cache is full,
we recycle head.prev and make it the new head. Cache accesses result in we recycle head.prev and make it the new head. Cache accesses result in
the node being moved to before the existing head and being marked as the the node being moved to before the existing head and being marked as the
new head node. new head node.
Items in the cache can be inserted with an optional "cost" value. This is 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 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. 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._cache = {}
self._head = head = _lrucachenode() self._head = head = _lrucachenode()
head.prev = head head.prev = head
head.next = head head.next = head
self._size = 1 self._size = 1
self.capacity = max self.capacity = max
self.totalcost = 0 self.totalcost = 0
self.maxcost = maxcost
def __len__(self): def __len__(self):
return len(self._cache) return len(self._cache)
def __contains__(self, k): def __contains__(self, k):
return k in self._cache return k in self._cache
def __iter__(self): def __iter__(self):
node = self._cache.get(k) node = self._cache.get(k)
# Replace existing value and mark as newest. # Replace existing value and mark as newest.
if node is not None: if node is not None:
self.totalcost -= node.cost self.totalcost -= node.cost
node.value = v node.value = v
node.cost = cost node.cost = cost
self.totalcost += cost self.totalcost += cost
self._movetohead(node) self._movetohead(node)
if self.maxcost:
self._enforcecostlimit()
return return
if self._size < self.capacity: if self._size < self.capacity:
node = self._addcapacity() node = self._addcapacity()
else: else:
# Grab the last/oldest item. # Grab the last/oldest item.
node = self._head.prev node = self._head.prev
# At capacity. Kill the old entry. # At capacity. Kill the old entry.
if node.key is not _notset: if node.key is not _notset:
self.totalcost -= node.cost self.totalcost -= node.cost
del self._cache[node.key] del self._cache[node.key]
node.key = k node.key = k
node.value = v node.value = v
node.cost = cost node.cost = cost
self.totalcost += cost self.totalcost += cost
self._cache[k] = node self._cache[k] = node
# And mark it as newest entry. No need to adjust order since it # And mark it as newest entry. No need to adjust order since it
# is already self._head.prev. # is already self._head.prev.
self._head = node self._head = node
if self.maxcost:
self._enforcecostlimit()
def __setitem__(self, k, v): def __setitem__(self, k, v):
self.insert(k, v) self.insert(k, v)
def __delitem__(self, k): def __delitem__(self, k):
node = self._cache.pop(k) node = self._cache.pop(k)
self.totalcost -= node.cost self.totalcost -= node.cost
node.markempty() node.markempty()
n = self._head n = self._head
while n.key is not _notset: while n.key is not _notset:
self.totalcost -= n.cost self.totalcost -= n.cost
n.markempty() n.markempty()
n = n.next n = n.next
self._cache.clear() 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. """Create a new cache as a copy of the current one.
By default, the new cache has the same capacity as the existing one. By default, the new cache has the same capacity as the existing one.
But, the cache capacity can be changed as part of performing the But, the cache capacity can be changed as part of performing the
copy. copy.
Items in the copy have an insertion/access order matching this Items in the copy have an insertion/access order matching this
instance. instance.
""" """
capacity = capacity or self.capacity 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 # We copy entries by iterating in oldest-to-newest order so the copy
# has the correct ordering. # has the correct ordering.
# Find the first non-empty entry. # Find the first non-empty entry.
n = self._head.prev n = self._head.prev
while n.key is _notset and n is not self._head: while n.key is _notset and n is not self._head:
n = n.prev n = n.prev
node = _lrucachenode() node = _lrucachenode()
head.prev.next = node head.prev.next = node
node.prev = head.prev node.prev = head.prev
node.next = head node.next = head
head.prev = node head.prev = node
self._size += 1 self._size += 1
return node 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): def lrucachefunc(func):
'''cache most recent results of function calls''' '''cache most recent results of function calls'''
cache = {} cache = {}
order = collections.deque() order = collections.deque()
if func.__code__.co_argcount == 1: if func.__code__.co_argcount == 1:
def f(arg): def f(arg):
if arg not in cache: if arg not in cache:
if len(cache) > 20: if len(cache) > 20:

tests/test-lrucachedict.py

# Contents and order of original dict should remain unchanged. # Contents and order of original dict should remain unchanged.
dc['b'] = 'vb_new' dc['b'] = 'vb_new'
self.assertEqual(list(iter(d)), ['d', 'c', 'b', 'a']) self.assertEqual(list(iter(d)), ['d', 'c', 'b', 'a'])
for key in ('a', 'b', 'c', 'd'): for key in ('a', 'b', 'c', 'd'):
self.assertEqual(d[key], 'v%s' % key) 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): def testcopydecreasecapacity(self):
d = util.lrucachedict(5) d = util.lrucachedict(5)
d.insert('a', 'va', cost=4) d.insert('a', 'va', cost=4)
d.insert('b', 'vb', cost=2) d.insert('b', 'vb', cost=2)
d['c'] = 'vc' d['c'] = 'vc'
d['d'] = 'vd' d['d'] = 'vd'
dc = d.copy(2) dc = d.copy(2)
self.assertEqual(d.popoldest(), ('a', 'va')) self.assertEqual(d.popoldest(), ('a', 'va'))
self.assertEqual(len(d), 3) self.assertEqual(len(d), 3)
for key in ('b', 'c', 'd'): for key in ('b', 'c', 'd'):
self.assertEqual(d[key], 'v%s' % key) self.assertEqual(d[key], 'v%s' % key)
d['a'] = 'va' d['a'] = 'va'
self.assertEqual(d.popoldest(), ('b', 'vb')) 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__': if __name__ == '__main__':
silenttestrunner.main(__name__) silenttestrunner.main(__name__)