comparison mercurial/ancestor.py @ 7882:8d78fc991b71

ancestor: caching the parent list to improve performance

When computing the DAG depth, we walk through all ancestors: this commit adds
memoization during that first step. Then, the memorized parents are fetched
from a dict instead of calling parents() on each vertex.

This tweak, according to Kcachegrind, improves ancestor() performance by 16%
when cloning a big repository.

7881:3ac7114c2555

    if a == b:
        return a

    # find depth from root of all ancestors
    visit = [a, b]
    depth = {}
    while visit:
        vertex = visit[-1]
        pl = pfunc(vertex)
        if not pl:
            depth[vertex] = 0
            visit.pop()
        else:
            for p in pl:

        while h:
            d, n = heapq.heappop(h)
            if n not in seen:
                seen[n] = 1
                yield (d, n)
                for p in pfunc(n):
                    heapq.heappush(h, (depth[p], p))

    def generations(vertex):
        sg, s = None, {}
        for g, v in ancestors(vertex):

7882:8d78fc991b71

    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:

        while h:
            d, n = heapq.heappop(h)
            if n not in seen:
                seen[n] = 1
                yield (d, n)
                for p in parentcache[n]:
                    heapq.heappush(h, (depth[p], p))

    def generations(vertex):
        sg, s = None, {}
        for g, v in ancestors(vertex):