Mercurial > public > mercurial-scm > hg

comparison mercurial/branchmap.py @ 22357:9c3c3dc14a65

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
branchmap: pre-filter topological heads before ancestors based filtering We know that topological heads will not be ancestors of anything, so we filter them out to potentially reduce the range of the ancestors computation. On a strongly headed repo this gives humble speedup: from 0.1984 to 0.1629
author Pierre-Yves David <pierre-yves.david@fb.com>
date Sat, 30 Aug 2014 12:33:12 +0200
parents 3c8fb24334e9
children cb99bacb9b4e
comparison
equal deleted inserted replaced
22356:3c8fb24334e9 22357:9c3c3dc14a65
237 for r in revgen: 237 for r in revgen:
238 branch, closesbranch = getbranchinfo(r) 238 branch, closesbranch = getbranchinfo(r)
239 newbranches.setdefault(branch, []).append(r) 239 newbranches.setdefault(branch, []).append(r)
240 if closesbranch: 240 if closesbranch:
241 self._closednodes.add(cl.node(r)) 241 self._closednodes.add(cl.node(r))
242
243 # fetch current topological heads to speed up filtering
244 topoheads = set(cl.headrevs())
245
242 # if older branchheads are reachable from new ones, they aren't 246 # if older branchheads are reachable from new ones, they aren't
243 # really branchheads. Note checking parents is insufficient: 247 # really branchheads. Note checking parents is insufficient:
244 # 1 (branch a) -> 2 (branch b) -> 3 (branch a) 248 # 1 (branch a) -> 2 (branch b) -> 3 (branch a)
245 for branch, newheadrevs in newbranches.iteritems(): 249 for branch, newheadrevs in newbranches.iteritems():
246 bheads = self.setdefault(branch, []) 250 bheads = self.setdefault(branch, [])
253 bheadset.update(newheadrevs) 257 bheadset.update(newheadrevs)
254 258
255 # This prunes out two kinds of heads - heads that are superseded by 259 # This prunes out two kinds of heads - heads that are superseded by
256 # a head in newheadrevs, and newheadrevs that are not heads because 260 # a head in newheadrevs, and newheadrevs that are not heads because
257 # an existing head is their descendant. 261 # an existing head is their descendant.
258 ancestors = set(cl.ancestors(newheadrevs, min(bheadset))) 262 uncertain = bheadset - topoheads
259 bheadset -= ancestors 263 if uncertain:
264 floorrev = min(uncertain)
265 ancestors = set(cl.ancestors(newheadrevs, floorrev))
266 bheadset -= ancestors
260 bheadrevs = sorted(bheadset) 267 bheadrevs = sorted(bheadset)
261 self[branch] = [cl.node(rev) for rev in bheadrevs] 268 self[branch] = [cl.node(rev) for rev in bheadrevs]
262 tiprev = bheadrevs[-1] 269 tiprev = bheadrevs[-1]
263 if tiprev > self.tiprev: 270 if tiprev > self.tiprev:
264 self.tipnode = cl.node(tiprev) 271 self.tipnode = cl.node(tiprev)