~bzr-pqm/bzr/bzr.dev

Viewing changes to bzrlib/_known_graph_pyx.pyx

Committer: John Arbash Meinel
Date: 2009-08-16 16:56:30 UTC
mto: This revision was merged to the branch mainline in revision 4629.
Revision ID: john@arbash-meinel.com-20090816165630-g94xm2dan6i03dvv

Switch from having a MergeSortNode => KnownGraphNode to
having KnownGraphNode.extra => MergeSortNode

This avoids some of the dict lookups, etc, especially while creating the
nodes. I'm not 100% sure I like the layering, though.

I suppose it could be considered a 'void*' for processing algorithms to
use, similar to the \.seen member.

# 92ms graph.KnownGraph().merge_sort()
# 42ms kg.merge_sort()

files modified:
bzrlib/_known_graph_pyx.pyx

Show diffs side-by-side

added added

removed removed

bzrlib/_known_graph_pyx.pyx

cdef object children

cdef public long gdfo

cdef int seen

cdef object extra

def __init__(self, key):

cdef int i

# Greatest distance from origin

self.gdfo = -1

self.seen = 0

self.extra = None

property child_keys:

def __get__(self):

409

411

cdef class _MergeSortNode:

410

412

"""Tracks information about a node during the merge_sort operation."""

411

413

412

cdef _KnownGraphNode node

413

414

cdef Py_ssize_t merge_depth

414

cdef _MergeSortNode left_ms_parent

415

cdef _MergeSortNode left_pending_parent

416

cdef object pending_parents # list of _MergeSortNode for non-left parents

415

cdef _KnownGraphNode left_parent

416

cdef _KnownGraphNode left_pending_parent

417

cdef object pending_parents # list of _KnownGraphNode for non-left parents

417

418

cdef Py_ssize_t revno_first

418

419

cdef Py_ssize_t revno_second

419

420

cdef Py_ssize_t revno_last

422

423

cdef int seen_by_child # A child node has seen this parent

423

424

cdef int completed # Fully Processed

424

425

def __init__(self, node):

426

self.node = node

426

def __init__(self):

427

self.merge_depth = -1

428

self.left_ms_parent = None

428

self.left_parent = None

429

self.left_pending_parent = None

430

self.pending_parents = None

431

self.revno_first = -1

436

self.completed = 0

437

438

def __repr__(self):

439

cdef _MergeSortNode ms_par

440

left_key = None

441

if self.left_ms_parent is not None:

442

left_key = self.left_ms_parent.node.key

443

left_pp = None

444

if self.left_pending_parent is not None:

445

left_pp = self.left_pending_parent.node.key

446

pp = []

447

if self.pending_parents:

448

for ms_par in self.pending_parents:

449

pp.append(ms_par.node.key)

450

