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.
--- a/mercurial/ancestor.py Mon Mar 23 13:49:16 2009 +0100
+++ b/mercurial/ancestor.py Mon Mar 23 15:36:30 2009 +0100
@@ -19,11 +19,13 @@
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 @@
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):