annotate tests/test-pathencode.py @ 49658:523cacdfd324

delta-find: set the default candidate chunk size to 10

I ran performance and storage tests on repositories of various sizes and shapes
for the following values of the config : 5, 10, 20, 50, 100, no-chunking

The performance tests do not show any statistical impact on computation
times for large pushes and pulls.

For searching for an individual delta, this can provide a significant
performance improvement with a minor degradation of space-quality on the
result. (see data at the end of the commit).

For overall store size, the change :
- does not have any impact on many small repositories,
- has an observable, but very negligible impact on most larger repositories.
- One private repository we use for testing sees a small increase in size
  (1%) in the narrower version.
  We will try to get more numbers on a larger version of that repository to
  make sure nothing pathological happens.

We pick "10" as the limit as "5" seems a bit more risky.

There are room to improve the current code, by using more aggressive filtering
and better (i.e any) sorting of the candidates. However this is already a large
improvement for pathological cases, with little impact in the common
situations.

The initial motivation for this change is to fix performance of delta
computation for a file where the previous code ended up testing 20 000 possible
candidate-bases in one go, which is… slow. This affected about ½ of the file
revisions leading to atrocious performance, especially during some push/pull
operations.


Details about individual delta finding timing:
----------------------------------------------

The vast majority of benchmark cases are unchanged but the three below. The first
two do not see any impact on the final delta. The last one sees a change in
delta-size that is negligible compared to the full text size.


### data-env-vars.name     = mozilla-try-2019-02-18-zstd-sparse-revlog
  # benchmark.name         = perf-delta-find
  # benchmark.variants.rev = manifest-snapshot-many-tries-a (revision 756096)
∞:   5.844783
5:   4.473523  (-23.46%)
10:  4.970053  (-14.97%)
20:  5.770386   (-1.27%)
50   5.821358
100: 5.834887

MANIFESTLOG: rev = 756096: (no-limit)
    delta-base = 301840
    search-rounds = 6
    try-count = 60
    delta-type = snapshot
    snap-depth = 7
    delta-size = 179

MANIFESTLOG: rev=756096: (limit = 10)
    delta-base=301840
    search-rounds=9
    try-count=51
    delta-type=snapshot
    snap-depth=7
    delta-size=179

### data-env-vars.name     = mozilla-try-2019-02-18-zstd-sparse-revlog
  # benchmark.name         = perf-delta-find
  # benchmark.variants.rev = manifest-snapshot-many-tries-d (revision 754060)
∞:   5.017663
5:   3.655931  (-27.14%)
10:  4.095436  (-18.38%)
20:  4.828949   (-3.76%)
50   4.987574
100: 4.994889

MANIFESTLOG: rev=754060: (no limit)
    delta-base=301840
    search-rounds=5
    try-count=53
    delta-type=snapshot
    snap-depth=7
    delta-size = 179

MANIFESTLOG: rev=754060: (limite = 10)
    delta-base=301840
    search-rounds=8
    try-count=45
    delta-type=snapshot
    snap-depth=7
    delta-size = 179

### data-env-vars.name     = mozilla-try-2019-02-18-zstd-sparse-revlog
  # benchmark.name         = perf-delta-find
  # bin-env-vars.hg.flavor = rust
  # benchmark.variants.rev = manifest-snapshot-many-tries-e (revision 693368)
∞:   4.869282
5:   2.039732  (-58.11%)
10:  2.413537  (-50.43%)
20:  4.449639   (-8.62%)
50   4.865863
100: 4.882649

MANIFESTLOG: rev=693368:
    delta-base=693336
    search-rounds=6
    try-count=53
    delta-type=snapshot
    snap-depth=6
    full-test-size=131065
    delta-size=199

MANIFESTLOG: rev=693368:
    delta-base=278023
    search-rounds=5
    try-count=21
    delta-type=snapshot
    snap-depth=4
    full-test-size=131065
    delta-size=278