return '%s(%s depth:%s rev:%s,%s,%s first:%s seen:%s)' % (self.__class__.__name__,

451

self.node.key, self.merge_depth,

439

return '%s(depth:%s rev:%s,%s,%s first:%s seen:%s)' % (self.__class__.__name__,

440

self.merge_depth,

452

441

self.revno_first, self.revno_second, self.revno_last,

453

442

self.is_first_child, self.seen_by_child)

454

443

458

447

return 0

459

448

460

449

461

cdef _MergeSortNode _get_ms_node(lst, Py_ssize_t pos):

462

cdef PyObject *temp_node

463

464

temp_node = PyList_GET_ITEM(lst, pos)

465

return <_MergeSortNode>temp_node

466

450

# cdef _MergeSortNode _get_ms_node(lst, Py_ssize_t pos):

451

# cdef PyObject *temp_node

452

453

# temp_node = PyList_GET_ITEM(lst, pos)

454

# return <_MergeSortNode>temp_node

455

467

456

468

457

cdef class _MergeSorter:

469

458

"""This class does the work of computing the merge_sort ordering.

474

463

475

464

# Current performance numbers for merge_sort(bzr_dev_parent_map):

476

465

# 310ms tsort.merge_sort()

477

# 103ms graph.KnownGraph().merge_sort()

478

# 55ms kg.merge_sort()

466

# 92ms graph.KnownGraph().merge_sort()

467

# 42ms kg.merge_sort()

479

468

480

469

cdef KnownGraph graph

481

470

cdef object _depth_first_stack # list

482

471

cdef Py_ssize_t _last_stack_item # offset to last item on stack

483

cdef object _ms_nodes # dict of key => _MergeSortNode

472

# cdef object _ms_nodes # dict of key => _MergeSortNode

484

473

cdef object _revno_to_branch_count # {revno => num child branches}

485

474

cdef object _scheduled_nodes # List of nodes ready to be yielded

486

475

487

476

def __init__(self, known_graph, tip_key):

488

477

cdef _KnownGraphNode node

489

cdef _MergeSortNode ms_node

478

490

479

self.graph = known_graph

491

self._ms_nodes = {}

480

# self._ms_nodes = {}

492

481

self._revno_to_branch_count = {}

493

482

self._depth_first_stack = []

494

483

self._last_stack_item = -1

495

484

self._scheduled_nodes = []

496

485

if tip_key is not None and tip_key != NULL_REVISION:

497

486

node = self.graph._nodes[tip_key]

498

ms_node = self._get_or_create_node(node)

499

self._push_node(ms_node, 0)

487

self._push_node(node, 0)

500

488

501

489

cdef _MergeSortNode _get_or_create_node(self, _KnownGraphNode node):

502

490

cdef PyObject *temp_node

503

491

cdef _MergeSortNode ms_node

504

492

505

temp_node = PyDict_GetItem(self._ms_nodes, node.key)

506

if temp_node == NULL:

507

ms_node = _MergeSortNode(node)

508

PyDict_SetItem(self._ms_nodes, node.key, ms_node)

493

if node.extra is None:

494

ms_node = _MergeSortNode()

495

node.extra = ms_node

509

496

else:

510

ms_node = <_MergeSortNode>temp_node

497

ms_node = <_MergeSortNode>node.extra

511

498

return ms_node

512

499

513

cdef _push_node(self, _MergeSortNode ms_node, Py_ssize_t merge_depth):

500

cdef _push_node(self, _KnownGraphNode node, Py_ssize_t merge_depth):

514

501

cdef _KnownGraphNode parent_node

515

cdef _MergeSortNode ms_parent_node

502

cdef _MergeSortNode ms_node, ms_parent_node

516

503

cdef Py_ssize_t pos

517

504

505

ms_node = self._get_or_create_node(node)

518

506

ms_node.merge_depth = merge_depth

519

if PyTuple_GET_SIZE(ms_node.node.parents) > 0:

520

parent_node = _get_parent(ms_node.node.parents, 0)

521

ms_node.left_ms_parent = self._get_or_create_node(

522

parent_node)

523

ms_node.left_pending_parent = ms_node.left_ms_parent

524

if PyTuple_GET_SIZE(ms_node.node.parents) > 1:

525

ms_node.pending_parents = []

526

for pos from 1 <= pos < PyTuple_GET_SIZE(ms_node.node.parents):

527

parent_node = _get_parent(ms_node.node.parents, pos)

528

PyList_Append(ms_node.pending_parents,

529

self._get_or_create_node(parent_node))

507

if PyTuple_GET_SIZE(node.parents) > 0:

508

parent_node = _get_parent(node.parents, 0)

509

ms_node.left_parent = parent_node

510

ms_node.left_pending_parent = parent_node

511

if PyTuple_GET_SIZE(node.parents) > 1:

512

ms_node.pending_parents = list(node.parents[1:])

513

# ms_node.pending_parents = []

514

# for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):

515

# parent_node = _get_parent(node.parents, pos)

516

# PyList_Append(ms_node.pending_parents, parent_node)

530

517

531

518

ms_node.is_first_child = 1

532

if ms_node.left_ms_parent is not None:

533

if ms_node.left_ms_parent.seen_by_child:

519

if ms_node.left_parent is not None:

520

ms_parent_node = self._get_or_create_node(ms_node.left_parent)

521

if ms_parent_node.seen_by_child:

534

522

ms_node.is_first_child = 0

535

ms_node.left_ms_parent.seen_by_child = 1

523

ms_parent_node.seen_by_child = 1

536

524

self._last_stack_item = self._last_stack_item + 1

537

525

if self._last_stack_item < PyList_GET_SIZE(self._depth_first_stack):

538

Py_INCREF(ms_node) # SetItem steals a ref

526

Py_INCREF(node) # SetItem steals a ref

539

527

PyList_SetItem(self._depth_first_stack, self._last_stack_item,

540

ms_node)

528

node)

541

529

else:

542

PyList_Append(self._depth_first_stack, ms_node)

530

PyList_Append(self._depth_first_stack, node)

543

531

# print 'pushed: %s' % (ms_node,)

544

532

545

533

cdef _pop_node(self):

546

534

cdef PyObject *temp

547

cdef _MergeSortNode ms_node

548

cdef _KnownGraphNode parent_node

535

cdef _MergeSortNode ms_node, ms_parent_node

536

cdef _KnownGraphNode node, parent_node

549

537

550

538

assert self._last_stack_item >= 0

551

ms_node = _get_ms_node(self._depth_first_stack, self._last_stack_item)

539

node = _get_list_node(self._depth_first_stack, self._last_stack_item)

540

ms_node = <_MergeSortNode>node.extra

552

541

self._last_stack_item = self._last_stack_item - 1

553

542

# print 'popping: %s' % (ms_node,)

554

if ms_node.left_ms_parent is not None:

543

if ms_node.left_parent is not None:

555

544

# Assign the revision number for *this* node, from its left-hand

556

545

# parent

546

ms_parent_node = <_MergeSortNode>ms_node.left_parent.extra

557

547

if ms_node.is_first_child:

558

548

# First child just increments the final digit

559

ms_node.revno_first = ms_node.left_ms_parent.revno_first

560

ms_node.revno_second = ms_node.left_ms_parent.revno_second

561

ms_node.revno_last = ms_node.left_ms_parent.revno_last + 1

549

ms_node.revno_first = ms_parent_node.revno_first

550

ms_node.revno_second = ms_parent_node.revno_second

551

ms_node.revno_last = ms_parent_node.revno_last + 1

562

552

else:

563

553

# Not the first child, make a new branch

564

if ms_node.left_ms_parent.revno_first == -1:

554

if ms_parent_node.revno_first == -1:

565

555

# Mainline ancestor, the increment is on the last digit

566

base_revno = ms_node.left_ms_parent.revno_last

556

base_revno = ms_parent_node.revno_last

567

557

else:

568

base_revno = ms_node.left_ms_parent.revno_first

558

base_revno = ms_parent_node.revno_first

569

559

temp = PyDict_GetItem(self._revno_to_branch_count,

570

560

base_revno)

571

561

if temp == NULL:

574

564

branch_count = (<object>temp) + 1

575

565

PyDict_SetItem(self._revno_to_branch_count, base_revno,

576

566

branch_count)

577

if ms_node.left_ms_parent.revno_first == -1:

578

ms_node.revno_first = ms_node.left_ms_parent.revno_last

567

if ms_parent_node.revno_first == -1:

568

ms_node.revno_first = ms_parent_node.revno_last

579

569

else:

580

ms_node.revno_first = ms_node.left_ms_parent.revno_first

570

ms_node.revno_first = ms_parent_node.revno_first

581

571

ms_node.revno_second = branch_count

582

572

ms_node.revno_last = 1

583

573

else:

594

584

ms_node.revno_last = 1

595

585

self._revno_to_branch_count[0] = root_count

596

586

ms_node.completed = 1

597

PyList_Append(self._scheduled_nodes, ms_node)

587

PyList_Append(self._scheduled_nodes, node)

598

588

599

589

cdef _schedule_stack(self):

590

cdef _KnownGraphNode last_node, next_node

600

591

cdef _MergeSortNode ms_node, ms_last_node, ms_next_node

601

592

cdef Py_ssize_t next_merge_depth

602

593

ordered = []

604

595

# Peek at the last item on the stack

605

596

# print self._depth_first_stack

606

597

# print ' ', self._scheduled_nodes

607

ms_last_node = _get_ms_node(self._depth_first_stack,

608

self._last_stack_item)

598

last_node = _get_list_node(self._depth_first_stack,

599

self._last_stack_item)

600

ms_last_node = <_MergeSortNode>last_node.extra

609

601

if not ms_last_node.has_pending_parents():

610

602

# Processed all parents, pop this node

611

603

self._pop_node()

613

605

while ms_last_node.has_pending_parents():

614

606

if ms_last_node.left_pending_parent is not None:

615

607

# recurse depth first into the primary parent

616

ms_next_node = ms_last_node.left_pending_parent

608

next_node = ms_last_node.left_pending_parent

617

609

ms_last_node.left_pending_parent = None

618

610

else:

619

611

# place any merges in right-to-left order for scheduling

623

615

# subtree rather than the left most, which will

624

616

# display nicely (you get smaller trees at the top

625

617

# of the combined merge).

626

ms_next_node = ms_last_node.pending_parents.pop()

618

next_node = ms_last_node.pending_parents.pop()

619

ms_next_node = self._get_or_create_node(next_node)

627

620

if ms_next_node.completed:

628

621

# this parent was completed by a child on the

629

622

# call stack. skip it.

643

636

644

637

assert ms_next_node is not None

645

638

next_merge_depth = 0

646

if ms_next_node is ms_last_node.left_ms_parent:

639

if next_node is ms_last_node.left_parent:

647

640

next_merge_depth = 0

648

641

else:

649

642

next_merge_depth = 1

650

643

next_merge_depth = next_merge_depth + ms_last_node.merge_depth

651

self._push_node(ms_next_node, next_merge_depth)

644

self._push_node(next_node, next_merge_depth)

652

645

# and do not continue processing parents until this 'call'

653

646

# has recursed.

654

647

break

655

648

656

649

cdef topo_order(self):

657

cdef _MergeSortNode ms_node, ms_last_node

658

cdef _KnownGraphNode next_node

650

cdef _MergeSortNode ms_node, ms_prev_node

651

cdef _KnownGraphNode node, prev_node

659

652

cdef Py_ssize_t pos

660

653

661

654

# print

671

664

ordered = []

672

665

pos = PyList_GET_SIZE(self._scheduled_nodes) - 1

673

666

if pos >= 0:

674

ms_last_node = _get_ms_node(self._scheduled_nodes, pos)

667

prev_node = _get_list_node(self._scheduled_nodes, pos)

668

ms_prev_node = <_MergeSortNode>prev_node.extra

675

669

while pos >= 0:

676

ms_node = ms_last_node

670

if node is not None:

671

# Clear out the extra info we don't need

672

node.extra = None

673

node = prev_node

674

ms_node = ms_prev_node

677

675

pos = pos - 1

678

676

if pos == -1:

679

677

# Final node is always the end-of-chain

680

678

end_of_merge = True

681

679

else:

682

ms_last_node = _get_ms_node(self._scheduled_nodes, pos)

683

if ms_last_node.merge_depth < ms_node.merge_depth:

680

prev_node = _get_list_node(self._scheduled_nodes, pos)

681

ms_prev_node = <_MergeSortNode>prev_node.extra

682

if ms_prev_node.merge_depth < ms_node.merge_depth:

684

683

# Next node is to our left, so this is the end of the right

685

684

# chain

686

685

end_of_merge = True

687

elif (ms_last_node.merge_depth == ms_node.merge_depth

688

and ms_last_node.node not in ms_node.node.parents):

686

elif (ms_prev_node.merge_depth == ms_node.merge_depth

687

and prev_node not in node.parents):

689

688

# The next node is not a direct parent of this node

690

689

end_of_merge = True

691

690

else:

697

696

else:

698

697

revno = (ms_node.revno_first, ms_node.revno_second,

699

698

ms_node.revno_last)

700

PyList_Append(ordered, (sequence_number, ms_node.node.key,

699

PyList_Append(ordered, (sequence_number, node.key,

701

700

ms_node.merge_depth, revno, end_of_merge))

702

701

sequence_number = sequence_number + 1

702

if node is not None:

703

node.extra = None

703

704

# Clear out the scheduled nodes

704

705

self._scheduled_nodes = []

705

706

return ordered

Older »