← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

  • Committer: John Arbash Meinel
  • Date: 2009-06-10 22:03:39 UTC
  • mto: (4371.4.5 vila-better-heads)
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090610220339-akbmevv1b0236upf
Attempt to make things better by splitting out left_parent and right_parent into
individual attributes (to avoid extra type checks, etc.)
However, this seems to make things *much* worse rather than better.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
30
30
    int PyDict_SetItem(object d, object k, object v) except -1
31
31
    void Py_INCREF(object)
32
32
 
 
33
 
33
34
import heapq
34
35
 
35
36
from bzrlib import revision
36
37
 
 
38
heappush = heapq.heappush
 
39
heappop = heapq.heappop
 
40
 
37
41
 
38
42
cdef class _KnownGraphNode:
39
43
    """Represents a single object in the known graph."""
40
44
 
41
45
    cdef object key
42
 
    # Ideally, we could change this into fixed arrays, rather than get the
43
 
    # extra allocations. Consider that 99% of all revisions will have <= 2
44
 
    # parents, we may want to put in the effort
 
46
    # 99% of all revisions have <= 2 parents, so we pre-allocate space for it,
 
47
    # but allow the flexibility of having N parents
 
48
    cdef _KnownGraphNode left_parent
 
49
    cdef _KnownGraphNode right_parent
45
50
    cdef list parents
46
51
    cdef list children
47
52
    cdef _KnownGraphNode linear_dominator_node
51
56
    cdef object ancestor_of
52
57
 
53
58
    def __init__(self, key, parents):
 
59
        cdef _KnownGraphNode _parent_node
 
60
        cdef int i
 
61
 
54
62
        self.key = key
55
 
        if parents is None:
56
 
            self.parents = parents
57
 
        else:
58
 
            if not isinstance(parents, list):
59
 
                raise TypeError('parents must be a list')
60
 
            for parent in parents:
61
 
                if not isinstance(parent, _KnownGraphNode):
62
 
                    raise TypeError('parents must be a list of _KnownGraphNode')
63
 
        self.parents = parents
 
63
        self.left_parent = None
 
64
        self.right_parent = None
 
65
        self.set_parents(parents)
 
66
 
64
67
        self.children = []
65
68
        # oldest ancestor, such that no parents between here and there have >1
66
69
        # child or >1 parent.
89
92
            else:
90
93
                return self.linear_dominator_node.key
91
94
 
 
95
    cdef set_parents(self, list parents):
 
96
        cdef int num_parents
 
97
        self.parents = parents
 
98
        if parents is None:
 
99
            return
 
100
        num_parents = len(self.parents)
 
101
        if num_parents > 2:
 
102
            # No special ops
 
103
            return
 
104
        if num_parents > 0:
 
105
            self.left_parent = self.parents[0]
 
106
        if num_parents > 1:
 
107
            self.right_parent = self.parents[1]
 
108
 
92
109
    cdef clear_references(self):
93
110
        self.parents = None
94
111
        self.children = None
95
112
        self.linear_dominator_node = None
 
113
        self.left_parent = None
 
114
        self.right_parent = None
96
115
 
97
116
    def __repr__(self):
98
117
        parent_keys = []
116
135
    cdef public object _nodes
117
136
    cdef dict _known_heads
118
137
    cdef public int do_cache
 
138
    # Nodes we've touched that we'll need to reset their info when heads() is
 
139
    # done
 
140
    cdef list _to_cleanup
119
141
 
120
142
    def __init__(self, parent_map, do_cache=True):
121
143
        """Create a new KnownGraph instance.
125
147
        self._nodes = {}
126
148
        # Maps {sorted(revision_id, revision_id): heads}
127
149
        self._known_heads = {}
 
150
        self._to_cleanup = []
128
151
        self.do_cache = int(do_cache)
129
152
        self._initialize_nodes(parent_map)
130
153
        self._find_linear_dominators()
162
185
            if key in nodes:
163
186
                node = nodes[key]
164
187
                assert node.parents is None
165
 
                node.parents = parent_nodes
 
188
                node.set_parents(parent_nodes)
166
189
            else:
167
190
                node = _KnownGraphNode(key, parent_nodes)
168
191
                nodes[key] = node
378
401
            heads.append(<object>test_key)
379
402
        return dom_lookup_key, PyFrozenSet_New(heads)
380
403
 
 
404
    cdef int _process_parent(self, _KnownGraphNode node,
 
405
                             _KnownGraphNode parent_node,
 
406
                             dict candidate_nodes,
 
407
                             queue) except -1:
 
408
        """Process the parent of a node, seeing if we need to walk it.
 
