← 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: Canonical.com Patch Queue Manager
  • Date: 2009-08-19 18:04:49 UTC
  • mfrom: (4593.5.43 1.19-known-graph-sorted)
  • Revision ID: pqm@pqm.ubuntu.com-20090819180449-p5dibldf9pcp24n4
(jam) Add VersionedFiles.get_known_graph_ancestry and
        KnownGraph.merge_sort()

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
44
44
 
45
45
    void Py_INCREF(object)
46
46
 
 
47
import gc
47
48
 
48
 
from bzrlib import revision
 
49
from bzrlib import errors, revision
49
50
 
50
51
cdef object NULL_REVISION
51
52
NULL_REVISION = revision.NULL_REVISION
59
60
    cdef object children
60
61
    cdef public long gdfo
61
62
    cdef int seen
 
63
    cdef object extra
62
64
 
63
65
    def __init__(self, key):
64
 
        cdef int i
65
 
 
66
66
        self.key = key
67
67
        self.parents = None
68
68
 
70
70
        # Greatest distance from origin
71
71
        self.gdfo = -1
72
72
        self.seen = 0
 
73
        self.extra = None
73
74
 
74
75
    property child_keys:
75
76
        def __get__(self):
115
116
    return <_KnownGraphNode>temp_node
116
117
 
117
118
 
118
 
# TODO: slab allocate all _KnownGraphNode objects.
119
 
#       We already know how many we are going to need, except for a couple of
120
 
#       ghosts that could be allocated on demand.
 
119
cdef class _MergeSorter
121
120
 
122
121
cdef class KnownGraph:
123
122
    """This is a class which assumes we already know the full graph."""
136
135
        # Maps {sorted(revision_id, revision_id): heads}
137
136
        self._known_heads = {}
138
137
        self.do_cache = int(do_cache)
 
138
        # TODO: consider disabling gc since we are allocating a lot of nodes
 
139
        #       that won't be collectable anyway. real world testing has not
 
140
        #       shown a specific impact, yet.
139
141
        self._initialize_nodes(parent_map)
140
142
        self._find_gdfo()
141
143
 
183
185
            parent_keys = <object>temp_parent_keys
184
186
            num_parent_keys = len(parent_keys)
185
187
            node = self._get_or_create_node(key)
186
 
            # We know how many parents, so we could pre allocate an exact sized
187
 
            # tuple here
 
188
            # We know how many parents, so we pre allocate the tuple
188
189
            parent_nodes = PyTuple_New(num_parent_keys)
189
 
            # We use iter here, because parent_keys maybe be a list or tuple
190
190
            for pos2 from 0 <= pos2 < num_parent_keys:
 
191
                # Note: it costs us 10ms out of 40ms to lookup all of these
 
192
                #       parents, it doesn't seem to be an allocation overhead,
 
193
                #       but rather a lookup overhead. There doesn't seem to be
 
194
                #       a way around it, and that is one reason why
 
195
                #       KnownGraphNode maintains a direct pointer to the parent
 
196
                #       node.
 
197
                # We use [] because parent_keys may be a tuple or list
191
198
                parent_node = self._get_or_create_node(parent_keys[pos2])
192
199
                # PyTuple_SET_ITEM will steal a reference, so INCREF first
193
200
                Py_INCREF(parent_node)
335
342
        if self.do_cache:
336
343
            PyDict_SetItem(self._known_heads, heads_key, heads)
337
344
        return heads
 
345
 
 
346
    def topo_sort(self):
 
347
        """Return the nodes in topological order.
 
348
 
 
349
        All parents must occur before all children.
 
350
        """
 
351
        # This is, for the most part, the same iteration order that we used for
 
352
        # _find_gdfo, consider finding a way to remove the duplication
 
353
        # In general, we find the 'tails' (nodes with no parents), and then
 
354
        # walk to the children. For children that have all of their parents
 
355
        # yielded, we queue up the child to be yielded as well.
 
356
        cdef _KnownGraphNode node
 
357
        cdef _KnownGraphNode child
 
358
        cdef PyObject *temp
 
359
        cdef Py_ssize_t pos
 
