view mercurial/similar.py @ 30796:168ef0a4eb3b

perf: support multiple compression engines in perfrevlogchunks

Now that the revlog has a reference to a compressor, it is
possible to swap in other compression engines. So, teach
`hg perfrevlogchunks` to do that.

The default behavior of `hg perfrevlogchunks` is now to measure the
compression performance of all compression engines implementing the
revlog compressor API. This effectively adds the no-op "none"
compressor and zstd (when available) into the default set.

While we can't yet plug alternate compressors into revlogs, this
command gives us a preview of the performance. On the mozilla-unified
repository:

$ hg perfrevlogchunks -c
! compress w/ none
! wall 0.115159 comb 0.110000 user 0.110000 sys 0.000000 (best of 86)
! compress w/ zlib
! wall 5.681406 comb 5.680000 user 5.680000 sys 0.000000 (best of 3)
! compress w/ zstd
! wall 2.624781 comb 2.620000 user 2.620000 sys 0.000000 (best of 4)

$ hg perfrevlogchunks -m
! compress w/ none
! wall 0.124486 comb 0.120000 user 0.120000 sys 0.000000 (best of 79)
! compress w/ zlib
! wall 10.144701 comb 10.150000 user 10.150000 sys 0.000000 (best of 3)
! compress w/ zstd
! wall 4.383118 comb 4.390000 user 4.390000 sys 0.000000 (best of 3)

Those numbers for zstd look promising. But they aren't the full story.
For that, we'll need to look at decompression times and storage sizes.
Stay tuned...

# similar.py - mechanisms for finding similar files
#
# Copyright 2005-2007 Matt Mackall <[e-mail]>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.

from __future__ import absolute_import

import hashlib

from .i18n import _
from . import (
    bdiff,
    mdiff,
    util,
)

def _findexactmatches(repo, added, removed):
    '''find renamed files that have no changes

    Takes a list of new filectxs and a list of removed filectxs, and yields
    (before, after) tuples of exact matches.
    '''
    numfiles = len(added) + len(removed)

    # Get hashes of removed files.
    hashes = {}
    for i, fctx in enumerate(removed):
        repo.ui.progress(_('searching for exact renames'), i, total=numfiles,
                         unit=_('files'))
        h = hashlib.sha1(fctx.data()).digest()
        hashes[h] = fctx

    # For each added file, see if it corresponds to a removed file.
    for i, fctx in enumerate(added):
        repo.ui.progress(_('searching for exact renames'), i + len(removed),
                total=numfiles, unit=_('files'))
        h = hashlib.sha1(fctx.data()).digest()
        if h in hashes:
            yield (hashes[h], fctx)

    # Done
    repo.ui.progress(_('searching for exact renames'), None)

def _findsimilarmatches(repo, added, removed, threshold):
    '''find potentially renamed files based on similar file content

    Takes a list of new filectxs and a list of removed filectxs, and yields
    (before, after, score) tuples of partial matches.
    '''
    copies = {}
    for i, r in enumerate(removed):
        repo.ui.progress(_('searching for similar files'), i,
                         total=len(removed), unit=_('files'))

        # lazily load text
        @util.cachefunc
        def data():
            orig = r.data()
            return orig, mdiff.splitnewlines(orig)

        def score(text):
            orig, lines = data()
            # bdiff.blocks() returns blocks of matching lines
            # count the number of bytes in each
            equal = 0
            matches = bdiff.blocks(text, orig)
            for x1, x2, y1, y2 in matches:
                for line in lines[y1:y2]:
                    equal += len(line)

            lengths = len(text) + len(orig)
            return equal * 2.0 / lengths

        for a in added:
            bestscore = copies.get(a, (None, threshold))[1]
            myscore = score(a.data())
            if myscore >= bestscore:
                copies[a] = (r, myscore)
    repo.ui.progress(_('searching'), None)

    for dest, v in copies.iteritems():
        source, bscore = v
        yield source, dest, bscore

def findrenames(repo, added, removed, threshold):
    '''find renamed files -- yields (before, after, score) tuples'''
    parentctx = repo['.']
    workingctx = repo[None]

    # Zero length files will be frequently unrelated to each other, and
    # tracking the deletion/addition of such a file will probably cause more
    # harm than good. We strip them out here to avoid matching them later on.
    addedfiles = set([workingctx[fp] for fp in added
            if workingctx[fp].size() > 0])
    removedfiles = set([parentctx[fp] for fp in removed
            if fp in parentctx and parentctx[fp].size() > 0])

    # Find exact matches.
    for (a, b) in _findexactmatches(repo,
            sorted(addedfiles), sorted(removedfiles)):
        addedfiles.remove(b)
        yield (a.path(), b.path(), 1.0)

    # If the user requested similar files to be matched, search for them also.
    if threshold < 1.0:
        for (a, b, score) in _findsimilarmatches(repo,
                sorted(addedfiles), sorted(removedfiles), threshold):
            yield (a.path(), b.path(), score)