← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tsort.py

  • Committer: John Arbash Meinel
  • Date: 2007-04-19 00:03:01 UTC
  • mto: This revision was merged to the branch mainline in revision 2432.
  • Revision ID: john@arbash-meinel.com-20070419000301-ud6ambkulyaulnfr
Inline self._pop_node and self._push_node
These are still separate functions, but rather than using self._a_stack.append
we assign a local variable a_stack_append, and call it directly.
This drops the merge_sort() time down to approx 385ms-400ms
With that large of a speed-up it seems worth the loss
in readability. (This is almost 50% of the original time)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tsort.py
423
423
        # These are safe to offload to local variables, because they are used
424
424
        # as a stack and modified in place, never assigned to.
425
425
        node_name_stack = self._node_name_stack
 
426
        node_merge_depth_stack = self._node_merge_depth_stack
426
427
        pending_parents_stack = self._pending_parents_stack
427
428
        left_subtree_pushed_stack = self._left_subtree_pushed_stack
428
429
        completed_node_names = self._completed_node_names
429
 
 
430
 
        pop_node = self._pop_node
431
 
        push_node = self._push_node
 
430
        scheduled_nodes = self._scheduled_nodes
 
431
 
 
432
        graph_pop = self._graph.pop
 
433
 
 
434
        def push_node(node_name, merge_depth, parents,
 
435
                      node_name_stack_append=node_name_stack.append,
 
436
                      node_merge_depth_stack_append=node_merge_depth_stack.append,
 
437
                      left_subtree_pushed_stack_append=left_subtree_pushed_stack.append,
 
438
                      pending_parents_stack_append=pending_parents_stack.append,
 
439
                      assigned_sequence_stack_append=self._assigned_sequence_stack.append,
 
440
                      original_graph=self._original_graph,
 
441
                      revnos=self._revnos,
 
442
                      ):
 
443
            """Add node_name to the pending node stack.
 
444
 
 
445
            Names in this stack will get emitted into the output as they are popped
 
446
            off the stack.
 
447
 
 
448
            This inlines a lot of self._variable.append functions as local
 
449
            variables.
 
450
            """
 
451
            node_name_stack_append(node_name)
 
452
            node_merge_depth_stack_append(merge_depth)
 
453
            left_subtree_pushed_stack_append(False)
 
454
            pending_parents_stack_append(list(parents))
 
455
            # as we push it, assign it a sequence number against its parent:
 
456
            parents = original_graph[node_name]
 
457
            if parents:
 
458
                # node has parents, assign from the left most parent.
 
459
                parent_revno = revnos[parents[0]]
 
460
                sequence = parent_revno[1]
 
461
                parent_revno[1] += 1
 
462
            else:
 
463
                # no parents, use the root sequence
 
464
                sequence = self._root_sequence
 
465
                self._root_sequence +=1
 
466
            assigned_sequence_stack_append(sequence)
 
467
 
 
468
        def pop_node(node_name_stack_pop=node_name_stack.pop,
 
469
                     node_merge_depth_stack_pop=node_merge_depth_stack.pop,
 
470
                     assigned_sequence_stack_pop=self._assigned_sequence_stack.pop,
 
471
                     left_subtree_pushed_stack_pop=left_subtree_pushed_stack.pop,
 
472
                     pending_parents_stack_pop=pending_parents_stack.pop,
 
473
                     original_graph=self._original_graph,
 
474
                     revnos=self._revnos,
 
475
                     completed_node_names_add=self._completed_node_names.add,
 
476
                     scheduled_nodes_append=scheduled_nodes.append,
 
477
                    ):
 
478
            """Pop the top node off the stack
 
479
 
 
480
            The node is appended to the sorted output.
 
481
            """
 
482
            # we are returning from the flattened call frame:
 
483
            # pop off the local variables
 
484
            node_name = node_name_stack_pop()
 
485
            merge_depth = node_merge_depth_stack_pop()
 
486
            sequence = assigned_sequence_stack_pop()
 
487
            # remove this node from the pending lists:
 
488
            left_subtree_pushed_stack_pop()
 
489
            pending_parents_stack_pop()
 
490
 
 
491
            parents = original_graph[node_name]
 
492
            if parents:
 
493
                # node has parents, assign from the left most parent.
 
494
                parent_revno = revnos[parents[0]]
 
495
                if sequence:
 
496
                    # not the first child, make a new branch
 
497
                    revno = parent_revno[0] + (sequence, 1)
 
498
                else:
 
499
                    # increment the sequence number within the branch
 
500
                    revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
 
501
            else:
 
502
                # no parents, use the root sequence
 
503
                if sequence:
 
504
                    # make a parallel import revision number
 
505
                    revno = (0, sequence, 1)
 
506
                else:
 
507
                    revno = (1,)
 
508
 
 
509
            # store the revno for this node for future reference
 
510
            revnos[node_name][0] = revno
 
511
            completed_node_names_add(node_name)
 
512
            scheduled_nodes_append((node_name, merge_depth, revno))
 
513
            return node_name
 
514
 
432
515
 
433
516
        while node_name_stack:
434
517
            # loop until this call completes.
460
543
                    # otherwise transfer it from the source graph into the
461
544
                    # top of the current depth first search stack.
462
545
                    try:
463
 
                        parents = self._graph.pop(next_node_name)
 
546
                        parents = graph_pop(next_node_name)
464
547
                    except KeyError:
465
548
                        # if the next node is not in the source graph it has
466
549
                        # already been popped from it and placed into the
476
559
                        next_merge_depth = 0
477
560
                        left_subtree_pushed_stack[-1] = True
478
561
                    next_merge_depth = (
479
 
                        self._node_merge_depth_stack[-1] + next_merge_depth)
 
562
                        node_merge_depth_stack[-1] + next_merge_depth)
480
563
                    push_node(
481
564
                        next_node_name,
482
565
                        next_merge_depth,
484
567
                    # and do not continue processing parents until this 'call' 
485
568
                    # has recursed.
486
569
                    break
 
570
 
487
571
        # We have scheduled the graph. Now deliver the ordered output:
488
572
        sequence_number = 0
489
 
        scheduled_nodes = self._scheduled_nodes
490
573
        stop_revision = self._stop_revision
491
574
        generate_revno = self._generate_revno
492
575
        original_graph = self._original_graph