360
        cdef int replace
 
361
        cdef Py_ssize_t last_item
 
362
 
 
363
        pending = self._find_tails()
 
364
        if PyList_GET_SIZE(pending) == 0 and len(self._nodes) > 0:
 
365
            raise errors.GraphCycleError(self._nodes)
 
366
 
 
367
        topo_order = []
 
368
 
 
369
        last_item = PyList_GET_SIZE(pending) - 1
 
370
        while last_item >= 0:
 
371
            # Avoid pop followed by push, instead, peek, and replace
 
372
            # timing shows this is 930ms => 770ms for OOo
 
373
            node = _get_list_node(pending, last_item)
 
374
            last_item = last_item - 1
 
375
            if node.parents is not None:
 
376
                # We don't include ghost parents
 
377
                PyList_Append(topo_order, node.key)
 
378
            for pos from 0 <= pos < PyList_GET_SIZE(node.children):
 
379
                child = _get_list_node(node.children, pos)
 
380
                if child.gdfo == -1:
 
381
                    # We know we have a graph cycle because a node has a parent
 
382
                    # which we couldn't find
 
383
                    raise errors.GraphCycleError(self._nodes)
 
384
                child.seen = child.seen + 1
 
385
                if child.seen == PyTuple_GET_SIZE(child.parents):
 
386
                    # All parents of this child have been yielded, queue this
 
387
                    # one to be yielded as well
 
388
                    last_item = last_item + 1
 
389
                    if last_item < PyList_GET_SIZE(pending):
 
390
                        Py_INCREF(child) # SetItem steals a ref
 
391
                        PyList_SetItem(pending, last_item, child)
 
392
                    else:
 
393
                        PyList_Append(pending, child)
 
394
                    # We have queued this node, we don't need to track it
 
395
                    # anymore
 
396
                    child.seen = 0
 
397
        # We started from the parents, so we don't need to do anymore work
 
398
        return topo_order
 
399
 
 
400
 
 
401
    def merge_sort(self, tip_key):
 
402
        """Compute the merge sorted graph output."""
 
403
        cdef _MergeSorter sorter
 
404
 
 
405
        # TODO: consider disabling gc since we are allocating a lot of nodes
 
406
        #       that won't be collectable anyway. real world testing has not
 
407
        #       shown a specific impact, yet.
 
408
        sorter = _MergeSorter(self, tip_key)
 
409
        return sorter.topo_order()
 
410
 
 
411
 
 
412
cdef class _MergeSortNode:
 
413
    """Tracks information about a node during the merge_sort operation."""
 
414
 
 
415
    # Public api
 
416
    cdef public object key
 
417
    cdef public long merge_depth
 
418
    cdef public object end_of_merge # True/False Is this the end of the current merge
 
419
 
 
420
    # Private api, used while computing the information
 
421
    cdef _KnownGraphNode left_parent
 
422
    cdef _KnownGraphNode left_pending_parent
 
423
    cdef object pending_parents # list of _KnownGraphNode for non-left parents
 
424
    cdef long _revno_first
 
425
    cdef long _revno_second
 
426
    cdef long _revno_last
 
427
    # TODO: turn these into flag/bit fields rather than individual members
 
428
    cdef int is_first_child # Is this the first child?
 
429
    cdef int seen_by_child # A child node has seen this parent
 
430
    cdef int completed # Fully Processed
 
431
 
 
432
    def __init__(self, key):
 
433
        self.key = key
 
434
        self.merge_depth = -1
 
435
        self.left_parent = None
 
436
        self.left_pending_parent = None
 
437
        self.pending_parents = None
 
438
        self._revno_first = -1
 
439
        self._revno_second = -1
 
440
        self._revno_last = -1
 
441
        self.is_first_child = 0
 
442
        self.seen_by_child = 0
 
443
        self.completed = 0
 
444
 
 
445
    def __repr__(self):
 
446
        return '%s(depth:%s rev:%s,%s,%s first:%s seen:%s)' % (self.__class__.__name__,
 
447
            self.merge_depth,
 
448
            self._revno_first, self._revno_second, self._revno_last,
 
449
            self.is_first_child, self.seen_by_child)
 