409
 
 
410
        :return: 0 No extra work needed
 
411
                 1 This was a candidate node, and now there is only 1 candidate
 
412
                   left, so break out of the loop
 
413
        """
 
414
        cdef PyObject *maybe_candidate
 
415
        maybe_candidate = PyDict_GetItem(candidate_nodes, parent_node.key)
 
416
        if maybe_candidate != NULL:
 
417
            candidate_nodes.pop(parent_node.key)
 
418
            if len(candidate_nodes) <= 1:
 
419
                return 1
 
420
        if parent_node.ancestor_of is None:
 
421
            # This node hasn't been walked yet, so just project node's ancestor
 
422
            # info directly to parent_node, and enqueue it for later processing
 
423
            parent_node.ancestor_of = node.ancestor_of
 
424
            heappush(queue, (-parent_node.gdfo, parent_node))
 
425
            self._to_cleanup.append(parent_node)
 
426
        elif parent_node.ancestor_of != node.ancestor_of:
 
427
            # Combine to get the full set of parents
 
428
            # Rewrite using PySet_* functions, unfortunately you have to use
 
429
            # PySet_Add since there is no PySet_Update... :(
 
430
            all_ancestors = set(parent_node.ancestor_of)
 
431
            all_ancestors.update(node.ancestor_of)
 
432
            parent_node.ancestor_of = tuple(sorted(all_ancestors))
 
433
        return 0
 
434
 
381
435
    cdef object _heads_from_candidate_nodes(self, dict candidate_nodes):
382
 
        cdef list to_cleanup
383
436
        cdef _KnownGraphNode node
384
437
        cdef _KnownGraphNode parent_node
385
438
        cdef int num_candidates
 
439
        cdef int num_parents
 
440
        cdef list queue
386
441
 
387
442
        queue = []
388
 
        to_cleanup = []
389
443
        for node in candidate_nodes.itervalues():
390
444
            assert node.ancestor_of is None
391
445
            node.ancestor_of = (node.key,)
392
446
            queue.append((-node.gdfo, node))
393
 
            to_cleanup.append(node)
 
447
            self._to_cleanup.append(node)
394
448
        heapq.heapify(queue)
395
449
        # These are nodes that we determined are 'common' that we are no longer
396
450
        # walking
423
477
                # We are at the tip of a long linear region
424
478
                # We know that there is nothing between here and the tail
425
479
                # that is interesting, so skip to the end
426
 
                parents = [node.linear_dominator_node]
 
480
                if (self._process_parent(node, node.linear_dominator_node,
 
481
                                         candidate_nodes, queue)):
 
482
                    break
427
483
            else:
428
 
                parents = node.parents
429
 
            for parent_node in node.parents:
430
 
                if parent_node.key in candidate_nodes:
431
 
                    candidate_nodes.pop(parent_node.key)
432
 
                    if len(candidate_nodes) <= 1:
433
 
                        break
434
 
                if parent_node.ancestor_of is None:
435
 
                    # This node hasn't been walked yet
436
 
                    parent_node.ancestor_of = node.ancestor_of
437
 
                    # Enqueue this node
438
 
                    heappush(queue, (-parent_node.gdfo, parent_node))
439
 
                    to_cleanup.append(parent_node)
440
 
                elif parent_node.ancestor_of != node.ancestor_of:
441
 
                    # Combine to get the full set of parents
442
 
                    all_ancestors = set(parent_node.ancestor_of)
443
 
                    all_ancestors.update(node.ancestor_of)
444
 
                    parent_node.ancestor_of = tuple(sorted(all_ancestors))
445
 
        for node in to_cleanup:
 
484
                num_parents = len(node.parents)
 
485
                if num_parents > 2:
 
486
                   for parent_node in node.parents:
 
487
                       if (self._process_parent(node, parent_node,
 
488
                                                candidate_nodes, queue)):
 
489
                           break
 
490
                else:
 
491
                    if num_parents > 0:
 
492
                        if (self._process_parent(node, node.left_parent,
 
493
                                                 candidate_nodes, queue)):
 
494
                            break
 
495
                    if num_parents > 1:
 
496
                        if (self._process_parent(node, node.right_parent,
 
497
                                                 candidate_nodes, queue)):
 
498
                            break
 
499
        for node in self._to_cleanup:
446
500
            node.ancestor_of = None
447
501
        return PyFrozenSet_New(candidate_nodes)