Mercurial > hg-stable

changeset 7882:8d78fc991b71

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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.
author Nicolas Dumazet <nicdumz.commits@gmail.com>
date Mon, 23 Mar 2009 15:36:30 +0100
parents 3ac7114c2555
children c63c30ae9e39
files mercurial/ancestor.py
diffstat 1 files changed, 3 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- 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):