compare_stores.py

#!/usr/bin/env python3
"""Compare actual version-store CLI writes, retrievals and storage on shared histories."""
import argparse
import hashlib
import itertools
import json
import os
import platform
import random
import shutil
import statistics
import subprocess
import tempfile
import time
from pathlib import Path

ROOT = Path(__file__).resolve().parent
SEED = 20261028
NAMES = ('git', 'fossil', 'nab', 'dnab', 'rcs')


def digest(data):
    return hashlib.sha256(data).hexdigest()


def tree_bytes(path):
    return sum(p.stat().st_size for p in path.rglob('*') if p.is_file())


def summarize(samples):
    ordered = sorted(samples)
    return {'median_ms': statistics.median(samples), 'min_ms': min(samples),
            'max_ms': max(samples), 'p95_ms': ordered[min(len(ordered) - 1, int(len(ordered) * .95))],
            'samples_ms': samples}


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument('--versions', type=int, default=1000)
    parser.add_argument('--sizes', type=int, nargs='+', default=[4096, 131072])
    parser.add_argument('--workloads', nargs='+', choices=('binary', 'text'), default=['binary', 'text'])
    parser.add_argument('--runs', type=int, default=1)
    parser.add_argument('--reads', type=int, default=3)
    parser.add_argument('--tools', nargs='+', choices=NAMES, default=list(NAMES))
    args = parser.parse_args()
    if args.versions < 1 or args.runs < 1 or args.reads < 1 or any(s < 32 for s in args.sizes):
        parser.error('versions, runs and reads must be positive; sizes must be at least 32')
    if any(len(set(items)) != len(items) for items in (args.tools, args.sizes, args.workloads)):
        parser.error('tools, sizes and workloads must not be duplicated')
    needed = {'git': ['git'], 'fossil': ['fossil'], 'nab': ['nab'], 'dnab': ['dnab'], 'rcs': ['rcs', 'ci', 'co']}
    binaries = {}
    for name in args.tools:
        for binary in needed[name]:
            path = shutil.which(binary)
            if not path:
                parser.error(f'{binary} not found; select installed tools with --tools')
            binaries[binary] = str(Path(path).resolve())
    directory = Path(tempfile.mkdtemp(prefix='compare-stores-', dir=ROOT))
    home = directory / 'home'
    home.mkdir()
    env = os.environ.copy()
    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')
    for key in list(env):
        if key.startswith('GIT_') and key not in ('GIT_CONFIG_NOSYSTEM', 'GIT_CONFIG_GLOBAL', 'GIT_TERMINAL_PROMPT'):
            del env[key]

    def call(command, cwd, timed=False):
        start = time.perf_counter_ns()
        result = subprocess.run(command, cwd=cwd, env=env, stdout=subprocess.PIPE,
                                stderr=subprocess.PIPE, stdin=subprocess.DEVNULL, timeout=300)
        elapsed = (time.perf_counter_ns() - start) / 1e6
        if result.returncode:
            raise RuntimeError(f'{command!r} failed ({result.returncode}): {result.stderr.decode(errors="replace")}\n{result.stdout.decode(errors="replace")}')
        return (elapsed if timed else None), result.stdout

    def cmd(binary, *items):
        return [binaries[binary], *map(str, items)]

    report = {'seed': SEED, 'platform': platform.platform(), 'arguments': vars(args),
              'script_sha256': digest(Path(__file__).read_bytes()),
              'binaries': {n: {'path': p, 'sha256': digest(Path(p).read_bytes())} for n, p in binaries.items()},
              'directory': str(directory), 'completed': False, 'cases': [],
              'protocol': ('Fresh isolated repositories per trial; deterministic identical cumulative binary and ASCII text histories. '
                  'Each edit replaces three 16-byte regions and appends one byte. Text retains line breaks in replacement regions. Tools rotate each revision and read repeat. '
                  'Write timing includes CLI startup and normal storage operations, including git add+commit and initial fossil add+commit; '
                  'fixture generation and working-file writes are excluded. RCS uses binary keyword mode and retains a lock. '
                  'Fossil commits carry unique tags for retrieval; tags add metadata. Git automatic maintenance is disabled. '
                  'Read timing captures reconstructed stdout; SHA-256 checking is outside the timed interval. '
                  'All revisions are additionally reconstructed and verified outside timed probes. '
                  'Sizes are logical bytes in repository files only, excluding working copies and checkout databases. '
                  'Packed git is a copied repository repacked separately; its copy and repack do not affect normal writes. '
                  'Initialization, verification and packing are outside write timings. Warm caches and background load are uncontrolled.'),
              'limitations': ('CLI/process, metadata, compression, locking and durability policies differ; this is an end-to-end '
                  'single-file comparison, not a measurement of a delta algorithm alone. Git and Fossil track commits as well as contents; '
                  'nab/dnab and RCS are file archives. Git packing time is reported separately; packed size is not the normal-write size.')}
    result_path = directory / 'results.json'

    def save():
        result_path.write_text(json.dumps(report, indent=2) + '\n')

    save()
    checkpoints = sorted({n for n in (100, 1000, args.versions) if n <= args.versions})
    for size, workload in itertools.product(args.sizes, args.workloads):
        for trial in range(args.runs):
            case_dir = directory / f'{workload}-{size}-{trial}'
            case_dir.mkdir()
            dirs = {}
            tools = {}
            for name in args.tools:
                folder = case_dir / name
                folder.mkdir()
                dirs[name] = folder
                tools[name] = {'write_ms': [], 'checkpoints': []}
                if name == 'git':
                    call(cmd('git', 'init', '-q', '.'), folder)
                    for key, value in [('user.name', 'Benchmark'), ('user.email', 'benchmark@example.invalid'),
                                       ('gc.auto', '0'), ('commit.gpgsign', 'false'), ('core.hooksPath', os.devnull)]:
                        call(cmd('git', 'config', key, value), folder)
                elif name == 'fossil':
                    call(cmd('fossil', 'init', 'repo.fossil', '--admin-user', 'benchmark'), folder)
                    checkout = folder / 'checkout'
                    checkout.mkdir()
                    call(cmd('fossil', 'open', folder / 'repo.fossil', '--nosync'), checkout)
                    dirs[name] = checkout
                elif name == 'rcs':
                    call(cmd('rcs', '-q', '-i', '-kb', '-t-benchmark', 'content,v'), folder)
            case = {'workload': workload, 'initial_bytes': size, 'trial': trial, 'fixture_sha256': [], 'tools': tools}
            report['cases'].append(case)
            rng = random.Random(SEED + size)
            if workload == 'binary':
                data = bytearray(rng.randbytes(size))
            else:
                raw = rng.randbytes(size).hex()
                data = bytearray('\n'.join(raw[i:i + 64] for i in range(0, len(raw), 64))[:size], 'ascii')
            hashes = case['fixture_sha256']

            def get(name, version, git_ids):
                folder = dirs[name]
                if name == 'git':
                    command = cmd('git', 'show', f'{git_ids[version]}:content')
                elif name == 'fossil':
                    command = cmd('fossil', 'cat', 'content', '-r', f'bench-{version}')
                elif name in ('nab', 'dnab'):
                    command = cmd(name, 'rebuild', folder / f'archive.{name}', version)
                else:
                    command = cmd('co', '-q', '-p1.' + str(version + 1), '-kb', 'content,v')
                return call(command, folder, timed=True)

            for version in range(args.versions):
                if version:
                    for _ in range(3):
                        at = rng.randrange(len(data) - 16)
                        if workload == 'text':
                            while b'\n' in data[at:at + 16]:
                                at = rng.randrange(len(data) - 16)
                            data[at:at + 16] = rng.randbytes(8).hex().encode('ascii')
                        else:
                            data[at:at + 16] = rng.randbytes(16)
                    data += (rng.randbytes(1).hex()[:1].encode('ascii') if workload == 'text'
                             else rng.randbytes(1))
                hashes.append(digest(data))
                if version and hashes[-1] in hashes[:-1]:
                    raise RuntimeError('fixture contains a duplicate version')
                order = args.tools[:]
                shift = (version + trial) % len(order)
                order = order[shift:] + order[:shift]
                for name in order:
                    folder = dirs[name]
                    (folder / 'content').write_bytes(data)
                    elapsed = 0
                    if name == 'git':
                        ms, _ = call(cmd('git', 'add', '--', 'content'), folder, True)
                        elapsed += ms
                        ms, _ = call(cmd('git', 'commit', '-q', '-m', f'version {version}', '--no-verify'), folder, True)
                    elif name == 'fossil':
                        if version == 0:
                            ms, _ = call(cmd('fossil', 'add', 'content'), folder, True)
                            elapsed += ms
                        ms, _ = call(cmd('fossil', 'commit', '-m', f'version {version}', '--tag', f'bench-{version}',
                                         '--no-warnings', '--no-verify', '--nosign', '--nosync', '--user-override', 'benchmark', '--hash'), folder, True)
                    elif name in ('nab', 'dnab'):
                        ms, _ = call(cmd(name, 'patch', folder / 'content', folder / f'archive.{name}'), folder, True)
                    else:
                        ms, _ = call(cmd('ci', '-q', '-l', '-mbenchmark', 'content'), folder, True)
                    tools[name]['write_ms'].append(elapsed + ms)
                count = version + 1
                if count not in checkpoints:
                    continue
                git_ids = []
                if 'git' in args.tools:
                    _, output = call(cmd('git', 'rev-list', '--reverse', 'HEAD'), dirs['git'])
                    git_ids = output.decode().splitlines()
                    if len(git_ids) != count:
                        raise RuntimeError('git revision count mismatch')
                probes = {name: {label: [] for label in ('first', 'middle', 'latest')} for name in args.tools}
                for repeat in range(args.reads):
                    shift = (repeat + trial + count) % len(args.tools)
                    order = args.tools[shift:] + args.tools[:shift]
                    for name in order:
                        for label, index in [('first', 0), ('middle', (count - 1) // 2), ('latest', count - 1)]:
                            ms, output = get(name, index, git_ids)
                            if digest(output) != hashes[index]:
                                raise RuntimeError(f'{name}: incorrect reconstruction of revision {index}')
                            probes[name][label].append(ms)
                for name in args.tools:
                    folder = dirs[name]
                    if name == 'git':
                        repo_size = tree_bytes(folder / '.git')
                    elif name == 'fossil':
                        repo_size = (folder.parent / 'repo.fossil').stat().st_size
                    elif name == 'rcs':
                        repo_size = (folder / 'content,v').stat().st_size
                    else:
                        repo_size = (folder / f'archive.{name}').stat().st_size
                    entry = {'versions': count, 'repository_logical_bytes': repo_size,
                             'write_last_100': summarize(tools[name]['write_ms'][-100:]),
                             'cumulative_write_ms': sum(tools[name]['write_ms']),
                             'reads': {label: summarize(samples) for label, samples in probes[name].items()}}
                    if name == 'git':
                        packed = case_dir / 'packed.git'
                        shutil.copytree(folder / '.git', packed)
                        ms, _ = call(cmd('git', '--git-dir', packed, 'repack', '-ad'), case_dir, True)
                        ms2, _ = call(cmd('git', '--git-dir', packed, 'prune-packed'), case_dir, True)
                        entry['packed_repository_logical_bytes'] = tree_bytes(packed)
                        entry['pack_ms'] = ms + ms2
                        shutil.rmtree(packed)
                    tools[name]['checkpoints'].append(entry)
                save()
                print(f'{workload}, {size} bytes, trial {trial + 1}, {count} versions complete', flush=True)
            for name in args.tools:
                for version in range(args.versions):
                    _, output = get(name, version, git_ids)
                    if digest(output) != hashes[version]:
                        raise RuntimeError(f'{name}: incorrect reconstruction of revision {version}')
                tools[name]['verified_revisions'] = args.versions
            save()
    report['completed'] = True
    save()
    print(f'Results: {result_path}', flush=True)


if __name__ == '__main__':
    main()