mercurial-scm/hg: tests/test-lrucachedict.py annotate

annotate tests/test-lrucachedict.py @ 39570:f296c0b366c8

util: lower water mark when removing nodes after cost limit reached See the inline comment for the reasoning here. This is a pretty common strategy for garbage collectors, other cache-like primtives. The performance impact is substantial: $ hg perflrucachedict --size 4 --gets 1000000 --sets 1000000 --mixed 1000000 --costlimit 100 ! inserts w/ cost limit ! wall 1.659181 comb 1.650000 user 1.650000 sys 0.000000 (best of 7) ! wall 1.722122 comb 1.720000 user 1.720000 sys 0.000000 (best of 6) ! mixed w/ cost limit ! wall 1.139955 comb 1.140000 user 1.140000 sys 0.000000 (best of 9) ! wall 1.182513 comb 1.180000 user 1.180000 sys 0.000000 (best of 9) $ hg perflrucachedict --size 1000 --gets 1000000 --sets 1000000 --mixed 1000000 --costlimit 10000 ! inserts ! wall 0.679546 comb 0.680000 user 0.680000 sys 0.000000 (best of 15) ! sets ! wall 0.825147 comb 0.830000 user 0.830000 sys 0.000000 (best of 13) ! inserts w/ cost limit ! wall 25.105273 comb 25.080000 user 25.080000 sys 0.000000 (best of 3) ! wall 1.724397 comb 1.720000 user 1.720000 sys 0.000000 (best of 6) ! mixed ! wall 0.807096 comb 0.810000 user 0.810000 sys 0.000000 (best of 13) ! mixed w/ cost limit ! wall 12.104470 comb 12.070000 user 12.070000 sys 0.000000 (best of 3) ! wall 1.190563 comb 1.190000 user 1.190000 sys 0.000000 (best of 9) $ hg perflrucachedict --size 1000 --gets 1000000 --sets 1000000 --mixed 1000000 --costlimit 10000 --mixedgetfreq 90 ! inserts ! wall 0.711177 comb 0.710000 user 0.710000 sys 0.000000 (best of 14) ! sets ! wall 0.846992 comb 0.850000 user 0.850000 sys 0.000000 (best of 12) ! inserts w/ cost limit ! wall 25.963028 comb 25.960000 user 25.960000 sys 0.000000 (best of 3) ! wall 2.184311 comb 2.180000 user 2.180000 sys 0.000000 (best of 5) ! mixed ! wall 0.728256 comb 0.730000 user 0.730000 sys 0.000000 (best of 14) ! mixed w/ cost limit ! wall 3.174256 comb 3.170000 user 3.170000 sys 0.000000 (best of 4) ! wall 0.773186 comb 0.770000 user 0.770000 sys 0.000000 (best of 13) $ hg perflrucachedict --size 100000 --gets 1000000 --sets 1000000 --mixed 1000000 --mixedgetfreq 90 --costlimit 5000000 ! gets ! wall 1.191368 comb 1.190000 user 1.190000 sys 0.000000 (best of 9) ! wall 1.195304 comb 1.190000 user 1.190000 sys 0.000000 (best of 9) ! inserts ! wall 0.950995 comb 0.950000 user 0.950000 sys 0.000000 (best of 11) ! inserts w/ cost limit ! wall 1.589732 comb 1.590000 user 1.590000 sys 0.000000 (best of 7) ! sets ! wall 1.094941 comb 1.100000 user 1.090000 sys 0.010000 (best of 9) ! mixed ! wall 0.936420 comb 0.940000 user 0.930000 sys 0.010000 (best of 10) ! mixed w/ cost limit ! wall 0.882780 comb 0.870000 user 0.870000 sys 0.000000 (best of 11) This puts us ~2x slower than caches without cost accounting. And for read-heavy workloads (the prime use cases for caches), performance is nearly identical. In the worst case (pure write workloads with cost accounting enabled), we're looking at ~1.5us per insert on large caches. That seems "fast enough." Differential Revision: https://phab.mercurial-scm.org/D4505

author	Gregory Szorc <gregory.szorc@gmail.com>
date	Thu, 06 Sep 2018 18:04:27 -0700
parents	842cd0bdda75
children	8f2c0d1b454c

