Mercurial > public > mercurial-scm > hg-stable

comparison mercurial/util.py @ 39583:ee087f0d7db5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
util: allow lrucachedict to track cost of entries Currently, lrucachedict allows tracking of arbitrary items with the only limit being the total number of items in the cache. Caches can be a lot more useful when they are bound by the size of the items in them rather than the number of elements in the cache. In preparation for teaching lrucachedict to enforce a max size of cached items, we teach lrucachedict to optionally associate a numeric cost value with each node. We purposefully let the caller define their own cost for nodes. This does introduce some overhead. Most of it comes from __setitem__, since that function now calls into insert(), thus introducing Python function call overhead. $ hg perflrucachedict --size 4 --gets 1000000 --sets 1000000 --mixed 1000000 ! gets ! wall 0.599552 comb 0.600000 user 0.600000 sys 0.000000 (best of 17) ! wall 0.614643 comb 0.610000 user 0.610000 sys 0.000000 (best of 17) ! inserts ! <not available> ! wall 0.655817 comb 0.650000 user 0.650000 sys 0.000000 (best of 16) ! sets ! wall 0.540448 comb 0.540000 user 0.540000 sys 0.000000 (best of 18) ! wall 0.805644 comb 0.810000 user 0.810000 sys 0.000000 (best of 13) ! mixed ! wall 0.651556 comb 0.660000 user 0.660000 sys 0.000000 (best of 15) ! wall 0.781357 comb 0.780000 user 0.780000 sys 0.000000 (best of 13) $ hg perflrucachedict --size 1000 --gets 1000000 --sets 1000000 --mixed 1000000 ! gets ! wall 0.621014 comb 0.620000 user 0.620000 sys 0.000000 (best of 16) ! wall 0.615146 comb 0.620000 user 0.620000 sys 0.000000 (best of 17) ! inserts ! <not available> ! wall 0.698115 comb 0.700000 user 0.700000 sys 0.000000 (best of 15) ! sets ! wall 0.560247 comb 0.560000 user 0.560000 sys 0.000000 (best of 18) ! wall 0.832495 comb 0.830000 user 0.830000 sys 0.000000 (best of 12) ! mixed ! wall 0.686172 comb 0.680000 user 0.680000 sys 0.000000 (best of 15) ! wall 0.841359 comb 0.840000 user 0.840000 sys 0.000000 (best of 12) We're still under 1us per insert, which seems like reasonable performance for a cache. If we comment out updating of self.totalcost during insert(), performance of insert() is identical to __setitem__ before. However, I don't want to make total cost evaluation lazy because it has significant performance implications for when we need to evaluate the total cost at mutation time (it requires a cache traversal, which could be expensive for large caches). Differential Revision: https://phab.mercurial-scm.org/D4502
author Gregory Szorc <gregory.szorc@gmail.com>
date Fri, 07 Sep 2018 12:14:42 -0700
parents bd9d3a89f07b
children 842cd0bdda75
comparison
equal deleted inserted replaced
39582:bd9d3a89f07b 39583:ee087f0d7db5
1207 """A node in a doubly linked list. 1207 """A node in a doubly linked list.
1208 1208
1209 Holds a reference to nodes on either side as well as a key-value 1209 Holds a reference to nodes on either side as well as a key-value
1210 pair for the dictionary entry. 1210 pair for the dictionary entry.
1211 """ 1211 """
1212 __slots__ = (u'next', u'prev', u'key', u'value') 1212 __slots__ = (u'next', u'prev', u'key', u'value', u'cost')
1213 1213
1214 def __init__(self): 1214 def __init__(self):
1215 self.next = None 1215 self.next = None
1216 self.prev = None 1216 self.prev = None
1217 1217
1218 self.key = _notset 1218 self.key = _notset
1219 self.value = None 1219 self.value = None
1220 self.cost = 0
1220 1221
1221 def markempty(self): 1222 def markempty(self):
1222 """Mark the node as emptied.""" 1223 """Mark the node as emptied."""
1223 self.key = _notset 1224 self.key = _notset
1225 self.value = None
1226 self.cost = 0
1224 1227
1225 class lrucachedict(object): 1228 class lrucachedict(object):
1226 """Dict that caches most recent accesses and sets. 1229 """Dict that caches most recent accesses and sets.
1227 1230
1228 The dict consists of an actual backing dict - indexed by original 1231 The dict consists of an actual backing dict - indexed by original
1231 1234
1232 The head node is the newest entry in the cache. If the cache is full, 1235 The head node is the newest entry in the cache. If the cache is full,
1233 we recycle head.prev and make it the new head. Cache accesses result in 1236 we recycle head.prev and make it the new head. Cache accesses result in
1234 the node being moved to before the existing head and being marked as the 1237 the node being moved to before the existing head and being marked as the
1235 new head node. 1238 new head node.
1239
1240 Items in the cache can be inserted with an optional "cost" value. This is
1241 simply an integer that is specified by the caller. The cache can be queried
1242 for the total cost of all items presently in the cache.
1236 """ 1243 """
1237 def __init__(self, max): 1244 def __init__(self, max):
1238 self._cache = {} 1245 self._cache = {}
1239 1246
1240 self._head = head = _lrucachenode() 1247 self._head = head = _lrucachenode()
1241 head.prev = head 1248 head.prev = head
1242 head.next = head 1249 head.next = head
1243 self._size = 1 1250 self._size = 1
1244 self.capacity = max 1251 self.capacity = max
1252 self.totalcost = 0
1245 1253
1246 def __len__(self): 1254 def __len__(self):
1247 return len(self._cache) 1255 return len(self._cache)
1248 1256
1249 def __contains__(self, k): 1257 def __contains__(self, k):
1259 def __getitem__(self, k): 1267 def __getitem__(self, k):
1260 node = self._cache[k] 1268 node = self._cache[k]
1261 self._movetohead(node) 1269 self._movetohead(node)
1262 return node.value 1270 return node.value
1263 1271
1264 def __setitem__(self, k, v): 1272 def insert(self, k, v, cost=0):
1273 """Insert a new item in the cache with optional cost value."""
1265 node = self._cache.get(k) 1274 node = self._cache.get(k)
1266 # Replace existing value and mark as newest. 1275 # Replace existing value and mark as newest.
1267 if node is not None: 1276 if node is not None:
1277 self.totalcost -= node.cost
1268 node.value = v 1278 node.value = v
1279 node.cost = cost
1280 self.totalcost += cost
1269 self._movetohead(node) 1281 self._movetohead(node)
1270 return 1282 return
1271 1283
1272 if self._size < self.capacity: 1284 if self._size < self.capacity:
1273 node = self._addcapacity() 1285 node = self._addcapacity()
1275 # Grab the last/oldest item. 1287 # Grab the last/oldest item.
1276 node = self._head.prev 1288 node = self._head.prev
1277 1289
1278 # At capacity. Kill the old entry. 1290 # At capacity. Kill the old entry.
1279 if node.key is not _notset: 1291 if node.key is not _notset:
1292 self.totalcost -= node.cost
1280 del self._cache[node.key] 1293 del self._cache[node.key]
1281 1294
1282 node.key = k 1295 node.key = k
1283 node.value = v 1296 node.value = v
1297 node.cost = cost
1298 self.totalcost += cost
1284 self._cache[k] = node 1299 self._cache[k] = node
1285 # And mark it as newest entry. No need to adjust order since it 1300 # And mark it as newest entry. No need to adjust order since it
1286 # is already self._head.prev. 1301 # is already self._head.prev.
1287 self._head = node 1302 self._head = node
1288 1303
1304 def __setitem__(self, k, v):
1305 self.insert(k, v)
1306
1289 def __delitem__(self, k): 1307 def __delitem__(self, k):
1290 node = self._cache.pop(k) 1308 node = self._cache.pop(k)
1309 self.totalcost -= node.cost
1291 node.markempty() 1310 node.markempty()
1292 1311
1293 # Temporarily mark as newest item before re-adjusting head to make 1312 # Temporarily mark as newest item before re-adjusting head to make
1294 # this node the oldest item. 1313 # this node the oldest item.
1295 self._movetohead(node) 1314 self._movetohead(node)
1304 return default 1323 return default
1305 1324
1306 def clear(self): 1325 def clear(self):
1307 n = self._head 1326 n = self._head
1308 while n.key is not _notset: 1327 while n.key is not _notset:
1328 self.totalcost -= n.cost
1309 n.markempty() 1329 n.markempty()
1310 n = n.next 1330 n = n.next
1311 1331
1312 self._cache.clear() 1332 self._cache.clear()
1313 1333
1334 n = n.prev 1354 n = n.prev
1335 1355
1336 # We could potentially skip the first N items when decreasing capacity. 1356 # We could potentially skip the first N items when decreasing capacity.
1337 # But let's keep it simple unless it is a performance problem. 1357 # But let's keep it simple unless it is a performance problem.
1338 for i in range(len(self._cache)): 1358 for i in range(len(self._cache)):
1339 result[n.key] = n.value 1359 result.insert(n.key, n.value, cost=n.cost)
1340 n = n.prev 1360 n = n.prev
1341 1361
1342 return result 1362 return result
1343 1363
1344 def popoldest(self): 1364 def popoldest(self):
1357 1377
1358 key, value = n.key, n.value 1378 key, value = n.key, n.value
1359 1379
1360 # And remove it from the cache and mark it as empty. 1380 # And remove it from the cache and mark it as empty.
1361 del self._cache[n.key] 1381 del self._cache[n.key]
1382 self.totalcost -= n.cost
1362 n.markempty() 1383 n.markempty()
1363 1384
1364 return key, value 1385 return key, value
1365 1386
1366 def _movetohead(self, node): 1387 def _movetohead(self, node):