Raw data for store size (in bytes) for various chunk size value below:
----------------------------------------------------------------------


   440 134 384          5 pypy/.hg/store/
   440 134 384         10 pypy/.hg/store/
   440 134 384         20 pypy/.hg/store/
   440 134 384         50 pypy/.hg/store/
   440 134 384        100 pypy/.hg/store/
   440 134 384        ... pypy/.hg/store/

   666 987 471          5 netbsd-xsrc-2022-11-15/.hg/store/
   666 987 471         10 netbsd-xsrc-2022-11-15/.hg/store/
   666 987 471         20 netbsd-xsrc-2022-11-15/.hg/store/
   666 987 471         50 netbsd-xsrc-2022-11-15/.hg/store/
   666 987 471        100 netbsd-xsrc-2022-11-15/.hg/store/
   666 987 471        ... netbsd-xsrc-2022-11-15/.hg/store/

   852 844 884          5 netbsd-pkgsrc-2022-11-15/.hg/store/
   852 844 884         10 netbsd-pkgsrc-2022-11-15/.hg/store/
   852 844 884         20 netbsd-pkgsrc-2022-11-15/.hg/store/
   852 844 884         50 netbsd-pkgsrc-2022-11-15/.hg/store/
   852 844 884        100 netbsd-pkgsrc-2022-11-15/.hg/store/
   852 844 884        ... netbsd-pkgsrc-2022-11-15/.hg/store/

 1 504 227 981           5 netbeans-2018-08-01-sparse-zstd/.hg/store/
 1 504 227 871         10 netbeans-2018-08-01-sparse-zstd/.hg/store/
 1 504 227 813         20 netbeans-2018-08-01-sparse-zstd/.hg/store/
 1 504 227 813         50 netbeans-2018-08-01-sparse-zstd/.hg/store/
 1 504 227 813        100 netbeans-2018-08-01-sparse-zstd/.hg/store/
 1 504 227 813        ... netbeans-2018-08-01-sparse-zstd/.hg/store/

 3 875 801 068          5 netbsd-src-2022-11-15/.hg/store/
 3 875 696 767         10 netbsd-src-2022-11-15/.hg/store/
 3 875 696 757         20 netbsd-src-2022-11-15/.hg/store/
 3 875 696 653         50 netbsd-src-2022-11-15/.hg/store/
 3 875 696 653        100 netbsd-src-2022-11-15/.hg/store/
 3 875 696 653        ... netbsd-src-2022-11-15/.hg/store/

 4 531 441 314          5 mozilla-central/.hg/store/
 4 531 435 157         10 mozilla-central/.hg/store/
 4 531 432 045         20 mozilla-central/.hg/store/
 4 531 429 119         50 mozilla-central/.hg/store/
 4 531 429 119        100 mozilla-central/.hg/store/
 4 531 429 119        ... mozilla-central/.hg/store/

 4 875 861 390          5 mozilla-unified/.hg/store/
 4 875 855 155         10 mozilla-unified/.hg/store/
 4 875 852 027         20 mozilla-unified/.hg/store/
 4 875 848 851         50 mozilla-unified/.hg/store/
 4 875 848 851        100 mozilla-unified/.hg/store/
 4 875 848 851        ... mozilla-unified/.hg/store/

11 498 764 601          5 mozilla-try/.hg/store/
11 497 968 858         10 mozilla-try/.hg/store/
11 497 958 730         20 mozilla-try/.hg/store/
11 497 927 156         50 mozilla-try/.hg/store/
11 497 925 963        100 mozilla-try/.hg/store/
11 497 923 428        ... mozilla-try/.hg/store/

10 047 914 031          5 private-repo
 9 969 132 101         10 private-repo
 9 944 745 015         20 private-repo
 9 939 756 703         50 private-repo
 9 939 833 016        100 private-repo
 9 939 822 035        ... private-repo

# This is a randomized test that generates different pathnames every
# time it is invoked, and tests the encoding of those pathnames.
#
# It uses a simple probabilistic model to generate valid pathnames
# that have proven likely to expose bugs and divergent behavior in
# different encoding implementations.


import binascii
import collections
import itertools
import math
import os
import random
import sys
import time
from mercurial import (
    pycompat,
    store,
)

validchars = set(map(pycompat.bytechr, range(0, 256)))
alphanum = range(ord('A'), ord('Z'))

for c in (b'\0', b'/'):
    validchars.remove(c)

winreserved = (
    b'aux con prn nul'.split()
    + [b'com%d' % i for i in range(1, 10)]
    + [b'lpt%d' % i for i in range(1, 10)]
)


def casecombinations(names):
    '''Build all case-diddled combinations of names.'''

    combos = set()

    for r in names:
        for i in range(len(r) + 1):
            for c in itertools.combinations(range(len(r)), i):
                d = r
                for j in c:
                    d = b''.join((d[:j], d[j : j + 1].upper(), d[j + 1 :]))
                combos.add(d)
    return sorted(combos)


def buildprobtable(fp, cmd='hg manifest tip'):
    """Construct and print a table of probabilities for path name
    components.  The numbers are percentages."""

    counts = collections.defaultdict(lambda: 0)
    for line in os.popen(cmd).read().splitlines():
        if line[-2:] in ('.i', '.d'):
            line = line[:-2]
        if line.startswith('data/'):
            line = line[5:]
        for c in line:
            counts[c] += 1
    for c in '\r/\n':
        counts.pop(c, None)
    t = sum(counts.values()) / 100.0
    fp.write('probtable = (')
    for i, (k, v) in enumerate(
        sorted(counts.items(), key=lambda x: x[1], reverse=True)
    ):
        if (i % 5) == 0:
            fp.write('\n    ')
        vt = v / t
        if vt < 0.0005:
            break
        fp.write('(%r, %.03f), ' % (k, vt))
    fp.write('\n    )\n')


# A table of character frequencies (as percentages), gleaned by
# looking at filelog names from a real-world, very large repo.

