← 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 21:02:22 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-20090610210222-trfxgzd242tl04nl
A few tweaks to the pyrex version.

It is now 'as fast' as the python one for heads() checks on bzr ancestry.
It is about 2s faster for heads() checks for annotating NEWS.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
25
25
    ctypedef struct PyObject:
26
26
        pass
27
27
 
 
28
    object PyFrozenSet_New(object)
 
29
    PyObject * PyDict_GetItem(object d, object k)
 
30
    int PyDict_SetItem(object d, object k, object v) except -1
 
31
    void Py_INCREF(object)
 
32
 
28
33
import heapq
29
34
 
30
35
from bzrlib import revision
41
46
    cdef list children
42
47
    cdef _KnownGraphNode linear_dominator_node
43
48
    cdef public long dominator_distance
44
 
    cdef public long gdfo
 
49
    cdef public object gdfo # Int
45
50
    # This could also be simplified
46
51
    cdef object ancestor_of
47
52
 
141
146
        cdef _KnownGraphNode node
142
147
        cdef _KnownGraphNode parent_node
143
148
        cdef list parent_nodes
 
149
        cdef dict nodes
 
150
 
 
151
        nodes = self._nodes
144
152
 
145
153
        for key, parent_keys in parent_map.iteritems():
146
154
            parent_nodes = []
147
155
            for parent_key in parent_keys:
148
156
                try:
149
 
                    parent_node = self._nodes[parent_key]
 
157
                    parent_node = nodes[parent_key]
150
158
                except KeyError:
151
159
                    parent_node = _KnownGraphNode(parent_key, None)
152
 
                    self._nodes[parent_key] = parent_node
 
160
                    nodes[parent_key] = parent_node
153
161
                parent_nodes.append(parent_node)
154
 
            if key in self._nodes:
155
 
                node = self._nodes[key]
 
162
            if key in nodes:
 
163
                node = nodes[key]
156
164
                assert node.parents is None
157
165
                node.parents = parent_nodes
158
166
            else:
159
167
                node = _KnownGraphNode(key, parent_nodes)
160
 
                self._nodes[key] = node
 
168
                nodes[key] = node
161
169
            for parent_node in parent_nodes:
162
170
                parent_node.children.append(node)
163
171
 
