Rev 2: some typos and other work. in http://bzr.arbash-meinel.com/plugins/test_graph
John Arbash Meinel
john at arbash-meinel.com
Mon Dec 10 21:01:10 GMT 2007
At http://bzr.arbash-meinel.com/plugins/test_graph
------------------------------------------------------------
revno: 2
revision-id:john at arbash-meinel.com-20071210210105-afwkl4a38ikmbtzr
parent: john at arbash-meinel.com-20071210194759-ii8q80gow8690x99
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: test_graph
timestamp: Mon 2007-12-10 15:01:05 -0600
message:
some typos and other work.
modified:
graph_testing.py graph_testing.py-20071210194758-1pwa1q7e3wnjf418-2
-------------- next part --------------
=== modified file 'graph_testing.py'
--- a/graph_testing.py 2007-12-10 19:47:59 +0000
+++ b/graph_testing.py 2007-12-10 21:01:05 +0000
@@ -16,6 +16,8 @@
"""Basic functions for testing graph operations."""
+import time
+
from bzrlib import (
branch,
errors,
@@ -23,16 +25,19 @@
)
-
class GraphTester(object):
def __init__(self, rev_graph):
self.rev_graph = rev_graph
self.head_times = {}
+ self.trivial_head_times = {}
self.find_difference_times = {}
+ self.trivial_diff_times = {}
self.hold_graph = False
+ self.invalid_heads = set()
+ self.invalid_diffs = set()
- def get_interesting_nodes(self):
+ def get_interesting_nodes(self, last_revision):
"""Go through the revision graph, and look for interesting nodes.
Currently that is just defined as nodes which have more than one parent.
@@ -40,7 +45,8 @@
comes first.)
"""
interesting = []
- for seq_num, revision_id, depth, eom in tsort.merge_sort(self.rev_graph):
+ for seq_num, revision_id, depth, eom in tsort.merge_sort(self.rev_graph,
+ last_revision):
parent_ids = self.rev_graph[revision_id]
if len(parent_ids) > 1:
interesting.append(revision_id)
@@ -51,26 +57,28 @@
ancestries = {}
# We go in reverse order, so that we will tend to find the ancestries in
# the map
- for revision_id in reversed(self.interesting):
- ancestry = set([revision_id])
- needed = set([revision_id])
- while needed:
- next = needed.pop()
- parent_ids = self.rev_graph[next]
- ancestry.update(parent_ids)
- for parent_id in parent_ids:
- if parent_id in ancestries:
- ancestry.update(ancestries[parent_id])
- else: # We need to probe in this direction
- needed.add(parent_id)
- ancestries[revision_id] = ancestry
+ for interesting_id in reversed(self.interesting):
+ needed_ids = list(self.rev_graph[interesting_id]) + [interesting_id]
+ for revision_id in needed_ids:
+ ancestry = set([revision_id])
+ needed = set([revision_id])
+ while needed:
+ next = needed.pop()
+ parent_ids = self.rev_graph[next]
+ ancestry.update(parent_ids)
+ for parent_id in parent_ids:
+ if parent_id in ancestries:
+ ancestry.update(ancestries[parent_id])
+ else: # We need to probe in this direction
+ needed.add(parent_id)
+ ancestries[revision_id] = ancestry
self.ancestries = ancestries
def time_functions(self, a_branch):
if self.hold_graph:
graph = a_branch.repository.get_graph()
- for revision_id in reversed(interesting):
+ for revision_id in reversed(self.interesting):
parent_ids = self.rev_graph[revision_id]
a_branch.lock_read()
try:
@@ -82,17 +90,53 @@
finally:
a_branch.unlock()
self.head_times[revision_id] = t_heads
- if heads != set(parent_ids):
- print 'heads() mismatch for: %s' % (revision_id,)
+ parent_id_set = set(parent_ids)
+ if heads != parent_id_set:
+ if heads.issubset(parent_ids):
+ print 'heads() is subset for: %s' % (revision_id,)
+ else:
+ print 'heads() mismatch for: %s' % (revision_id,)
+ self.invalid_heads.add(revision_id)
+
+ a_branch.lock_read()
+ try:
+ if not self.hold_graph:
+ graph = a_branch.repository.get_graph()
+ t_start = time.clock()
+ for parent_id in parent_ids:
+ heads = graph.heads((revision_id, parent_id))
+ assert heads == set([revision_id])
+ t_trivial_heads = time.clock() - t_start
+ finally:
+ a_branch.unlock()
+ self.trivial_head_times[revision_id] = t_heads
+
+ a_branch.lock_read()
+ try:
+ if not self.hold_graph:
+ graph = a_branch.repository.get_graph()
+ t_start = time.clock()
+ for parent_id in parent_ids:
+ left, right = graph.find_difference(revision_id, parent_id)
+ if right != set():
+ print 'found unmerged nodes for:\n %s\nand %s' % (
+ revision_id, parent_id)
+ t_trivial_diff = time.clock() - t_start
+ finally:
+ a_branch.unlock()
+ self.trivial_diff_times[revision_id] = t_trivial_diff
+
if len(parent_ids) < 2:
continue
+
+ a_branch.lock_read()
try:
if not self.hold_graph:
graph = a_branch.repository.get_graph()
t_start = time.clock()
left, right = graph.find_difference(parent_ids[0],
parent_ids[1])
- t_diff = t_start - t_start
+ t_diff = time.clock() - t_start
finally:
a_branch.unlock()
self.find_difference_times[revision_id] = t_diff
@@ -106,6 +150,8 @@
print 'left incorrect for: %s' % (revision_id,)
elif not right_correct:
print 'right incorrect for: %s' % (revision_id,)
+ if not left_correct or not right_correct:
+ self.invalid_diffs.add(revision_id)
def get_statistics(self, times):
min_time = None
@@ -126,6 +172,7 @@
'min_time':min_time,
'min_rev':min_rev,
'max_time':max_time,
+ 'max_rev':max_rev,
'avg_time':avg_time,
'total_time':total_time,
}
@@ -134,19 +181,26 @@
def test_all(location):
the_branch = branch.Branch.open(location)
the_branch.lock_read()
+ the_branch.lock_read()
try:
- rev_graph = the_branch.repository.get_revision_graph(
- the_branch.last_revision())
+ last_revision = the_branch.last_revision()
+ rev_graph = the_branch.repository.get_revision_graph(last_revision)
rev_id_map = the_branch.get_revision_id_to_revno_map()
finally:
the_branch.unlock()
tester = GraphTester(rev_graph)
- tester.get_interesting_nodes()
+ tester.hold_graph = True
+ tester.get_interesting_nodes(last_revision)
tester.get_ancestry_for_interesting()
- tester.time_functions()
+ tester.time_functions(the_branch)
import pprint
+ print 'trivial heads:'
+ pprint.pprint(tester.get_statistics(tester.trivial_head_times))
+ print 'trivial diff:'
+ pprint.pprint(tester.get_statistics(tester.trivial_diff_times))
print 'heads:'
pprint.pprint(tester.get_statistics(tester.head_times))
print 'diffs:'
- pprint.pprint(tester.get_statistics(tester.find_difference_times)
+ pprint.pprint(tester.get_statistics(tester.find_difference_times))
import pdb; pdb.set_trace()
+ the_branch.unlock()
More information about the bazaar-commits
mailing list