treemanifest: use visitchildrenset when doing a walk
For this series, starting at 'introduce lazy loading of subdirs' and ending with
this commit, we get the following timing numbers, using roughly the same
methodology and setup that we did in an earlier commit.
"before" is
6268fed3.
diff --git:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 1.585 s +- 0.034 s | 1.574 s +- 0.045 s | 99.3%
m-u | | x | 1.591 s +- 0.024 s | 1.601 s +- 0.034 s | 100.6%
m-u | x | | 1.579 s +- 0.032 s | 1.603 s +- 0.029 s | 101.5%
m-u | x | x | 109.8 ms +- 2.1 ms | 108.8 ms +- 2.2 ms | 99.1%
l-d-r | | | 234.6 ms +- 5.1 ms | 240.1 ms +- 7.9 ms | 102.3%
l-d-r | | x | 238.3 ms +- 8.1 ms | 232.2 ms +- 6.3 ms | 97.4%
l-d-r | x | | 120.0 ms +- 2.7 ms | 119.6 ms +- 2.1 ms | 99.7%
l-d-r | x | x | 120.2 ms +- 1.6 ms | 119.1 ms +- 1.6 ms | 99.1%
diff -c . --git:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 356.9 ms +- 5.6 ms | 355.9 ms +- 5.6 ms | 99.7%
m-u | | x | 209.1 ms +- 3.3 ms | 205.8 ms +- 2.6 ms | 98.4%
m-u | x | | 418.3 ms +- 14.0 ms | 350.8 ms +- 7.7 ms | 83.9% <--
m-u | x | x | 168.3 ms +- 1.5 ms | 168.1 ms +- 2.7 ms | 99.9%
l-d-r | | | 100.5 ms +- 2.1 ms | 99.1 ms +- 1.6 ms | 98.6%
l-d-r | | x | 5.672 s +- 0.133 s | 4.335 s +- 0.051 s | 76.4% <--
l-d-r | x | | 102.8 ms +- 2.8 ms | 100.4 ms +- 1.7 ms | 97.7%
l-d-r | x | x | 1.025 s +- 0.028 s | 875.9 ms +- 12.1 ms | 85.5% <--
rebase -r . --keep -d .^^:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 6.654 s +- 0.137 s | 6.718 s +- 0.046 s | 101.0%
m-u | | x | 6.672 s +- 0.104 s | 6.716 s +- 0.143 s | 100.7%
m-u | x | | 6.661 s +- 0.072 s | 6.658 s +- 0.066 s | 100.0%
m-u | x | x | 696.0 ms +- 49.0 ms | 696.2 ms +- 54.8 ms | 100.0%
l-d-r | | | 789.1 ms +- 12.5 ms | 793.5 ms +- 17.3 ms | 100.6%
l-d-r | | x | 7.621 s +- 0.194 s | 7.144 s +- 0.116 s | 93.7% <--
l-d-r | x | | 335.4 ms +- 9.7 ms | 339.6 ms +- 10.8 ms | 101.3%
l-d-r | x | x | 6.315 s +- 0.085 s | 5.633 s +- 0.105 s | 89.2% <--
status --change . --copies:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 331.2 ms +- 7.0 ms | 335.1 ms +- 6.5 ms | 101.2%
m-u | | x | 184.0 ms +- 3.8 ms | 183.1 ms +- 3.4 ms | 99.5%
m-u | x | | 330.5 ms +- 7.2 ms | 332.7 ms +- 6.9 ms | 100.7%
m-u | x | x | 148.7 ms +- 3.5 ms | 147.5 ms +- 2.2 ms | 99.2%
l-d-r | | | 97.3 ms +- 1.3 ms | 98.2 ms +- 2.5 ms | 100.9%
l-d-r | | x | 5.196 s +- 0.030 s | 4.281 s +- 0.025 s | 82.4% <--
l-d-r | x | | 101.4 ms +- 3.1 ms | 100.9 ms +- 1.8 ms | 99.5%
l-d-r | x | x | 1.015 s +- 0.018 s | 861.2 ms +- 11.2 ms | 84.8% <--
status --copies:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 2.356 s +- 0.032 s | 2.369 s +- 0.027 s | 100.6%
m-u | | x | 2.371 s +- 0.041 s | 2.385 s +- 0.028 s | 100.6%
m-u | x | | 2.366 s +- 0.036 s | 2.379 s +- 0.030 s | 100.5%
m-u | x | x | 121.8 ms +- 3.8 ms | 121.1 ms +- 2.7 ms | 99.4%
l-d-r | | | 726.2 ms +- 12.9 ms | 723.1 ms +- 12.7 ms | 99.6%
l-d-r | | x | 738.7 ms +- 11.2 ms | 741.3 ms +- 11.1 ms | 100.4%
l-d-r | x | | 215.9 ms +- 3.6 ms | 214.7 ms +- 5.9 ms | 99.4%
l-d-r | x | x | 213.1 ms +- 2.5 ms | 212.8 ms +- 4.5 ms | 99.9%
update $rev^; ~/src/hg/hg{hg}/hg update $rev:
repo | N | T | before (mean +- stdev) | after (mean +- stdev) | % of before
------+---+---+------------------------+-----------------------+------------
m-u | | | 3.922 s +- 0.045 s | 3.937 s +- 0.034 s | 100.4%
m-u | | x | 3.673 s +- 0.028 s | 3.660 s +- 0.035 s | 99.6%
m-u | x | | 3.959 s +- 0.073 s | 3.904 s +- 0.051 s | 98.6%
m-u | x | x | 417.0 ms +- 13.0 ms | 406.2 ms +- 6.5 ms | 97.4%
l-d-r | | | 534.3 ms +- 12.2 ms | 537.9 ms +- 8.8 ms | 100.7%
l-d-r | | x | 10.671 s +- 0.275 s | 10.111 s +- 0.114 s | 94.8% <--
l-d-r | x | | 309.7 ms +- 3.5 ms | 307.9 ms +- 4.0 ms | 99.4%
l-d-r | x | x | 1.837 s +- 0.014 s | 1.887 s +- 0.035 s | 102.7%
Differential Revision: https://phab.mercurial-scm.org/D4371
# Randomized torture test generation for bdiff
from __future__ import absolute_import, print_function
import random
import sys
from mercurial import (
mdiff,
)
def reducetest(a, b):
tries = 0
reductions = 0
print("reducing...")
while tries < 1000:
a2 = "\n".join(l for l in a.splitlines()
if random.randint(0, 100) > 0) + "\n"
b2 = "\n".join(l for l in b.splitlines()
if random.randint(0, 100) > 0) + "\n"
if a2 == a and b2 == b:
continue
if a2 == b2:
continue
tries += 1
try:
test1(a, b)
except Exception as inst:
reductions += 1
tries = 0
a = a2
b = b2
print("reduced:", reductions, len(a) + len(b),
repr(a), repr(b))
try:
test1(a, b)
except Exception as inst:
print("failed:", inst)
sys.exit(0)
def test1(a, b):
d = mdiff.textdiff(a, b)
if not d:
raise ValueError("empty")
c = mdiff.patches(a, [d])
if c != b:
raise ValueError("bad")
def testwrap(a, b):
try:
test1(a, b)
return
except Exception as inst:
pass
print("exception:", inst)
reducetest(a, b)
def test(a, b):
testwrap(a, b)
testwrap(b, a)
def rndtest(size, noise):
a = []
src = " aaaaaaaabbbbccd"
for x in xrange(size):
a.append(src[random.randint(0, len(src) - 1)])
while True:
b = [c for c in a if random.randint(0, 99) > noise]
b2 = []
for c in b:
b2.append(c)
while random.randint(0, 99) < noise:
b2.append(src[random.randint(0, len(src) - 1)])
if b2 != a:
break
a = "\n".join(a) + "\n"
b = "\n".join(b2) + "\n"
test(a, b)
maxvol = 10000
startsize = 2
while True:
size = startsize
count = 0
while size < maxvol:
print(size)
volume = 0
while volume < maxvol:
rndtest(size, 2)
volume += size
count += 2
size *= 2
maxvol *= 4
startsize *= 4