450
 
 
451
    cdef int has_pending_parents(self):
 
452
        if self.left_pending_parent is not None or self.pending_parents:
 
453
            return 1
 
454
        return 0
 
455
 
 
456
    cdef object _revno(self):
 
457
        if self._revno_first == -1:
 
458
            if self._revno_second != -1:
 
459
                raise RuntimeError('Something wrong with: %s' % (self,))
 
460
            return (self._revno_last,)
 
461
        else:
 
462
            return (self._revno_first, self._revno_second, self._revno_last)
 
463
 
 
464
    property revno:
 
465
        def __get__(self):
 
466
            return self._revno()
 
467
 
 
468
 
 
469
cdef class _MergeSorter:
 
470
    """This class does the work of computing the merge_sort ordering.
 
471
 
 
472
    We have some small advantages, in that we get all the extra information
 
473
    that KnownGraph knows, like knowing the child lists, etc.
 
474
    """
 
475
 
 
476
    # Current performance numbers for merge_sort(bzr_dev_parent_map):
 
477
    #  302ms tsort.merge_sort()
 
478
    #   91ms graph.KnownGraph().merge_sort()
 
479
    #   40ms kg.merge_sort()
 
480
 
 
481
    cdef KnownGraph graph
 
482
    cdef object _depth_first_stack  # list
 
483
    cdef Py_ssize_t _last_stack_item # offset to last item on stack
 
484
    # cdef object _ms_nodes # dict of key => _MergeSortNode
 
485
    cdef object _revno_to_branch_count # {revno => num child branches}
 
486
    cdef object _scheduled_nodes # List of nodes ready to be yielded
 
487
 
 
488
    def __init__(self, known_graph, tip_key):
 
489
        cdef _KnownGraphNode node
 
490
 
 
491
        self.graph = known_graph
 
492
        # self._ms_nodes = {}
 
493
        self._revno_to_branch_count = {}
 
494
        self._depth_first_stack = []
 
495
        self._last_stack_item = -1
 
496
        self._scheduled_nodes = []
 
497
        if (tip_key is not None and tip_key != NULL_REVISION
 
498
            and tip_key != (NULL_REVISION,)):
 
499
            node = self.graph._nodes[tip_key]
 
500
            self._get_ms_node(node)
 
501
            self._push_node(node, 0)
 
502
 
 
503
    cdef _MergeSortNode _get_ms_node(self, _KnownGraphNode node):
 
504
        cdef PyObject *temp_node
 
505
        cdef _MergeSortNode ms_node
 
506
 
 
507
        if node.extra is None:
 
508
            ms_node = _MergeSortNode(node.key)
 
509
            node.extra = ms_node
 
510
        else:
 
511
            ms_node = <_MergeSortNode>node.extra
 
512
        return ms_node
 
513
 
 
514
    cdef _push_node(self, _KnownGraphNode node, long merge_depth):
 
515
        cdef _KnownGraphNode parent_node
 
516
        cdef _MergeSortNode ms_node, ms_parent_node
 
517
        cdef Py_ssize_t pos
 
518
 
 
519
        ms_node = self._get_ms_node(node)
 
520
        ms_node.merge_depth = merge_depth
 
521
        if PyTuple_GET_SIZE(node.parents) > 0:
 
522
            parent_node = _get_parent(node.parents, 0)
 
523
            ms_node.left_parent = parent_node
 
524
            ms_node.left_pending_parent = parent_node
 
525
        if PyTuple_GET_SIZE(node.parents) > 1:
 
526
            ms_node.pending_parents = []
 
527
            for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):
 
528
                parent_node = _get_parent(node.parents, pos)
 
529
                if parent_node.parents is None: # ghost
 
530
                    continue
 
531
                PyList_Append(ms_node.pending_parents, parent_node)
 
532
 
 
533
        ms_node.is_first_child = 1
 
534
        if ms_node.left_parent is not None:
 
535
            ms_parent_node = self._get_ms_node(ms_node.left_parent)
 
536
            if ms_parent_node.seen_by_child:
 
