view tests/hghave @ 17970:0b03454abae7

ancestor: faster algorithm for difference of ancestor sets

One of the major reasons rebase is slow in large repositories is
the computation of the detach set: the set of ancestors of the
changesets to rebase not in the destination parent. This is currently
done via a revset that does two walks all the way to the root of
the DAG. Instead of doing that, to find ancestors of a set <revs>
not in another set <common> we walk up the tree in reverse revision
number order, maintaining sets of nodes visited from <revs>, <common>
or both.

For the common case where the sets are close both topologically and
in revision number (relative to repository size), this has been
found to speed up rebase by around 15-20%. When the nodes are farther
apart and the DAG is highly branching, it is harder to say which
would win.

Here's how long computing the detach set takes in a linear repository
with over 400000 changesets, rebasing near tip:

Rebasing across 4 changesets
Revset method: 2.2s
New algorithm: 0.00015s

Rebasing across 250 changesets
Revset method: 2.2s
New algorithm: 0.00069s

Rebasing across 10000 changesets
Revset method: 2.4s
New algorithm: 0.019s

#!/usr/bin/env python
"""Test the running system for features availability. Exit with zero
if all features are there, non-zero otherwise. If a feature name is
prefixed with "no-", the absence of feature is tested.
"""
import optparse
import sys
import hghave

checks = hghave.checks

def list_features():
    for name, feature in checks.iteritems():
        desc = feature[1]
        print name + ':', desc

def test_features():
    failed = 0
    for name, feature in checks.iteritems():
        check, _ = feature
        try:
            check()
        except Exception, e:
            print "feature %s failed:  %s" % (name, e)
            failed += 1
    return failed

parser = optparse.OptionParser("%prog [options] [features]")
parser.add_option("--test-features", action="store_true",
                  help="test available features")
parser.add_option("--list-features", action="store_true",
                  help="list available features")
parser.add_option("-q", "--quiet", action="store_true",
                  help="check features silently")

if __name__ == '__main__':
    options, args = parser.parse_args()
    if options.list_features:
        list_features()
        sys.exit(0)

    if options.test_features:
        sys.exit(test_features())

    quiet = options.quiet

    failures = 0

    def error(msg):
        global failures
        if not quiet:
            sys.stderr.write(msg + '\n')
        failures += 1

    for feature in args:
        negate = feature.startswith('no-')
        if negate:
            feature = feature[3:]

        if feature not in checks:
            error('skipped: unknown feature: ' + feature)
            continue

        check, desc = checks[feature]
        try:
            available = check()
        except Exception, e:
            error('hghave check failed: ' + feature)
            continue

        if not negate and not available:
            error('skipped: missing feature: ' + desc)
        elif negate and available:
            error('skipped: system supports %s' % desc)

    if failures != 0:
        sys.exit(1)