Mercurial > public > mercurial-scm > hg

comparison contrib/perf-utils/subsetmaker.py @ 49015:3f6ddb1c193b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
subsetmaker: rework the antichain generation to be usable 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. Differential Revision: https://phab.mercurial-scm.org/D12396
author Pierre-Yves David <pierre-yves.david@octobus.net>
date Mon, 21 Mar 2022 20:06:51 +0100
parents 5a24bb7f4ed7
children abc327f9628b
comparison
equal deleted inserted replaced
49014:5a24bb7f4ed7 49015:3f6ddb1c193b
157 seed = revsetlang.getinteger(seed, _(b"seed should be a number")) 157 seed = revsetlang.getinteger(seed, _(b"seed should be a number"))
158 rand = random.Random(seed) 158 rand = random.Random(seed)
159 else: 159 else:
160 assert False 160 assert False
161 161
162 selected = set() 162 cl = repo.changelog
163 163
164 baseset = revset.getset(repo, smartset.fullreposet(repo), x) 164 # We already have cheap access to the parent mapping.
165 undecided = baseset 165 # However, we need to build a mapping of the children mapping
166 parents = repo.changelog._uncheckedparentrevs
167 children_map = collections.defaultdict(list)
168 for r in cl:
169 p1, p2 = parents(r)
170 if p1 >= 0:
171 children_map[p1].append(r)
172 if p2 >= 0:
173 children_map[p2].append(r)
174 children = children_map.__getitem__
175
176 selected = set()
177 undecided = SortedSet(cl)
166 178
167 while undecided: 179 while undecided:
168 pick = rand.choice(list(undecided)) 180 # while there is "undecided content", we pick a random changeset X
181 # and we remove anything in `::X + X::` from undecided content
182 pick = rand.choice(undecided)
169 selected.add(pick) 183 selected.add(pick)
170 undecided = repo.revs( 184 undecided.remove(pick)
171 '%ld and not (::%ld or %ld::head())', baseset, selected, selected 185
172 ) 186 ancestors = set(p for p in parents(pick) if p in undecided)
187 descendants = set(c for c in children(pick) if c in undecided)
188
189 while ancestors:
190 current = ancestors.pop()
191 undecided.remove(current)
192 for p in parents(current):
193 if p in undecided:
194 ancestors.add(p)
195 while descendants:
196 current = descendants.pop()
197 undecided.remove(current)
198 for p in children(current):
199 if p in undecided:
200 ancestors.add(p)
173 201
174 return smartset.baseset(selected) & subset 202 return smartset.baseset(selected) & subset