rev	line source
28931 ba0e4789bd2e tests: make test-lrucachedict use print_function Pulkit Goyal <7895pulkit@gmail.com> parents: 28930 diff changeset	1 from __future__ import absolute_import, print_function
28930 e3f01188d439 tests: make test-lrucachedict use absolute_import Pulkit Goyal <7895pulkit@gmail.com> parents: 27576 diff changeset	2
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	3 import unittest
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	4
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	5 import silenttestrunner
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	6
28930 e3f01188d439 tests: make test-lrucachedict use absolute_import Pulkit Goyal <7895pulkit@gmail.com> parents: 27576 diff changeset	7 from mercurial import (
e3f01188d439 tests: make test-lrucachedict use absolute_import Pulkit Goyal <7895pulkit@gmail.com> parents: 27576 diff changeset	8 util,
e3f01188d439 tests: make test-lrucachedict use absolute_import Pulkit Goyal <7895pulkit@gmail.com> parents: 27576 diff changeset	9 )
18603 2251b3184e6e util: add an LRU cache dict Siddharth Agarwal <sid0@fb.com> parents: diff changeset	10
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	11 class testlrucachedict(unittest.TestCase):
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	12 def testsimple(self):
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	13 d = util.lrucachedict(4)
39564 5d75a3c16193 util: make capacity a public attribute on lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39563 diff changeset	14 self.assertEqual(d.capacity, 4)
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	15 d.insert('a', 'va', cost=2)
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	16 d['b'] = 'vb'
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	17 d['c'] = 'vc'
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	18 d.insert('d', 'vd', cost=42)
18603 2251b3184e6e util: add an LRU cache dict Siddharth Agarwal <sid0@fb.com> parents: diff changeset	19
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	20 self.assertEqual(d['a'], 'va')
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	21 self.assertEqual(d['b'], 'vb')
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	22 self.assertEqual(d['c'], 'vc')
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	23 self.assertEqual(d['d'], 'vd')
18603 2251b3184e6e util: add an LRU cache dict Siddharth Agarwal <sid0@fb.com> parents: diff changeset	24
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	25 self.assertEqual(d.totalcost, 44)
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	26
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	27 # 'a' should be dropped because it was least recently used.
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	28 d['e'] = 've'
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	29 self.assertNotIn('a', d)
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	30 self.assertIsNone(d.get('a'))
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	31 self.assertEqual(d.totalcost, 42)
18603 2251b3184e6e util: add an LRU cache dict Siddharth Agarwal <sid0@fb.com> parents: diff changeset	32
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	33 self.assertEqual(d['b'], 'vb')
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	34 self.assertEqual(d['c'], 'vc')
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	35 self.assertEqual(d['d'], 'vd')
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	36 self.assertEqual(d['e'], 've')
18603 2251b3184e6e util: add an LRU cache dict Siddharth Agarwal <sid0@fb.com> parents: diff changeset	37
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	38 # Replacing item with different cost adjusts totalcost.
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	39 d.insert('e', 've', cost=4)
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	40 self.assertEqual(d.totalcost, 46)
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	41
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	42 # Touch entries in some order (both get and set).
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	43 d['e']
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	44 d['c'] = 'vc2'
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	45 d['d']
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	46 d['b'] = 'vb2'
29828 79add5a4e857 util: properly implement lrucachedict.get() Gregory Szorc <gregory.szorc@gmail.com> parents: 28931 diff changeset	47
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	48 # 'e' should be dropped now
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	49 d['f'] = 'vf'
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	50 self.assertNotIn('e', d)
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	51 self.assertEqual(d['b'], 'vb2')
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	52 self.assertEqual(d['c'], 'vc2')
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	53 self.assertEqual(d['d'], 'vd')
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	54 self.assertEqual(d['f'], 'vf')
18603 2251b3184e6e util: add an LRU cache dict Siddharth Agarwal <sid0@fb.com> parents: diff changeset	55
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	56 d.clear()
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	57 for key in ('a', 'b', 'c', 'd', 'e', 'f'):
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	58 self.assertNotIn(key, d)
18603 2251b3184e6e util: add an LRU cache dict Siddharth Agarwal <sid0@fb.com> parents: diff changeset	59
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	60 def testunfull(self):
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	61 d = util.lrucachedict(4)
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	62 d['a'] = 1
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	63 d['b'] = 2
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	64 d['a']
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	65 d['b']
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	66
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	67 for key in ('a', 'b'):
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	68 self.assertIn(key, d)
19710 887ffa22fd0d lrucachedict: implement clear() Siddharth Agarwal <sid0@fb.com> parents: 18603 diff changeset	69
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	70 def testcopypartial(self):
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	71 d = util.lrucachedict(4)
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	72 d.insert('a', 'va', cost=4)
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	73 d.insert('b', 'vb', cost=2)
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	74
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	75 dc = d.copy()
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	76
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	77 self.assertEqual(len(dc), 2)
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	78 self.assertEqual(dc.totalcost, 6)
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	79 for key in ('a', 'b'):
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	80 self.assertIn(key, dc)
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	81 self.assertEqual(dc[key], 'v%s' % key)
27371 45d996a566d7 util: reimplement lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 19710 diff changeset	82
39563 b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	83 self.assertEqual(len(d), 2)
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	84 for key in ('a', 'b'):
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	85 self.assertIn(key, d)
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	86 self.assertEqual(d[key], 'v%s' % key)
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	87
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	88 d['c'] = 'vc'
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	89 del d['b']
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	90 self.assertEqual(d.totalcost, 4)
39563 b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	91 dc = d.copy()
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	92 self.assertEqual(len(dc), 2)
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	93 self.assertEqual(dc.totalcost, 4)
39563 b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	94 for key in ('a', 'c'):
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	95 self.assertIn(key, dc)
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	96 self.assertEqual(dc[key], 'v%s' % key)
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	97
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	98 def testcopyempty(self):
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	99 d = util.lrucachedict(4)
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	100 dc = d.copy()
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	101 self.assertEqual(len(dc), 0)
b31b01f93b11 util: properly copy lrucachedict instances Gregory Szorc <gregory.szorc@gmail.com> parents: 39562 diff changeset	102
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	103 def testcopyfull(self):
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	104 d = util.lrucachedict(4)
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	105 d.insert('a', 'va', cost=42)
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	106 d['b'] = 'vb'
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	107 d['c'] = 'vc'
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	108 d['d'] = 'vd'
27576 6cd3044985c2 lrucachedict: add copy method Eric Sumner <ericsumner@fb.com> parents: 27371 diff changeset	109
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	110 dc = d.copy()
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	111
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	112 for key in ('a', 'b', 'c', 'd'):
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	113 self.assertIn(key, dc)
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	114 self.assertEqual(dc[key], 'v%s' % key)
27576 6cd3044985c2 lrucachedict: add copy method Eric Sumner <ericsumner@fb.com> parents: 27371 diff changeset	115
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	116 self.assertEqual(d.totalcost, 42)
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	117 self.assertEqual(dc.totalcost, 42)
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	118
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	119 # 'a' should be dropped because it was least recently used.
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	120 dc['e'] = 've'
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	121 self.assertNotIn('a', dc)
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	122 for key in ('b', 'c', 'd', 'e'):
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	123 self.assertIn(key, dc)
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	124 self.assertEqual(dc[key], 'v%s' % key)
27576 6cd3044985c2 lrucachedict: add copy method Eric Sumner <ericsumner@fb.com> parents: 27371 diff changeset	125
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	126 self.assertEqual(d.totalcost, 42)
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	127 self.assertEqual(dc.totalcost, 0)
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	128
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	129 # Contents and order of original dict should remain unchanged.
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	130 dc['b'] = 'vb_new'
27576 6cd3044985c2 lrucachedict: add copy method Eric Sumner <ericsumner@fb.com> parents: 27371 diff changeset	131
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	132 self.assertEqual(list(iter(d)), ['d', 'c', 'b', 'a'])
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	133 for key in ('a', 'b', 'c', 'd'):
067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	134 self.assertEqual(d[key], 'v%s' % key)
27576 6cd3044985c2 lrucachedict: add copy method Eric Sumner <ericsumner@fb.com> parents: 27371 diff changeset	135
39568 842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	136 d = util.lrucachedict(4, maxcost=42)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	137 d.insert('a', 'va', cost=5)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	138 d.insert('b', 'vb', cost=4)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	139 d.insert('c', 'vc', cost=3)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	140 dc = d.copy()
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	141 self.assertEqual(dc.maxcost, 42)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	142 self.assertEqual(len(dc), 3)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	143
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	144 # Max cost can be lowered as part of copy.
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	145 dc = d.copy(maxcost=10)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	146 self.assertEqual(dc.maxcost, 10)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	147 self.assertEqual(len(dc), 2)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	148 self.assertEqual(dc.totalcost, 7)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	149 self.assertIn('b', dc)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	150 self.assertIn('c', dc)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	151
39565 2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	152 def testcopydecreasecapacity(self):
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	153 d = util.lrucachedict(5)
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	154 d.insert('a', 'va', cost=4)
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	155 d.insert('b', 'vb', cost=2)
39565 2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	156 d['c'] = 'vc'
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	157 d['d'] = 'vd'
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	158
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	159 dc = d.copy(2)
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	160 self.assertEqual(dc.totalcost, 0)
39565 2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	161 for key in ('a', 'b'):
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	162 self.assertNotIn(key, dc)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	163 for key in ('c', 'd'):
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	164 self.assertIn(key, dc)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	165 self.assertEqual(dc[key], 'v%s' % key)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	166
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	167 dc.insert('e', 've', cost=7)
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	168 self.assertEqual(dc.totalcost, 7)
39565 2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	169 self.assertNotIn('c', dc)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	170 for key in ('d', 'e'):
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	171 self.assertIn(key, dc)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	172 self.assertEqual(dc[key], 'v%s' % key)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	173
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	174 # Original should remain unchanged.
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	175 self.assertEqual(d.totalcost, 6)
39565 2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	176 for key in ('a', 'b', 'c', 'd'):
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	177 self.assertIn(key, d)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	178 self.assertEqual(d[key], 'v%s' % key)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	179
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	180 def testcopyincreasecapacity(self):
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	181 d = util.lrucachedict(5)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	182 d['a'] = 'va'
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	183 d['b'] = 'vb'
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	184 d['c'] = 'vc'
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	185 d['d'] = 'vd'
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	186
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	187 dc = d.copy(6)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	188 for key in ('a', 'b', 'c', 'd'):
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	189 self.assertIn(key, dc)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	190 self.assertEqual(dc[key], 'v%s' % key)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	191
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	192 dc['e'] = 've'
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	193 dc['f'] = 'vf'
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	194 for key in ('a', 'b', 'c', 'd', 'e', 'f'):
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	195 self.assertIn(key, dc)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	196 self.assertEqual(dc[key], 'v%s' % key)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	197
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	198 dc['g'] = 'vg'
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	199 self.assertNotIn('a', dc)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	200 for key in ('b', 'c', 'd', 'e', 'f', 'g'):
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	201 self.assertIn(key, dc)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	202 self.assertEqual(dc[key], 'v%s' % key)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	203
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	204 # Original should remain unchanged.
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	205 for key in ('a', 'b', 'c', 'd'):
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	206 self.assertIn(key, d)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	207 self.assertEqual(d[key], 'v%s' % key)
2dcc68c7d25b util: ability to change capacity when copying lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39564 diff changeset	208
39566 bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	209 def testpopoldest(self):
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	210 d = util.lrucachedict(4)
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	211 d.insert('a', 'va', cost=10)
ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	212 d.insert('b', 'vb', cost=5)
39566 bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	213
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	214 self.assertEqual(len(d), 2)
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	215 self.assertEqual(d.popoldest(), ('a', 'va'))
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	216 self.assertEqual(len(d), 1)
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	217 self.assertEqual(d.totalcost, 5)
39566 bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	218 self.assertEqual(d.popoldest(), ('b', 'vb'))
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	219 self.assertEqual(len(d), 0)
39567 ee087f0d7db5 util: allow lrucachedict to track cost of entries Gregory Szorc <gregory.szorc@gmail.com> parents: 39566 diff changeset	220 self.assertEqual(d.totalcost, 0)
39566 bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	221 self.assertIsNone(d.popoldest())
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	222
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	223 d['a'] = 'va'
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	224 d['b'] = 'vb'
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	225 d['c'] = 'vc'
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	226 d['d'] = 'vd'
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	227
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	228 self.assertEqual(d.popoldest(), ('a', 'va'))
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	229 self.assertEqual(len(d), 3)
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	230 for key in ('b', 'c', 'd'):
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	231 self.assertEqual(d[key], 'v%s' % key)
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	232
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	233 d['a'] = 'va'
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	234 self.assertEqual(d.popoldest(), ('b', 'vb'))
bd9d3a89f07b util: add a popoldest() method to lrucachedict Gregory Szorc <gregory.szorc@gmail.com> parents: 39565 diff changeset	235
39568 842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	236 def testmaxcost(self):
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	237 # Item cost is zero by default.
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	238 d = util.lrucachedict(6, maxcost=10)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	239 d['a'] = 'va'
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	240 d['b'] = 'vb'
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	241 d['c'] = 'vc'
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	242 d['d'] = 'vd'
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	243 self.assertEqual(len(d), 4)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	244 self.assertEqual(d.totalcost, 0)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	245
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	246 d.clear()
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	247
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	248 # Insertion to exact cost threshold works without eviction.
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	249 d.insert('a', 'va', cost=6)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	250 d.insert('b', 'vb', cost=4)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	251
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	252 self.assertEqual(len(d), 2)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	253 self.assertEqual(d['a'], 'va')
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	254 self.assertEqual(d['b'], 'vb')
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	255
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	256 # Inserting a new element with 0 cost works.
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	257 d['c'] = 'vc'
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	258 self.assertEqual(len(d), 3)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	259
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	260 # Inserting a new element with cost putting us above high
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	261 # water mark evicts oldest single item.
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	262 d.insert('d', 'vd', cost=1)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	263 self.assertEqual(len(d), 3)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	264 self.assertEqual(d.totalcost, 5)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	265 self.assertNotIn('a', d)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	266 for key in ('b', 'c', 'd'):
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	267 self.assertEqual(d[key], 'v%s' % key)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	268
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	269 # Inserting a new element with enough room for just itself
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	270 # evicts all items before.
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	271 d.insert('e', 've', cost=10)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	272 self.assertEqual(len(d), 1)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	273 self.assertEqual(d.totalcost, 10)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	274 self.assertIn('e', d)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	275
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	276 # Inserting a new element with cost greater than threshold
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	277 # still retains that item.
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	278 d.insert('f', 'vf', cost=11)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	279 self.assertEqual(len(d), 1)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	280 self.assertEqual(d.totalcost, 11)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	281 self.assertIn('f', d)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	282
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	283 # Inserting a new element will evict the last item since it is
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	284 # too large.
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	285 d['g'] = 'vg'
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	286 self.assertEqual(len(d), 1)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	287 self.assertEqual(d.totalcost, 0)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	288 self.assertIn('g', d)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	289
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	290 d.clear()
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	291
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	292 d.insert('a', 'va', cost=7)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	293 d.insert('b', 'vb', cost=3)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	294 self.assertEqual(len(d), 2)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	295
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	296 # Replacing a value with smaller cost won't result in eviction.
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	297 d.insert('b', 'vb2', cost=2)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	298 self.assertEqual(len(d), 2)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	299
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	300 # Replacing a value with a higher cost will evict when threshold
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	301 # exceeded.
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	302 d.insert('b', 'vb3', cost=4)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	303 self.assertEqual(len(d), 1)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	304 self.assertNotIn('a', d)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	305
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	306 def testmaxcostcomplex(self):
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	307 d = util.lrucachedict(100, maxcost=100)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	308 d.insert('a', 'va', cost=9)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	309 d.insert('b', 'vb', cost=21)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	310 d.insert('c', 'vc', cost=7)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	311 d.insert('d', 'vc', cost=50)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	312 self.assertEqual(d.totalcost, 87)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	313
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	314 # Inserting new element should free multiple elements so we hit
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	315 # low water mark.
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	316 d.insert('e', 'vd', cost=25)
39570 f296c0b366c8 util: lower water mark when removing nodes after cost limit reached Gregory Szorc <gregory.szorc@gmail.com> parents: 39568 diff changeset	317 self.assertEqual(len(d), 2)
39568 842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	318 self.assertNotIn('a', d)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	319 self.assertNotIn('b', d)
39570 f296c0b366c8 util: lower water mark when removing nodes after cost limit reached Gregory Szorc <gregory.szorc@gmail.com> parents: 39568 diff changeset	320 self.assertNotIn('c', d)
39568 842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	321 self.assertIn('d', d)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	322 self.assertIn('e', d)
842cd0bdda75 util: teach lrucachedict to enforce a max total cost Gregory Szorc <gregory.szorc@gmail.com> parents: 39567 diff changeset	323
18603 2251b3184e6e util: add an LRU cache dict Siddharth Agarwal <sid0@fb.com> parents: diff changeset	324 if __name__ == '__main__':
39562 067f7d2c7d60 tests: rewrite test-lrucachedict.py to use unittest Gregory Szorc <gregory.szorc@gmail.com> parents: 29828 diff changeset	325 silenttestrunner.main(__name__)

Mercurial > public > mercurial-scm > hg

annotate tests/test-lrucachedict.py @ 39570:f296c0b366c8