probtable = (
    (b't', 9.828),
    (b'e', 9.042),
    (b's', 8.011),
    (b'a', 6.801),
    (b'i', 6.618),
    (b'g', 5.053),
    (b'r', 5.030),
    (b'o', 4.887),
    (b'p', 4.363),
    (b'n', 4.258),
    (b'l', 3.830),
    (b'h', 3.693),
    (b'_', 3.659),
    (b'.', 3.377),
    (b'm', 3.194),
    (b'u', 2.364),
    (b'd', 2.296),
    (b'c', 2.163),
    (b'b', 1.739),
    (b'f', 1.625),
    (b'6', 0.666),
    (b'j', 0.610),
    (b'y', 0.554),
    (b'x', 0.487),
    (b'w', 0.477),
    (b'k', 0.476),
    (b'v', 0.473),
    (b'3', 0.336),
    (b'1', 0.335),
    (b'2', 0.326),
    (b'4', 0.310),
    (b'5', 0.305),
    (b'9', 0.302),
    (b'8', 0.300),
    (b'7', 0.299),
    (b'q', 0.298),
    (b'0', 0.250),
    (b'z', 0.223),
    (b'-', 0.118),
    (b'C', 0.095),
    (b'T', 0.087),
    (b'F', 0.085),
    (b'B', 0.077),
    (b'S', 0.076),
    (b'P', 0.076),
    (b'L', 0.059),
    (b'A', 0.058),
    (b'N', 0.051),
    (b'D', 0.049),
    (b'M', 0.046),
    (b'E', 0.039),
    (b'I', 0.035),
    (b'R', 0.035),
    (b'G', 0.028),
    (b'U', 0.026),
    (b'W', 0.025),
    (b'O', 0.017),
    (b'V', 0.015),
    (b'H', 0.013),
    (b'Q', 0.011),
    (b'J', 0.007),
    (b'K', 0.005),
    (b'+', 0.004),
    (b'X', 0.003),
    (b'Y', 0.001),
)

for c, _ in probtable:
    validchars.remove(c)
validchars = list(validchars)


def pickfrom(rng, table):
    c = 0
    r = rng.random() * sum(i[1] for i in table)
    for i, p in table:
        c += p
        if c >= r:
            return i


reservedcombos = casecombinations(winreserved)

# The first component of a name following a slash.

firsttable = (
    (lambda rng: pickfrom(rng, probtable), 90),
    (lambda rng: rng.choice(validchars), 5),
    (lambda rng: rng.choice(reservedcombos), 5),
)

# Components of a name following the first.

resttable = firsttable[:-1]

# Special suffixes.

internalsuffixcombos = casecombinations(b'.hg .i .d'.split())

# The last component of a path, before a slash or at the end of a name.

lasttable = resttable + (
    (lambda rng: b'', 95),
    (lambda rng: rng.choice(internalsuffixcombos), 5),
)


def makepart(rng, k):
    '''Construct a part of a pathname, without slashes.'''

    p = pickfrom(rng, firsttable)(rng)
    l = len(p)
    ps = [p]
    maxl = rng.randint(1, k)
    while l < maxl:
        p = pickfrom(rng, resttable)(rng)
        l += len(p)
        ps.append(p)
    ps.append(pickfrom(rng, lasttable)(rng))
    return b''.join(ps)


def makepath(rng, j, k):
    '''Construct a complete pathname.'''

    return (
        b'data/'
        + b'/'.join(makepart(rng, k) for _ in range(j))
        + rng.choice([b'.d', b'.i'])
    )


def genpath(rng, count):
    '''Generate random pathnames with gradually increasing lengths.'''

    mink, maxk = 1, 4096

    def steps():
        for i in range(count):
            yield mink + int(round(math.sqrt((maxk - mink) * float(i) / count)))

    for k in steps():
        x = rng.randint(1, k)
        y = rng.randint(1, k)
        yield makepath(rng, x, y)


def runtests(rng, seed, count):
    nerrs = 0
    for p in genpath(rng, count):
        h = store._pathencode(p)  # uses C implementation, if available
        r = store._hybridencode(p, True)  # reference implementation in Python
        if h != r:
            if nerrs == 0:
                print('seed:', hex(seed)[:-1], file=sys.stderr)
            print("\np: '%s'" % p.encode("string_escape"), file=sys.stderr)
            print("h: '%s'" % h.encode("string_escape"), file=sys.stderr)
            print("r: '%s'" % r.encode("string_escape"), file=sys.stderr)
            nerrs += 1
    return nerrs


def main():
    import getopt

    # Empirically observed to take about a second to run
    count = 100
    seed = None
    opts, args = getopt.getopt(
        sys.argv[1:], 'c:s:', ['build', 'count=', 'seed=']
    )
    for o, a in opts:
        if o in ('-c', '--count'):
            count = int(a)
        elif o in ('-s', '--seed'):
            seed = int(a, base=0)  # accepts base 10 or 16 strings
        elif o == '--build':
            buildprobtable(
                sys.stdout,
                'find .hg/store/data -type f && '
                'cat .hg/store/fncache 2>/dev/null',
            )
            sys.exit(0)

    if seed is None:
        try:
            seed = int(binascii.hexlify(os.urandom(16)), 16)
        except AttributeError:
            seed = int(time.time() * 1000)

    rng = random.Random(seed)
    if runtests(rng, seed, count):
        sys.exit(1)


if __name__ == '__main__':
    main()