Mercurial > hg-stable
view mercurial/ancestor.py @ 9534:8e202431d620
bdiff: gradually enable the popularity hack
Patch from Jason Orendorff
The lower the threshold, the stronger the popularity hack's
influence. So at 3999 lines, the hack is disabled; and at 4000 lines,
the hack is enabled at maximum strength (t=4).
No source file in mercurial/crew is over 4000 lines. But there are, oh,
a few such files in Mozilla. I can testify that this hack causes hg to
generate some correct but eyebrow-raising patches.
I think the hack should phase in gradually. The threshold should be high
for small files where we don't need it so much. Like this:
t = (bn < 31000) ? 1000000 / bn : bn / 1000;
That would leave the popularity hack disabled for small files, then
gradually phase it in:
bn < 1000 -- t > bn (popularity hack is completely disabled)
bn == 1000 -- t = 1000 (still effectively disabled)
bn == 2000 -- t = 500 (only hits unusual files)
bn == 10000 -- t = 100 (only hits especially common lines)
bn == 31000 -- t = 31 (hack is at maximum power)
bn == 32000 -- t = 32 (hack could backfire, ease off)
author | Benoit Boissinot <benoit.boissinot@ens-lyon.org> |
---|---|
date | Sat, 03 Oct 2009 23:36:08 +0200 |
parents | 23429ebd3f9d |
children | 806e6b6cb8d8 25e572394f5c |
line wrap: on
line source
# ancestor.py - generic DAG ancestor algorithm for mercurial # # Copyright 2006 Matt Mackall <mpm@selenic.com> # # This software may be used and distributed according to the terms of the # GNU General Public License version 2, incorporated herein by reference. import heapq def ancestor(a, b, pfunc): """ return the least common ancestor of nodes a and b or None if there is no such ancestor. pfunc must return a list of parent vertices """ if a == b: return a # find depth from root of all ancestors parentcache = {} visit = [a, b] depth = {} while visit: vertex = visit[-1] pl = pfunc(vertex) parentcache[vertex] = pl if not pl: depth[vertex] = 0 visit.pop() else: for p in pl: if p == a or p == b: # did we find a or b as a parent? return p # we're done if p not in depth: visit.append(p) if visit[-1] == vertex: depth[vertex] = min([depth[p] for p in pl]) - 1 visit.pop() # traverse ancestors in order of decreasing distance from root def ancestors(vertex): h = [(depth[vertex], vertex)] seen = set() while h: d, n = heapq.heappop(h) if n not in seen: seen.add(n) yield (d, n) for p in parentcache[n]: heapq.heappush(h, (depth[p], p)) def generations(vertex): sg, s = None, set() for g, v in ancestors(vertex): if g != sg: if sg: yield sg, s sg, s = g, set((v,)) else: s.add(v) yield sg, s x = generations(a) y = generations(b) gx = x.next() gy = y.next() # increment each ancestor list until it is closer to root than # the other, or they match try: while 1: if gx[0] == gy[0]: for v in gx[1]: if v in gy[1]: return v gy = y.next() gx = x.next() elif gx[0] > gy[0]: gy = y.next() else: gx = x.next() except StopIteration: return None