← Back to benchmarkbenchmark_linux_maintainers.py
#!/usr/bin/env python3
"""Benchmark an ordered Linux MAINTAINERS manifest with version stores or chained deltas."""
import argparse
import hashlib
import json
import os
import platform
import shutil
import statistics
import subprocess
import sys
import tempfile
import time
from pathlib import Path
ROOT = Path(__file__).resolve().parent
STORES = ('git', 'fossil', 'nab', 'dnab', 'rcs', 'hg', 'chg')
DELTAS = ('xdelta3', 'rdiff', 'bsdiff', 'zstd')
def digest(data):
return hashlib.sha256(data).hexdigest()
def filehash(path):
return digest(Path(path).read_bytes())
def stats(samples):
ordered = sorted(samples)
return {'median_ms': statistics.median(samples), 'sum_ms': sum(samples),
'min_ms': ordered[0], 'max_ms': ordered[-1],
'p95_ms': ordered[min(len(ordered) - 1, int(len(ordered) * .95))],
'samples_ms': samples}
def tree_bytes(path):
return sum(p.stat().st_size for p in path.rglob('*') if p.is_file())
def main():
parser = argparse.ArgumentParser(description=__doc__)
parser.add_argument('manifest', type=Path)
parser.add_argument('--tools', nargs='+', choices=STORES + DELTAS, default=list(STORES + DELTAS))
parser.add_argument('--runs', type=int, default=3)
parser.add_argument('--reads', type=int, default=3)
parser.add_argument('--output', type=Path, required=True)
parser.add_argument('--resume', type=Path, help='reuse complete matching trials from a previous partial report')
parser.add_argument('--hg-server', default=shutil.which('hg'))
parser.add_argument('--nab', default=str(ROOT.parent / 'nab' / 'nab'))
args = parser.parse_args()
if args.runs < 1 or args.reads < 1 or len(set(args.tools)) != len(args.tools):
parser.error('runs and reads must be positive and tools unique')
manifest_path = args.manifest.resolve()
manifest = json.loads(manifest_path.read_bytes())
revisions = manifest['revisions']
if len(revisions) != 1000 or manifest['count'] != 1000:
raise ValueError('expected exactly 1000 revisions')
paths = []
for i, rev in enumerate(revisions):
if rev['index'] != i or (i and rev['parentid'] != revisions[i-1]['revid']):
raise ValueError(f'non-contiguous history at {i}')
if i and rev['timestamp'] < revisions[i-1]['timestamp']:
raise ValueError(f'non-chronological history at {i}')
path = (manifest_path.parent / rev['path']).resolve()
data = path.read_bytes()
if len(data) != rev['bytes'] or digest(data) != rev['sha256']:
raise ValueError(f'manifest mismatch at {i}: {path}')
paths.append(path)
needed = {'git': ['git'], 'fossil': ['fossil'], 'nab': ['nab'], 'dnab': ['dnab'],
'rcs': ['rcs', 'ci', 'co'], 'hg': ['hg'], 'chg': ['hg', 'chg'],
'xdelta3': ['xdelta3'], 'rdiff': ['rdiff'], 'bsdiff': ['bsdiff', 'bspatch'], 'zstd': ['zstd']}
binaries = {}
for tool in args.tools:
for name in needed[tool]:
path = args.hg_server if name == 'hg' else args.nab if name == 'nab' else shutil.which(name)
if not path:
parser.error(f'missing executable: {name}')
binaries[name] = str(Path(path).resolve())
args.output = args.output.resolve()
if args.output.exists():
parser.error('output already exists')
args.output.parent.mkdir(parents=True, exist_ok=True)
report = {'completed': False, 'manifest': str(manifest_path), 'manifest_sha256': filehash(manifest_path),
'script_sha256': filehash(__file__), 'platform': platform.platform(), 'python': sys.version,
'command': sys.argv, 'runs': args.runs, 'reads': args.reads,
'binaries': {name: {'path': p, 'sha256': filehash(p)} for name, p in binaries.items()},
'protocol': '1000 ordered exact manifest bytes, SHA-256 verified before timing. CLI wall time includes startup; working-file writes, initialization, hashes and verification excluded. Git add+commit+repack -ad on every revision. Fossil tags add metadata. RCS binary mode. chg uses a warmed isolated server. Store latest reads capture stdout; every store revision is validated. Delta encoding uses original predecessor; decoding sequentially uses its own previous reconstruction; reported decode sum is newest chain rebuild, excluding hash and other intervening work. rdiff encode includes signature. Delta storage is base plus all patches. Logical repository sizes exclude working files. Warm caches and background load uncontrolled.',
'trials': []}
if args.resume:
previous = json.loads(args.resume.read_text())
if previous['manifest_sha256'] != report['manifest_sha256']:
raise ValueError('resume manifest mismatch')
changed = {name for name in binaries if name not in previous['binaries'] or
previous['binaries'][name]['sha256'] != report['binaries'][name]['sha256']}
report['resumed_from'] = {'path': str(args.resume.resolve()), 'sha256': filehash(args.resume),
'script_sha256': previous['script_sha256'], 'changed_binaries': sorted(changed)}
for row in previous['trials']:
if row.get('completed') and row['trial'] < args.runs and row['tool'] in args.tools and not (set(needed[row['tool']]) & changed):
report['trials'].append(row)
def save():
tmp = args.output.with_suffix(args.output.suffix + '.tmp')
tmp.write_text(json.dumps(report, indent=2) + '\n')
tmp.replace(args.output)
save()
with tempfile.TemporaryDirectory(prefix='linux-maintainers-bench-', dir=ROOT) as temp:
root = Path(temp)
home = root / 'home'
home.mkdir()
env = os.environ.copy()
for key in list(env):
if key.startswith('GIT_'):
del env[key]
env.update(HOME=str(home), GIT_CONFIG_NOSYSTEM='1', GIT_CONFIG_GLOBAL=os.devnull,
GIT_TERMINAL_PROMPT='0', LC_ALL='C', TZ='UTC', USER='benchmark',
HGRCPATH=os.devnull, HGPLAIN='1')
config = root / 'hgrc'
config.write_text('[chgserver]\nskiphash = true\nidletimeout = 3600\n')
chg_env = dict(env, HGRCPATH=str(config), CHGHG=binaries.get('hg', ''), CHGSOCKNAME=str(root / 'chg.sock'))
def call(command, cwd, use_chg=False):
command = list(map(str, command))
start = time.perf_counter_ns()
result = subprocess.run(command, cwd=cwd, env=chg_env if use_chg else env,
stdin=subprocess.DEVNULL, stdout=subprocess.PIPE, stderr=subprocess.PIPE, timeout=300)
ms = (time.perf_counter_ns() - start) / 1e6
if result.returncode:
raise RuntimeError(f'{command!r}: exit {result.returncode}: {result.stderr.decode(errors="replace")} {result.stdout.decode(errors="replace")}')
return ms, result.stdout
for trial in range(args.runs):
for name in args.tools:
if any(row['trial'] == trial and row['tool'] == name and row.get('completed') for row in report['trials']):
print(f'trial {trial+1}, {name}: reused completed result', flush=True)
continue
work = root / f'{trial}-{name}'
work.mkdir()
row = {'trial': trial, 'tool': name, 'completed': False}
report['trials'].append(row)
save()
print(f'trial {trial+1}, {name}: starting', flush=True)
if name in STORES:
folder = work
is_chg = name == 'chg'
def cmd(binary, *rest):
return [binaries['chg'] if binary == 'hg' and is_chg else binaries[binary], *rest]
def run(binary, *rest):
return call(cmd(binary, *rest), folder, is_chg)
if name == 'git':
run('git', 'init', '-q', '.')
for key, value in [('user.name', 'Benchmark'), ('user.email', 'benchmark@example.invalid'), ('gc.auto', '0'), ('commit.gpgsign', 'false'), ('core.hooksPath', os.devnull)]:
run('git', 'config', key, value)
elif name in ('hg', 'chg'):
if is_chg:
run('hg', 'version')
run('hg', 'init', '.')
elif name == 'fossil':
run('fossil', 'init', 'repo.fossil', '--admin-user', 'benchmark')
folder = work / 'checkout'
folder.mkdir()
run('fossil', 'open', work / 'repo.fossil', '--nosync')
elif name == 'rcs':
run('rcs', '-q', '-i', '-kb', '-t-benchmark', 'content,v')
writes, archive_indices = [], []
for i, source in enumerate(paths):
(folder / 'content').write_bytes(source.read_bytes())
elapsed = 0
if name == 'git':
elapsed += run('git', 'add', '--', 'content')[0]
elapsed += run('git', 'commit', '-q', '--allow-empty', '-m', f'version {i}', '--no-verify')[0]
elapsed += run('git', 'repack', '-ad')[0]
elif name in ('hg', 'chg'):
if i == 0:
elapsed += run('hg', 'add', 'content')[0]
elapsed += run('hg', '--config', 'ui.allowemptycommit=True', 'commit', '-m', f'version {i}', '-u', 'benchmark')[0]
elif name == 'fossil':
if i == 0:
elapsed += run('fossil', 'add', 'content')[0]
elapsed += run('fossil', 'commit', '-m', f'version {i}', '--tag', f'bench-{i}', '--allow-empty', '--no-warnings', '--no-verify', '--nosign', '--nosync', '--user-override', 'benchmark', '--hash')[0]
elif name in ('nab', 'dnab'):
elapsed += run(name, 'patch', folder / 'content', folder / f'archive.{name}')[0]
archive_indices.append((archive_indices[-1] if i and revisions[i]['sha256'] == revisions[i-1]['sha256'] else (archive_indices[-1] + 1 if i else 0)))
else:
elapsed += run('ci', '-q', '-f', '-l', '-mbenchmark', 'content')[0]
writes.append(elapsed)
if (i + 1) % 100 == 0:
print(f'trial {trial+1}, {name}: {i+1} writes', flush=True)
ids = run('git', 'rev-list', '--reverse', 'HEAD')[1].decode().splitlines() if name == 'git' else None
if ids is not None and len(ids) != len(paths):
raise RuntimeError('git revision count mismatch')
def get(i):
if name == 'git': return run('git', 'show', f'{ids[i]}:content')
if name in ('hg', 'chg'): return run('hg', 'cat', '-r', str(i), 'content')
if name == 'fossil': return run('fossil', 'cat', 'content', '-r', f'bench-{i}')
if name in ('nab', 'dnab'): return run(name, 'rebuild', folder / f'archive.{name}', str(archive_indices[i]))
return run('co', '-q', f'-p1.{i+1}', '-kb', 'content,v')
latest = []
for _ in range(args.reads):
ms, output = get(999)
if digest(output) != revisions[999]['sha256']: raise RuntimeError(f'{name}: latest mismatch')
latest.append(ms)
if name == 'git': size = tree_bytes(folder / '.git')
elif name in ('hg', 'chg'): size = tree_bytes(folder / '.hg' / 'store') + (folder / '.hg' / 'requires').stat().st_size
elif name == 'fossil': size = (work / 'repo.fossil').stat().st_size
elif name == 'rcs': size = (folder / 'content,v').stat().st_size
else: size = (folder / f'archive.{name}').stat().st_size
for i, rev in enumerate(revisions):
_, output = get(i)
if digest(output) != rev['sha256']: raise RuntimeError(f'{name}: mismatch at {i}')
row.update(write=stats(writes), newest_rebuild=stats(latest), repository_logical_bytes=size, verified_revisions=len(paths))
if name in ('nab', 'dnab'):
row['archive_indices'] = archive_indices
row['consecutive_duplicates_elided'] = len(paths) - archive_indices[-1] - 1
else:
encode, decode, sizes = [], [], []
rebuilt = paths[0]
signature_ms, signature_bytes = [], []
for i in range(1, len(paths)):
previous, current = paths[i-1], paths[i]
patch, output = work / 'delta', work / f'rebuilt-{i}'
b = binaries[name]
if name == 'xdelta3':
enc = call([b, '-e', '-s', previous, current, patch], work)[0]
dec = [b, '-d', '-s', rebuilt, patch, output]
elif name == 'rdiff':
signature = work / 'signature'
sig = call([b, 'signature', previous, signature], work)[0]
signature_ms.append(sig)
signature_bytes.append(signature.stat().st_size)
enc = sig + call([b, 'delta', signature, current, patch], work)[0]
dec = [b, 'patch', rebuilt, patch, output]
elif name == 'bsdiff':
enc = call([b, previous, current, patch], work)[0]
dec = [binaries['bspatch'], rebuilt, output, patch]
else:
enc = call([b, '-q', f'--patch-from={previous}', current, '-o', patch], work)[0]
dec = [b, '-q', '-d', f'--patch-from={rebuilt}', patch, '-o', output]
encode.append(enc)
sizes.append(patch.stat().st_size)
decode.append(call(dec, work)[0])
if filehash(output) != revisions[i]['sha256']: raise RuntimeError(f'{name}: mismatch at {i}')
if rebuilt != paths[0]: rebuilt.unlink()
rebuilt = output
patch.unlink()
if name == 'rdiff': signature.unlink()
if i % 100 == 0: print(f'trial {trial+1}, {name}: {i} patches', flush=True)
row.update(encode=stats(encode), decode=stats(decode), delta_bytes=sizes,
base_bytes=revisions[0]['bytes'], repository_logical_bytes=revisions[0]['bytes'] + sum(sizes),
newest_rebuild_ms=sum(decode), verified_revisions=len(paths))
if name == 'rdiff': row.update(signature=stats(signature_ms), signature_bytes=signature_bytes)
decoder, argv, expected = {'xdelta3': ('xdelta3', ['-V'], 0),
'rdiff': ('rdiff', ['--version'], 0),
'bsdiff': ('bspatch', [], 1),
'zstd': ('zstd', ['--version'], 0)}[name]
startup = []
for _ in range(len(paths) - 1):
start = time.perf_counter_ns()
process = subprocess.run([binaries[decoder], *argv], cwd=work, env=env,
stdin=subprocess.DEVNULL, stdout=subprocess.PIPE,
stderr=subprocess.PIPE, timeout=120)
elapsed = (time.perf_counter_ns() - start) / 1e6
if process.returncode != expected:
raise RuntimeError(f'{decoder} startup probe returned {process.returncode}')
startup.append(elapsed)
row['decoder_startup'] = dict(stats(startup), executable=decoder, arguments=argv,
expected_exit=expected,
method='No-work version/usage invocation; startup estimate, not patch execution.')
row['completed'] = True
save()
shutil.rmtree(work)
for name, path in binaries.items():
if filehash(path) != report['binaries'][name]['sha256']:
raise RuntimeError(f'executable changed: {name}')
if filehash(manifest_path) != report['manifest_sha256']:
raise RuntimeError('manifest changed during run')
report['completed'] = True
save()
print(f'Results: {args.output}', flush=True)
if __name__ == '__main__':
main()