537
                ms_node.is_first_child = 0
 
538
            ms_parent_node.seen_by_child = 1
 
539
        self._last_stack_item = self._last_stack_item + 1
 
540
        if self._last_stack_item < PyList_GET_SIZE(self._depth_first_stack):
 
541
            Py_INCREF(node) # SetItem steals a ref
 
542
            PyList_SetItem(self._depth_first_stack, self._last_stack_item,
 
543
                           node)
 
544
        else:
 
545
            PyList_Append(self._depth_first_stack, node)
 
546
 
 
547
    cdef _pop_node(self):
 
548
        cdef PyObject *temp
 
549
        cdef _MergeSortNode ms_node, ms_parent_node, ms_prev_node
 
550
        cdef _KnownGraphNode node, parent_node, prev_node
 
551
 
 
552
        node = _get_list_node(self._depth_first_stack, self._last_stack_item)
 
553
        ms_node = <_MergeSortNode>node.extra
 
554
        self._last_stack_item = self._last_stack_item - 1
 
555
        if ms_node.left_parent is not None:
 
556
            # Assign the revision number from the left-hand parent
 
557
            ms_parent_node = <_MergeSortNode>ms_node.left_parent.extra
 
558
            if ms_node.is_first_child:
 
559
                # First child just increments the final digit
 
560
                ms_node._revno_first = ms_parent_node._revno_first
 
561
                ms_node._revno_second = ms_parent_node._revno_second
 
562
                ms_node._revno_last = ms_parent_node._revno_last + 1
 
563
            else:
 
564
                # Not the first child, make a new branch
 
565
                #  (mainline_revno, branch_count, 1)
 
566
                if ms_parent_node._revno_first == -1:
 
567
                    # Mainline ancestor, the increment is on the last digit
 
568
                    base_revno = ms_parent_node._revno_last
 
569
                else:
 
570
                    base_revno = ms_parent_node._revno_first
 
571
                temp = PyDict_GetItem(self._revno_to_branch_count,
 
572
                                      base_revno)
 
573
                if temp == NULL:
 
574
                    branch_count = 1
 
575
                else:
 
576
                    branch_count = (<object>temp) + 1
 
577
                PyDict_SetItem(self._revno_to_branch_count, base_revno,
 
578
                               branch_count)
 
579
                ms_node._revno_first = base_revno
 
580
                ms_node._revno_second = branch_count
 
581
                ms_node._revno_last = 1
 
582
        else:
 
583
            temp = PyDict_GetItem(self._revno_to_branch_count, 0)
 
584
            if temp == NULL:
 
585
                # The first root node doesn't have a 3-digit revno
 
586
                root_count = 0
 
587
                ms_node._revno_first = -1
 
588
                ms_node._revno_second = -1
 
589
                ms_node._revno_last = 1
 
590
            else:
 
591
                root_count = (<object>temp) + 1
 
592
                ms_node._revno_first = 0
 
593
                ms_node._revno_second = root_count
 
594
                ms_node._revno_last = 1
 
595
            PyDict_SetItem(self._revno_to_branch_count, 0, root_count)
 
596
        ms_node.completed = 1
 
597
        if PyList_GET_SIZE(self._scheduled_nodes) == 0:
 
598
            # The first scheduled node is always the end of merge
 
599
            ms_node.end_of_merge = True
 
600
        else:
 
601
            prev_node = _get_list_node(self._scheduled_nodes,
 
602
                                    PyList_GET_SIZE(self._scheduled_nodes) - 1)
 
603
            ms_prev_node = <_MergeSortNode>prev_node.extra
 
604
            if ms_prev_node.merge_depth < ms_node.merge_depth:
 
605
                # The previously pushed node is to our left, so this is the end
 
606
                # of this right-hand chain
 
607
                ms_node.end_of_merge = True
 
608
            elif (ms_prev_node.merge_depth == ms_node.merge_depth
 
609
                  and prev_node not in node.parents):
 
610
                # The next node is not a direct parent of this node
 
611
                ms_node.end_of_merge = True
 
612
            else:
 
