tests/hghave
author Gregory Szorc <gregory.szorc@gmail.com>
Sun, 06 Dec 2015 19:04:10 -0800
changeset 27371 45d996a566d7
parent 26068 05e7f57c74ac
child 28047 863075fd4cd0
permissions -rwxr-xr-x
util: reimplement lrucachedict As part of attempting to more aggressively use the existing lrucachedict, collections.deque operations were frequently showing up in profiling output, negating benefits of caching. Searching the internet seems to tell me that the most efficient way to implement an LRU cache in Python is to have a dict indexing the cached entries and then to use a doubly linked list to track freshness of each entry. So, this patch replaces our existing lrucachedict with a version using such a pattern. The recently introduced perflrucachedict command reveals the following timings for 10,000 operations for the following cache sizes for the existing cache: n=4 init=0.004079 gets=0.003632 sets=0.005188 mixed=0.005402 n=8 init=0.004045 gets=0.003998 sets=0.005064 mixed=0.005328 n=16 init=0.004011 gets=0.004496 sets=0.005021 mixed=0.005555 n=32 init=0.004064 gets=0.005611 sets=0.005188 mixed=0.006189 n=64 init=0.003975 gets=0.007684 sets=0.005178 mixed=0.007245 n=128 init=0.004121 gets=0.012005 sets=0.005422 mixed=0.009471 n=256 init=0.004143 gets=0.020295 sets=0.005227 mixed=0.013612 n=512 init=0.004039 gets=0.036703 sets=0.005243 mixed=0.020685 n=1024 init=0.004193 gets=0.068142 sets=0.005251 mixed=0.033064 n=2048 init=0.004070 gets=0.133383 sets=0.005160 mixed=0.050359 n=4096 init=0.004053 gets=0.265194 sets=0.004868 mixed=0.048352 n=8192 init=0.004087 gets=0.542218 sets=0.004562 mixed=0.032753 n=16384 init=0.004106 gets=1.064055 sets=0.004179 mixed=0.020367 n=32768 init=0.004034 gets=2.097620 sets=0.004260 mixed=0.013031 n=65536 init=0.004108 gets=4.106390 sets=0.004268 mixed=0.010191 As the data shows, the existing cache's retrieval performance diminishes linearly with cache size. (Keep in mind the microbenchmark is testing 100% cache hit rate.) The new cache implementation reveals the following: n=4 init=0.006665 gets=0.006541 sets=0.005733 mixed=0.006876 n=8 init=0.006649 gets=0.006374 sets=0.005663 mixed=0.006899 n=16 init=0.006570 gets=0.006504 sets=0.005799 mixed=0.007057 n=32 init=0.006854 gets=0.006459 sets=0.005747 mixed=0.007034 n=64 init=0.006580 gets=0.006495 sets=0.005740 mixed=0.006992 n=128 init=0.006534 gets=0.006739 sets=0.005648 mixed=0.007124 n=256 init=0.006669 gets=0.006773 sets=0.005824 mixed=0.007151 n=512 init=0.006701 gets=0.007061 sets=0.006042 mixed=0.007372 n=1024 init=0.006641 gets=0.007620 sets=0.006387 mixed=0.007464 n=2048 init=0.006517 gets=0.008598 sets=0.006871 mixed=0.008077 n=4096 init=0.006720 gets=0.010933 sets=0.007854 mixed=0.008663 n=8192 init=0.007383 gets=0.015969 sets=0.010288 mixed=0.008896 n=16384 init=0.006660 gets=0.025447 sets=0.011208 mixed=0.008826 n=32768 init=0.006658 gets=0.044390 sets=0.011192 mixed=0.008943 n=65536 init=0.006836 gets=0.082736 sets=0.011151 mixed=0.008826 Let's go through the results. The new cache takes longer to construct. ~6.6ms vs ~4.1ms. However, this is measuring 10,000 __init__ calls, so the difference is ~0.2us/instance. We currently only create lrucachedict for manifest instances, so this regression is not likely relevant. The new cache is slightly slower for retrievals for cache sizes < 1024. It's worth noting that the only existing use of lurcachedict is in manifest.py and the default cache size is 4. This regression is worrisome. However, for n=4, the delta is ~2.9s for 10,000 lookups, or ~0.29us/op. Again, this is a marginal regression and likely not relevant in the real world. Timing `hg log -p -l 100` for mozilla-central reveals that cache lookup times are dominated by decompression and fulltext resolution (even with lz4 manifests). The new cache is significantly faster for retrievals at larger capacities. Whereas the old implementation has retrieval performance linear with cache capacity, the new cache is constant time until much larger values. And, when it does start to increase significantly, it is a few magnitudes faster than the current cache. The new cache does appear to be slower for sets when capacity is large. However, performance is similar for smaller capacities. Of course, caches should generally be optimized for retrieval performance because if a cache is getting more sets than gets, it doesn't really make sense to cache. If this regression is worrisome, again, taking the largest regression at n=65536 of ~6.9ms for 10,000 results in a regression of ~0.68us/op. This is not significant in the grand scheme of things. Overall, the new cache is performant at retrievals at much larger capacity values which makes it a generally more useful cache backend. While there are regressions, their absolute value is extremely small. Since we aren't using lrucachedict aggressively today, these regressions should not be relevant. The improved scalability of lrucachedict should enable us to more aggressively utilize lrucachedict for more granular caching (read: higher capacity caches) in the near future. The impetus for this patch is to establish a cache of decompressed revlog revisions, notably manifest revisions. And since delta chains can grow to >10,000 and cache hit rate can be high, the improved retrieval performance of lrucachedict should be relevant.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
4881
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
     1
