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.

mercurial/ancestor.py

@@ -19,11 +19,13 b' def ancestor(a, b, pfunc):'
         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()
@@ -46,7 +48,7 b' def ancestor(a, b, pfunc):'
             if n not in seen:
                 seen[n] = 1
                 yield (d, n)
-                for p in pfunc(n):
+                for p in parentcache[n]:
                     heapq.heappush(h, (depth[p], p))
 
     def generations(vertex):