613
                ms_node.end_of_merge = False
 
614
        PyList_Append(self._scheduled_nodes, node)
 
615
 
 
616
    cdef _schedule_stack(self):
 
617
        cdef _KnownGraphNode last_node, next_node
 
618
        cdef _MergeSortNode ms_node, ms_last_node, ms_next_node
 
619
        cdef long next_merge_depth
 
620
        ordered = []
 
621
        while self._last_stack_item >= 0:
 
622
            # Peek at the last item on the stack
 
623
            last_node = _get_list_node(self._depth_first_stack,
 
624
                                       self._last_stack_item)
 
625
            if last_node.gdfo == -1:
 
626
                # if _find_gdfo skipped a node, that means there is a graph
 
627
                # cycle, error out now
 
628
                raise errors.GraphCycleError(self.graph._nodes)
 
629
            ms_last_node = <_MergeSortNode>last_node.extra
 
630
            if not ms_last_node.has_pending_parents():
 
631
                # Processed all parents, pop this node
 
632
                self._pop_node()
 
633
                continue
 
634
            while ms_last_node.has_pending_parents():
 
635
                if ms_last_node.left_pending_parent is not None:
 
636
                    # recurse depth first into the primary parent
 
637
                    next_node = ms_last_node.left_pending_parent
 
638
                    ms_last_node.left_pending_parent = None
 
639
                else:
 
640
                    # place any merges in right-to-left order for scheduling
 
641
                    # which gives us left-to-right order after we reverse
 
642
                    # the scheduled queue.
 
643
                    # Note: This has the effect of allocating common-new
 
644
                    #       revisions to the right-most subtree rather than the
 
645
                    #       left most, which will display nicely (you get
 
646
                    #       smaller trees at the top of the combined merge).
 
647
                    next_node = ms_last_node.pending_parents.pop()
 
648
                ms_next_node = self._get_ms_node(next_node)
 
649
                if ms_next_node.completed:
 
650
                    # this parent was completed by a child on the
 
651
                    # call stack. skip it.
 
652
                    continue
 
653
                # otherwise transfer it from the source graph into the
 
654
                # top of the current depth first search stack.
 
655
 
 
656
                if next_node is ms_last_node.left_parent:
 
657
                    next_merge_depth = ms_last_node.merge_depth
 
658
                else:
 
659
                    next_merge_depth = ms_last_node.merge_depth + 1
 
660
                self._push_node(next_node, next_merge_depth)
 
661
                # and do not continue processing parents until this 'call'
 
662
                # has recursed.
 
663
                break
 
664
 
 
665
    cdef topo_order(self):
 
666
        cdef _MergeSortNode ms_node
 
667
        cdef _KnownGraphNode node
 
668
        cdef Py_ssize_t pos
 
669
        cdef PyObject *temp_key, *temp_node
 
670
 
 
671
        # Note: allocating a _MergeSortNode and deallocating it for all nodes
 
672
        #       costs approx 8.52ms (21%) of the total runtime
 
673
        #       We might consider moving the attributes into the base
 
674
        #       KnownGraph object.
 
675
        self._schedule_stack()
 
676
 
 
677
        # We've set up the basic schedule, now we can continue processing the
 
678
        # output.
 
679
        # Note: This final loop costs us 40.0ms => 28.8ms (11ms, 25%) on
 
680
        #       bzr.dev, to convert the internal Object representation into a
 
681
        #       Tuple representation...
 
682
        #       2ms is walking the data and computing revno tuples
 
683
        #       7ms is computing the return tuple
 
684
        #       4ms is PyList_Append()
 
685
        ordered = []
 
686
        # output the result in reverse order, and separate the generated info
 
687
        for pos from PyList_GET_SIZE(self._scheduled_nodes) > pos >= 0:
 
688
            node = _get_list_node(self._scheduled_nodes, pos)
 
689
            ms_node = <_MergeSortNode>node.extra
 
690
            PyList_Append(ordered, ms_node)
 
691
            node.extra = None
 
692
        # Clear out the scheduled nodes now that we're done
 
693
        self._scheduled_nodes = []
 
694
        return ordered