« back to all changes in this revision
Viewing changes to bzrlib/_known_graph_pyx.pyx
- browse files at revision 4619
- compare with another revision
- download diff
- download tarball
- view history from revision 4619
- Committer: Canonical.com Patch Queue Manager
- Date: 2009-08-17 18:18:18 UTC
- mfrom: (4618.2.1 integration)
- Revision ID: pqm@pqm.ubuntu.com-20090817181818-6ks7pxgiwpqvsd3l
(vila) Make selftest --parallel=fork work again
- files renamed:
- bzrlib/tests/per_versionedfile.py => bzrlib/tests/test_versionedfile.py
- files modified:
- NEWS
added
removed
bzrlib/_known_graph_pyx.pyx
44
44
45
45
void Py_INCREF(object)
46
46
47
import gc
48
47
49
from bzrlib import errors, revision
48
from bzrlib import revision
50
49
51
50
cdef object NULL_REVISION
52
51
NULL_REVISION = revision.NULL_REVISION
60
59
cdef object children
61
60
cdef public long gdfo
62
61
cdef int seen
63
cdef object extra
64
62
65
63
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
74
73
75
74
property child_keys:
76
75
def __get__(self):
116
115
return <_KnownGraphNode>temp_node
117
116
118
117
119
cdef class _MergeSorter
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.
120
121
121
122
cdef class KnownGraph:
122
123
"""This is a class which assumes we already know the full graph."""
135
136
# Maps {sorted(revision_id, revision_id): heads}
136
137
self._known_heads = {}
137
138
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.
141
139
self._initialize_nodes(parent_map)
142
140
self._find_gdfo()
143
141
185
183
parent_keys = <object>temp_parent_keys
186
184
num_parent_keys = len(parent_keys)
187
185
node = self._get_or_create_node(key)
188
# We know how many parents, so we pre allocate the tuple
186
# We know how many parents, so we could pre allocate an exact sized
187
# tuple here
189
188
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
198
191
parent_node = self._get_or_create_node(parent_keys[pos2])
199
192
# PyTuple_SET_ITEM will steal a reference, so INCREF first
200
193
Py_INCREF(parent_node)
342
335
if self.do_cache:
343
336
PyDict_SetItem(self._known_heads, heads_key, heads)
344
337
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
Loggerhead is a web-based interface for Breezy
Version: 2.0.1