#!/usr/bin/env python
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
     2
"""Test the running system for features availability. Exit with zero
5084
80309fa23cdb hghave: feature absence can be checked by prefixing with 'no-'
Patrick Mezard <pmezard@gmail.com>
parents: 5081
diff changeset
     3
if all features are there, non-zero otherwise. If a feature name is
80309fa23cdb hghave: feature absence can be checked by prefixing with 'no-'
Patrick Mezard <pmezard@gmail.com>
parents: 5081
diff changeset
     4
prefixed with "no-", the absence of feature is tested.
4881
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
     5
"""
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
     6
import optparse
25732
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
     7
import os, sys
16966
23f621ca04b5 tests/hghave: extract hghave.py
Adrian Buehlmann <adrian@cadifra.com>
parents: 16891
diff changeset
     8
import hghave
9446
57d682d7d2da test-gendoc: test documentation generation
Martin Geisler <mg@lazybytes.net>
parents: 9395
diff changeset
     9
16966
23f621ca04b5 tests/hghave: extract hghave.py
Adrian Buehlmann <adrian@cadifra.com>
parents: 16891
diff changeset
    10
checks = hghave.checks
4881
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    11
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    12
def list_features():
22762
05b3238ba901 tests: make hghave list features alphabetically
Yuya Nishihara <yuya@tcha.org>
parents: 18229
diff changeset
    13
    for name, feature in sorted(checks.iteritems()):
4881
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    14
        desc = feature[1]
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    15
        print name + ':', desc
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    16
8059
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    17
def test_features():
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    18
    failed = 0
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    19
    for name, feature in checks.iteritems():
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    20
        check, _ = feature
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    21
        try:
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    22
            check()
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    23
        except Exception, e:
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    24
            print "feature %s failed:  %s" % (name, e)
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    25
            failed += 1
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    26
    return failed
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    27
4881
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    28
parser = optparse.OptionParser("%prog [options] [features]")
8059
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    29
parser.add_option("--test-features", action="store_true",
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    30
                  help="test available features")
4881
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    31
parser.add_option("--list-features", action="store_true",
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    32
                  help="list available features")
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    33
26068
05e7f57c74ac hghave: remove quiet option
Gregory Szorc <gregory.szorc@gmail.com>
parents: 26067
diff changeset
    34
def _loadaddon():
25732
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    35
    if 'TESTDIR' in os.environ:
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    36
        # loading from '.' isn't needed, because `hghave` should be
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    37
        # running at TESTTMP in this case
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    38
        path = os.environ['TESTDIR']
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    39
    else:
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    40
        path = '.'
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    41
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    42
    if not os.path.exists(os.path.join(path, 'hghaveaddon.py')):
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    43
        return
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    44
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    45
    sys.path.insert(0, path)
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    46
    try:
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    47
        import hghaveaddon
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    48
    except BaseException, inst:
26068
05e7f57c74ac hghave: remove quiet option
Gregory Szorc <gregory.szorc@gmail.com>
parents: 26067
diff changeset
    49
        sys.stderr.write('failed to import hghaveaddon.py from %r: %s\n'
05e7f57c74ac hghave: remove quiet option
Gregory Szorc <gregory.szorc@gmail.com>
parents: 26067
diff changeset
    50
                         % (path, inst))
25732
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    51
        sys.exit(2)
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    52
    sys.path.pop(0)
b94df10cc3b5 hghave: allow adding customized features at runtime
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 22762
diff changeset
    53
4881
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    54
if __name__ == '__main__':
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    55
    options, args = parser.parse_args()
26068
05e7f57c74ac hghave: remove quiet option
Gregory Szorc <gregory.szorc@gmail.com>
parents: 26067
diff changeset
    56
    _loadaddon()
4881
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    57
    if options.list_features:
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    58
        list_features()
c51c9bc4579d Add hghave utility and run-tests.py support.
Patrick Mezard <pmezard@gmail.com>
parents:
diff changeset
    59
        sys.exit(0)
5081
ea7b982b6c08 Remove trailing spaces
Thomas Arendsen Hein <thomas@intevation.de>
parents: 5074
diff changeset
    60
8059
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    61
    if options.test_features:
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    62
        sys.exit(test_features())
41a2c5cbcb6a hghave: checking that all targets are Exception-free
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 7823
diff changeset
    63
26068
05e7f57c74ac hghave: remove quiet option
Gregory Szorc <gregory.szorc@gmail.com>
parents: 26067
diff changeset
    64
    hghave.require(args)