# HG changeset patch
# User Nicolas Dumazet <nicdumz.commits@gmail.com>
# Date 2009-03-23 14:36:30
# Node ID 8d78fc991b71e627327debc413b4a12c5a7f7f16
# Parent  3ac7114c255507f39d3bb9f162fe848a75d187bc

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.

diff --git a/mercurial/ancestor.py b/mercurial/ancestor.py
--- a/mercurial/ancestor.py
+++ b/mercurial/ancestor.py
@@ -19,11 +19,13 @@ 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 @@ 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):