Mercurial > hg
diff 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.
author | Nicolas Dumazet <nicdumz.commits@gmail.com> |
---|---|
date | Mon, 23 Mar 2009 15:36:30 +0100 |
parents | 532ca442b903 |
children | 46293a0c7e9f |
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):