← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: John Arbash Meinel
  • Date: 2008-05-13 22:17:26 UTC
  • mto: This revision was merged to the branch mainline in revision 3443.
  • Revision ID: john@arbash-meinel.com-20080513221726-vqpvwthr1tncpb29
Several updates. A bit more debug logging, only step the all_unique searcher 1/10th of the time.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
 
17
import time
 
18
 
17
19
from bzrlib import (
18
20
    debug,
19
21
    errors,
24
26
    )
25
27
from bzrlib.deprecated_graph import (node_distances, select_farthest)
26
28
 
 
29
STEP_UNIQUE_SEARCHER_EVERY = 10
 
30
 
27
31
# DIAGRAM of terminology
28
32
#       A
29
33
#       /\
260
264
            unique_are_common_nodes.update(
261
265
                next_common_nodes.intersection(unique_searcher.seen))
262
266
            if unique_are_common_nodes:
 
267
                # TODO: This is a bit overboard, we only really care about
 
268
                #       the ancestors of the tips because the rest we
 
269
                #       already know. This is *correct* but causes us to
 
270
                #       search far too much ancestry.
263
271
                ancestors = unique_searcher.find_seen_ancestors(
264
272
                                unique_are_common_nodes)
265
273
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
315
323
                    len(ancestor_all_unique), len(stopped_common))
316
324
            del ancestor_all_unique, stopped_common
317
325
 
 
326
        # We step the ancestor_all_unique searcher only every other step
 
327
        step_all_unique = 0
318
328
        # While we still have common nodes to search
319
329
        while common_searcher._next_query:
320
330
            newly_seen_common = set(common_searcher.step())
338
348
                    unique_are_common_nodes.intersection_update(searcher.seen)
339
349
                unique_are_common_nodes.intersection_update(
340
350
                                            all_unique_searcher.seen)
341
 
                # TODO: lsprof reports this as the most expensive portion of
342
 
                #       this function. Taking 4.4s out of 6.2s spent in
343
 
                #       find_unique_ancestors
344
 
                unique_are_common_nodes.update(all_unique_searcher.step())
 
351
                # Step the all-unique less frequently than the other searchers.
 
352
                # In the common case, we don't need to spider out far here, so
 
353
                # avoid doing extra work.
 
354
                if not step_all_unique:
 
355
                    tstart = time.clock()
 
356
                    nodes = all_unique_searcher.step()
 
357
                    unique_are_common_nodes.update(nodes)
 
358
                    tdelta = time.clock() - tstart
 
359
                    _mutter('all_unique_searcher step() took %.3fs for %d nodes'
 
360
                            ' (%d total), iteration: %s', tdelta, 
 
361
                            len(nodes), len(all_unique_searcher.seen),
 
362
                            all_unique_searcher._iterations)
345
363
            intersect_searchers()
 
364
            step_all_unique = (step_all_unique + 1) % STEP_UNIQUE_SEARCHER_EVERY
346
365
 
347
366
            if newly_seen_common:
348
367
                # If a 'common' node is an ancestor of all unique searchers, we
403
422
                        len(unique_searchers), len(next_unique_searchers),
404
423
                        all_unique_searcher._iterations)
405
424
            unique_searchers = next_unique_searchers
406
 
        return unique_nodes.difference(common_searcher.seen)
 
425
        true_unique_nodes = unique_nodes.difference(common_searcher.seen)
 
426
        _mutter('Found %s truly unique nodes out of %s',
 
427
                len(true_unique_nodes), len(unique_nodes))
 
428
        return true_unique_nodes
407
429
 
408
430
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
409
431
    def get_parents(self, revisions):