288
296
        """
289
297
        cdef dict candidate_nodes
290
298
        cdef dict dom_to_node
 
299
        cdef dict nodes
 
300
        cdef _KnownGraphNode node
 
301
        cdef PyObject *maybe_node
291
302
 
292
303
        candidate_nodes = {}
 
304
        nodes = self._nodes
293
305
        for key in keys:
294
 
            candidate_nodes[key] = self._nodes[key]
 
306
            # node = nodes[key]
 
307
            # candidate_nodes[key] = node
 
308
            maybe_node = PyDict_GetItem(nodes, key)
 
309
            if maybe_node == NULL:
 
310
                raise KeyError('key %s not in nodes' % (key,))
 
311
            PyDict_SetItem(candidate_nodes, key, <object>maybe_node)
295
312
        if revision.NULL_REVISION in candidate_nodes:
296
313
            # NULL_REVISION is only a head if it is the only entry
297
314
            candidate_nodes.pop(revision.NULL_REVISION)
298
315
            if not candidate_nodes:
299
316
                return set([revision.NULL_REVISION])
 
317
        heads_key = PyFrozenSet_New(candidate_nodes)
300
318
        if len(candidate_nodes) < 2:
301
 
            return frozenset(candidate_nodes)
302
 
        heads_key = frozenset(candidate_nodes)
 
319
            return heads_key
303
320
        try:
304
321
            heads = self._known_heads[heads_key]
305
322
            return heads
306
323
        except KeyError:
307
324
            pass # compute it ourselves
308
 
        ## dominator = None
309
 
        ## # TODO: We could optimize for the len(candidate_nodes) > 2 by checking
310
 
        ## #       for *any* pair-wise matching, and then eliminating one of the
311
 
        ## #       nodes trivially. However, the fairly common case is just 2
312
 
        ## #       keys, so we'll focus on that, first
313
 
        ## for node in candidate_nodes.itervalues():
314
 
        ##     if dominator is None:
315
 
        ##         dominator = node.linear_dominator
316
 
        ##     elif dominator != node.linear_dominator:
317
 
        ##         break
318
 
        ## else:
319
 
        ##     # In 'time bzr annotate NEWS' this only catches *one* item, so it
320
 
        ##     # probably isn't worth the optimization
321
 
        ##     # All of these nodes have the same linear_dominator, which means
322
 
        ##     # they are in a line, the head is just the one with the highest
323
 
        ##     # distance
324
 
        ##     def get_distance(key):
325
 
        ##         return self._nodes[key].dominator_distance
326
 
        ##     def get_linear_head():
327
 
        ##         return max(candidate_nodes, key=get_distance)
328
 
        ##     return set([get_linear_head()])
329
325
        # Check the linear dominators of these keys, to see if we already
330
326
        # know the heads answer
331
 
        # dom_key = []
332
 
        # for node in candidate_nodes.itervalues():
333
 
        #     dom_key.append(node.linear_dominator.key)
334
 
        # dom_key = frozenset(dom_key)
335
 
        # if dom_key in self._known_heads:
336
 
        #     dom_to_node = dict([(node.linear_dominator, key)
337
 
        #                    for key, node in candidate_nodes.iteritems()])
338
 
        #     # map back into the original keys
339
 
        #     heads = self._known_heads[dom_key]
340
 
        #     heads = frozenset([dom_to_node[key] for key in heads])
341
 
        #     return heads
 
327
        dom_lookup_key, heads = self._heads_from_dominators(
 
328
                                    candidate_nodes.values())
 
329
        if heads is not None:
 
330
            return heads
342
331
        heads = self._heads_from_candidate_nodes(candidate_nodes)
343
 
        # if self.do_cache:
344
 
        #     self._known_heads[heads_key] = heads
345
 
        #     # Cache the dominator heads
346
 
        #     if dom_key is not None:
347
 
        #         dom_heads = frozenset([candidate_nodes[key].linear_dominator
348
 
        #                                for key in heads])
349
 
        #         self._known_heads[dom_key] = dom_heads
 
332
        if self.do_cache:
 
333
            self._cache_heads(heads, heads_key, dom_lookup_key, candidate_nodes)
350
334
        return heads
351
335
 
352
 
    def _heads_from_candidate_nodes(self, dict candidate_nodes):
 
336
    cdef object _cache_heads(self, heads, heads_key, dom_lookup_key,
 
337
                             candidate_nodes):
 
338
        cdef list dom_heads
 
339
        cdef PyObject *maybe_node
 
340
        cdef _KnownGraphNode node
 
341
 
 
342
        PyDict_SetItem(self._known_heads, heads_key, heads)
 
343
        dom_heads = []
 
344
        for key in heads:
 
345
            maybe_node = PyDict_GetItem(candidate_nodes, key)
 
346
            if maybe_node == NULL:
 
347
                raise KeyError
 
348
            node = <object>maybe_node
 
349
            dom_heads.append(node.linear_dominator_node.key)
 
350
        PyDict_SetItem(self._known_heads, dom_lookup_key,
 
351
                       PyFrozenSet_New(dom_heads))
 
352
 
 
353
    cdef object _heads_from_dominators(self, list candidates):
 
354
        cdef PyObject *test_heads
 
355
        cdef PyObject *test_key
 
356
        cdef list heads, dom_list_key
 
357
        cdef _KnownGraphNode node
 
358
 
 
359
        dom_list_key = []
 
360
        for node in candidates:
 
361
            dom_list_key.append(node.linear_dominator_node.key)
 
362
        dom_lookup_key = PyFrozenSet_New(dom_list_key)
 
363
        test_heads = PyDict_GetItem(self._known_heads, dom_lookup_key)
 
364
        if test_heads == NULL:
 
365
            return dom_lookup_key, None
 
366
        # We need to map back to the original keys
 
367
        dom_heads = <object>test_heads
 
368
        dom_to_key = {}
 
369
        for node in candidates:
 
370
            PyDict_SetItem(dom_to_key, node.linear_dominator_node.key,
 
371
                                       node.key)
 
372
        heads = []
 
373
        for dom_key in dom_heads:
 
374
            test_key = PyDict_GetItem(dom_to_key, dom_key)
 
375
            if test_key == NULL:
 
376
                # Should never happen
 
377
                raise KeyError
 
378
            heads.append(<object>test_key)
 
379
        return dom_lookup_key, PyFrozenSet_New(heads)
 
380
 
 
381
    cdef object _heads_from_candidate_nodes(self, dict candidate_nodes):
353
382
        cdef list to_cleanup
354
383
        cdef _KnownGraphNode node
355
384
        cdef _KnownGraphNode parent_node
367
396
        # walking
368
397
        # Now we walk nodes until all nodes that are being walked are 'common'
369
398
        num_candidates = len(candidate_nodes)
370
 
        nodes = self._nodes
371
399
        heappop = heapq.heappop
372
400
        heappush = heapq.heappush
373
 
        while queue and len(candidate_nodes) > 1:
 
401
        while len(queue) > 0 and len(candidate_nodes) > 1:
374
402
            _, node = heappop(queue)
375
403
            if len(node.ancestor_of) == num_candidates:
376
404
                # This node is now considered 'common'
416
444
                    parent_node.ancestor_of = tuple(sorted(all_ancestors))
417
445
        for node in to_cleanup:
418
446
            node.ancestor_of = None
419
 
        return frozenset(candidate_nodes)
 
447
        return PyFrozenSet_New(candidate_nodes)