This is an archive of the discontinued Mercurial Phabricator instance.

Differential D12396

subsetmaker: rework the antichain generation to be usable
ClosedPublic

Authored by marmoute on Tue, Mar 22, 3:06 AM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG3f6ddb1c193b: subsetmaker: rework the antichain generation to be usable
rHG073fe75c7fc6: subsetmaker: rework the antichain generation to be usable
Summary

Before this, antichain computation can run for 10s of hours without completion in
sight. We use a more direct approach in the computation to keep the computation
in complexity in check. With good result.

We can now have a full antichain computation on mozilla-try in about one
minute. Which is usable.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Revision Contents
Changeset List

PathPackages
Mcontrib/perf-utils/subsetmaker.py (42 lines)

Diff 32790

contrib/perf-utils/subsetmaker.py

rand = random rand = random
elif len(args) == 2: elif len(args) == 2:
x, seed = args x, seed = args
seed = revsetlang.getinteger(seed, _(b"seed should be a number")) seed = revsetlang.getinteger(seed, _(b"seed should be a number"))
rand = random.Random(seed) rand = random.Random(seed)
else: else:
assert False assert False
selected = set() cl = repo.changelog
baseset = revset.getset(repo, smartset.fullreposet(repo), x) # We already have cheap access to the parent mapping.
undecided = baseset # However, we need to build a mapping of the children mapping
parents = repo.changelog._uncheckedparentrevs
children_map = collections.defaultdict(list)
for r in cl:
p1, p2 = parents(r)
if p1 >= 0:
children_map[p1].append(r)
if p2 >= 0:
children_map[p2].append(r)
children = children_map.__getitem__
selected = set()
undecided = SortedSet(cl)
while undecided: while undecided:
pick = rand.choice(list(undecided)) # while there is "undecided content", we pick a random changeset X
# and we remove anything in `::X + X::` from undecided content
pick = rand.choice(undecided)
selected.add(pick) selected.add(pick)
undecided = repo.revs( undecided.remove(pick)
'%ld and not (::%ld or %ld::head())', baseset, selected, selected
) ancestors = set(p for p in parents(pick) if p in undecided)
descendants = set(c for c in children(pick) if c in undecided)
while ancestors:
current = ancestors.pop()
undecided.remove(current)
for p in parents(current):
if p in undecided:
ancestors.add(p)
while descendants:
current = descendants.pop()
undecided.remove(current)
for p in children(current):
if p in undecided:
ancestors.add(p)
return smartset.baseset(selected) & subset return smartset.baseset(selected) & subset