Rev 4449: (jam) graph.KnownGraph implementation, in file:///home/pqm/archives/thelove/bzr/%2Btrunk/
Canonical.com Patch Queue Manager
pqm at pqm.ubuntu.com
Tue Jun 16 20:32:50 BST 2009
At file:///home/pqm/archives/thelove/bzr/%2Btrunk/
------------------------------------------------------------
revno: 4449
revision-id: pqm at pqm.ubuntu.com-20090616193232-rorncr6v3z633n9u
parent: pqm at pqm.ubuntu.com-20090616180326-yo7scwj9xk9qa5tp
parent: john at arbash-meinel.com-20090616153514-2croj2d8ych1sk71
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Tue 2009-06-16 20:32:32 +0100
message:
(jam) graph.KnownGraph implementation,
used for optimized heads() lookups during annotate.
added:
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
bzrlib/tests/test__known_graph.py test__known_graph.py-20090610185421-vw8vfda2cgnckgb1-2
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
modified:
.bzrignore bzrignore-20050311232317-81f7b71efa2db11a
NEWS NEWS-20050323055033-4e00b5db738777ff
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/groupcompress.py groupcompress.py-20080705181503-ccbxd6xuy1bdnrpu-8
bzrlib/knit.py knit.py-20051212171256-f056ac8f0fbe1bd9
bzrlib/tests/__init__.py selftest.py-20050531073622-8d0e3c8845c97a64
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
bzrlib/tests/test_knit.py test_knit.py-20051212171302-95d4c00dd5f11f2b
setup.py setup.py-20050314065409-02f8a0a6e3f9bc70
------------------------------------------------------------
revno: 4371.3.48
revision-id: john at arbash-meinel.com-20090616153514-2croj2d8ych1sk71
parent: john at arbash-meinel.com-20090616142731-a385wy2gmp1i0oih
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Tue 2009-06-16 10:35:14 -0500
message:
Clean out some asserts, get rid of the 'dominator_distance' field which isn't used anyway.
modified:
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
bzrlib/tests/test__known_graph.py test__known_graph.py-20090610185421-vw8vfda2cgnckgb1-2
------------------------------------------------------------
revno: 4371.3.47
revision-id: john at arbash-meinel.com-20090616142731-a385wy2gmp1i0oih
parent: john at arbash-meinel.com-20090616141654-thumhpzctylmlyne
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Tue 2009-06-16 09:27:31 -0500
message:
Remove a spurious double declaration.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.46
revision-id: john at arbash-meinel.com-20090616141654-thumhpzctylmlyne
parent: john at arbash-meinel.com-20090616135714-8o7jdtqqsfuv914z
parent: pqm at pqm.ubuntu.com-20090616132232-4s8a3v00nfzh3i8w
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Tue 2009-06-16 09:16:54 -0500
message:
Merge bzr.dev 4447, resolve NEWS
added:
bzrlib/tests/per_repository_reference/test_get_rev_id_for_revno.py test_get_rev_id_for_-20090615064050-b6mq6co557towrxh-1
doc/developers/bug-handling.txt bughandling.txt-20090615072247-mplym00zjq2n4s61-1
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
bzrlib/branch.py branch.py-20050309040759-e4baf4e0d046576e
bzrlib/builtins.py builtins.py-20050830033751-fc01482b9ca23183
bzrlib/chk_serializer.py chk_serializer.py-20081002064345-2tofdfj2eqq01h4b-1
bzrlib/commit.py commit.py-20050511101309-79ec1a0168e0e825
bzrlib/errors.py errors.py-20050309040759-20512168c4e14fbd
bzrlib/remote.py remote.py-20060720103555-yeeg2x51vn0rbtdp-1
bzrlib/repository.py rev_storage.py-20051111201905-119e9401e46257e3
bzrlib/serializer.py serializer.py-20090402143702-wmkh9cfjhwpju0qi-1
bzrlib/smart/repository.py repository.py-20061128022038-vr5wy5bubyb8xttk-1
bzrlib/smart/request.py request.py-20061108095550-gunadhxmzkdjfeek-1
bzrlib/tests/blackbox/test_pull.py test_pull.py-20051201144907-64959364f629947f
bzrlib/tests/blackbox/test_split.py test_split.py-20061008023421-qy0vdpzysh5rriu8-1
bzrlib/tests/branch_implementations/test_dotted_revno_to_revision_id.py test_dotted_revno_to-20090121014844-6x7d9jtri5sspg1o-1
bzrlib/tests/per_repository/test_repository.py test_repository.py-20060131092128-ad07f494f5c9d26c
bzrlib/tests/per_repository_reference/__init__.py __init__.py-20080220025549-nnm2s80it1lvcwnc-2
bzrlib/tests/test_remote.py test_remote.py-20060720103555-yeeg2x51vn0rbtdp-2
bzrlib/tests/test_smart.py test_smart.py-20061122024551-ol0l0o0oofsu9b3t-2
bzrlib/xml4.py xml4.py-20050916091259-db5ab55e7e6ca324
bzrlib/xml8.py xml5.py-20050907032657-aac8f960815b66b1
bzrlib/xml_serializer.py xml.py-20050309040759-57d51586fdec365d
doc/developers/cycle.txt cycle.txt-20081017031739-rw24r0cywm2ok3xu-1
doc/developers/index.txt index.txt-20070508041241-qznziunkg0nffhiw-1
doc/developers/releasing.txt releasing.txt-20080502015919-fnrcav8fwy8ccibu-1
doc/en/developer-guide/HACKING.txt HACKING-20050805200004-2a5dc975d870f78c
------------------------------------------------------------
revno: 4371.3.45
revision-id: john at arbash-meinel.com-20090616135714-8o7jdtqqsfuv914z
parent: john at arbash-meinel.com-20090615171536-ef0rtljwjmrei7on
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Tue 2009-06-16 08:57:14 -0500
message:
The new code removes a get_parent_map call.
modified:
bzrlib/tests/test_knit.py test_knit.py-20051212171302-95d4c00dd5f11f2b
------------------------------------------------------------
revno: 4371.3.44
revision-id: john at arbash-meinel.com-20090615171536-ef0rtljwjmrei7on
parent: john at arbash-meinel.com-20090615170430-bd6ulrllik7xkwpv
parent: pqm at pqm.ubuntu.com-20090615170647-5zu6h93br8c4ue6i
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-15 12:15:36 -0500
message:
Merge bzr.dev 4443, resolve NEWS
added:
bzrlib/help_topics/en/diverged-branches.txt divergedbranches.txt-20090608035534-mb4ry8so4hw238n0-1
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
bzrlib/help_topics/__init__.py help_topics.py-20060920210027-rnim90q9e0bwxvy4-1
bzrlib/push.py push.py-20080606021927-5fe39050e8xne9un-1
bzrlib/tests/blackbox/test_push.py test_push.py-20060329002750-929af230d5d22663
------------------------------------------------------------
revno: 4371.3.43
revision-id: john at arbash-meinel.com-20090615170430-bd6ulrllik7xkwpv
parent: john at arbash-meinel.com-20090615170213-3sgtjlvsr50v9r12
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-15 12:04:30 -0500
message:
NEWS entry.
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
------------------------------------------------------------
revno: 4371.3.42
revision-id: john at arbash-meinel.com-20090615170213-3sgtjlvsr50v9r12
parent: john at arbash-meinel.com-20090615170030-p3am5qp19pstlu9x
parent: pqm at pqm.ubuntu.com-20090615154745-ma7p8rkmyegrzodf
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-15 12:02:13 -0500
message:
Merge bzr.dev 4442, in preparation for NEWS entry.
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
bzr bzr.py-20050313053754-5485f144c7006fa6
bzrlib/__init__.py __init__.py-20050309040759-33e65acf91bbcd5d
bzrlib/_dirstate_helpers_c.pyx dirstate_helpers.pyx-20070503201057-u425eni465q4idwn-3
bzrlib/builtins.py builtins.py-20050830033751-fc01482b9ca23183
bzrlib/bzrdir.py bzrdir.py-20060131065624-156dfea39c4387cb
bzrlib/chk_map.py chk_map.py-20081001014447-ue6kkuhofvdecvxa-1
bzrlib/commands.py bzr.py-20050309040720-d10f4714595cf8c3
bzrlib/dirstate.py dirstate.py-20060728012006-d6mvoihjb3je9peu-1
bzrlib/filters/__init__.py __init__.py-20080416080515-mkxl29amuwrf6uir-2
bzrlib/help.py help.py-20050505025907-4dd7a6d63912f894
bzrlib/help_topics/__init__.py help_topics.py-20060920210027-rnim90q9e0bwxvy4-1
bzrlib/remote.py remote.py-20060720103555-yeeg2x51vn0rbtdp-1
bzrlib/repofmt/groupcompress_repo.py repofmt.py-20080715094215-wp1qfvoo7093c8qr-1
bzrlib/repository.py rev_storage.py-20051111201905-119e9401e46257e3
bzrlib/shellcomplete.py shellcomplete.py-20050822153127-3be115ff5e70fc39
bzrlib/smart/bzrdir.py bzrdir.py-20061122024551-ol0l0o0oofsu9b3t-1
bzrlib/smart/request.py request.py-20061108095550-gunadhxmzkdjfeek-1
bzrlib/tests/blackbox/test_init.py test_init.py-20060309032856-a292116204d86eb7
bzrlib/tests/blackbox/test_pull.py test_pull.py-20051201144907-64959364f629947f
bzrlib/tests/blackbox/test_push.py test_push.py-20060329002750-929af230d5d22663
bzrlib/tests/branch_implementations/test_stacking.py test_stacking.py-20080214020755-msjlkb7urobwly0f-1
bzrlib/tests/bzrdir_implementations/test_bzrdir.py test_bzrdir.py-20060131065642-0ebeca5e30e30866
bzrlib/tests/test_bzrdir.py test_bzrdir.py-20060131065654-deba40eef51cf220
bzrlib/tests/test_chk_map.py test_chk_map.py-20081001014447-ue6kkuhofvdecvxa-2
bzrlib/tests/test_commands.py test_command.py-20051019190109-3b17be0f52eaa7a8
bzrlib/tests/test_eol_filters.py test_eol_filters.py-20090327060429-todzdjmqt3bpv5r8-2
bzrlib/tests/test_filters.py test_filters.py-20080417120614-tc3zok0vvvprsc99-1
bzrlib/tests/test_generate_docs.py test_generate_docs.p-20070102123151-cqctnsrlqwmiljd7-1
bzrlib/tests/test_help.py test_help.py-20070419045354-6q6rq15j9e2n5fna-1
bzrlib/tests/test_options.py testoptions.py-20051014093702-96457cfc86319a8f
bzrlib/tests/test_remote.py test_remote.py-20060720103555-yeeg2x51vn0rbtdp-2
bzrlib/tests/test_smart.py test_smart.py-20061122024551-ol0l0o0oofsu9b3t-2
bzrlib/tests/workingtree_implementations/test_content_filters.py test_content_filters-20080424071441-8navsrmrfdxpn90a-1
bzrlib/tests/workingtree_implementations/test_eol_conversion.py test_eol_conversion.-20090327060429-todzdjmqt3bpv5r8-4
bzrlib/workingtree.py workingtree.py-20050511021032-29b6ec0a681e02e3
bzrlib/workingtree_4.py workingtree_4.py-20070208044105-5fgpc5j3ljlh5q6c-1
doc/developers/releasing.txt releasing.txt-20080502015919-fnrcav8fwy8ccibu-1
doc/en/quick-reference/quick-start-summary.png quickstartsummary.pn-20071203142852-hsiybkmh37q5owwe-1
doc/en/user-guide/images/workflows_centralized.png workflows_centralize-20071114035000-q36a9h57ps06uvnl-8
doc/en/user-guide/images/workflows_gatekeeper.png workflows_gatekeeper-20071114035000-q36a9h57ps06uvnl-9
doc/en/user-guide/images/workflows_localcommit.png workflows_localcommi-20071114035000-q36a9h57ps06uvnl-10
doc/en/user-guide/images/workflows_peer.png workflows_peer.png-20071114035000-q36a9h57ps06uvnl-11
doc/en/user-guide/images/workflows_pqm.png workflows_pqm.png-20071114035000-q36a9h57ps06uvnl-12
doc/en/user-guide/images/workflows_shared.png workflows_shared.png-20071114035000-q36a9h57ps06uvnl-13
doc/en/user-guide/images/workflows_single.png workflows_single.png-20071114035000-q36a9h57ps06uvnl-14
generate_docs.py bzrinfogen.py-20051211224525-78e7c14f2c955e55
setup.py setup.py-20050314065409-02f8a0a6e3f9bc70
------------------------------------------------------------
revno: 4371.3.41
revision-id: john at arbash-meinel.com-20090615170030-p3am5qp19pstlu9x
parent: john at arbash-meinel.com-20090612202108-blsyks1kdxod0lsk
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-15 12:00:30 -0500
message:
Add a bit of discussion about why we would want to use linear dominators.
modified:
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.40
revision-id: john at arbash-meinel.com-20090612202108-blsyks1kdxod0lsk
parent: john at arbash-meinel.com-20090612193730-jwaocmo8a9m4t1jz
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Fri 2009-06-12 15:21:08 -0500
message:
Fixes for linear_nodes in the pyrex version.
Doesn't seem to specifically impact performance.
modified:
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.39
revision-id: john at arbash-meinel.com-20090612193730-jwaocmo8a9m4t1jz
parent: john at arbash-meinel.com-20090612180515-t0cwbjsnve094oik
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Fri 2009-06-12 14:37:30 -0500
message:
Implement the fix for the python version.
The idea is that if while walking we run into a node or its dominator
then we obviously supersede that node.
The other bit to be aware of, is that we shouldn't negate a node when
we walk to its own dominator.
modified:
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
bzrlib/tests/test__known_graph.py test__known_graph.py-20090610185421-vw8vfda2cgnckgb1-2
------------------------------------------------------------
revno: 4371.3.38
revision-id: john at arbash-meinel.com-20090612180515-t0cwbjsnve094oik
parent: john at arbash-meinel.com-20090612044424-3kv1qr5wkns35c22
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Fri 2009-06-12 13:05:15 -0500
message:
Add a failing test for handling nodes that are in the same linear chain.
It fails because the ancestry skipping causes us to miss the fact that the two nodes
are actually directly related. We could check at the beginning, as the
code used to do, but I think that will be incomplete for the more-than-two
heads cases.
added:
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test__known_graph.py test__known_graph.py-20090610185421-vw8vfda2cgnckgb1-2
------------------------------------------------------------
revno: 4371.3.37
revision-id: john at arbash-meinel.com-20090612044424-3kv1qr5wkns35c22
parent: john at arbash-meinel.com-20090612041307-jk38nrysmr78f5d0
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 23:44:24 -0500
message:
cleanup passes.
Write some helper functions that avoid having to retype the ugly
inline code everywhere.
Get rid of the special-case exit when popping candidate nodes.
At best it just avoids adding a couple parents to the heap before
we hit the while loop and notice we are done anyway. And it allows
us to remove some extraneous if/break blocks and clean up the code
a bit.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.36
revision-id: john at arbash-meinel.com-20090612041307-jk38nrysmr78f5d0
parent: john at arbash-meinel.com-20090612041001-qqauzvhsb5z333gz
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 23:13:07 -0500
message:
Cache heads() results from dominator lookups.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.35
revision-id: john at arbash-meinel.com-20090612041001-qqauzvhsb5z333gz
parent: john at arbash-meinel.com-20090612033417-cg8dj74mkbuth2ob
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 23:10:01 -0500
message:
Changing the heapq algorithm actually ends up with better overall performance.
First, use the same 'replace instead of pop+push' trick.
Second, fix a small issue when gdfo ordering lets us number further than I thought we could.
Clarify some code paths, which even makes it a little bit faster.
(currently at 68.3ms for bzr.dev, 771ms for OOo)
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.34
revision-id: john at arbash-meinel.com-20090612033417-cg8dj74mkbuth2ob
parent: john at arbash-meinel.com-20090612031025-m3hbl28qub56doga
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 22:34:17 -0500
message:
Changing the code to allow a special case for not always popping the
last item, and instead re-using that slot for the next item.
It resolves the issue with OOo (w/ OOo being so linear, my guess is 90% of it is
numbered with a single entry in the list, which probably caused cycles of
deallocating the buffer, and reallocating it on every node.)
Not sure if it worth the ugliness, though. Certainly the code is more prone to
mistakes now.
I'll probably go back to the heapq version. Approximately as fast, and much more
elegant.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.33
revision-id: john at arbash-meinel.com-20090612031025-m3hbl28qub56doga
parent: john at arbash-meinel.com-20090611221804-xbsmslillnb6tldf
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 22:10:25 -0500
message:
Use a hybrid pass to walk all nodes.
This avoids a heapq, which we didn't really need anyway.
It is ~ the same number of passes, only we trade off a simplistic
'find_tails' call, with doing more work on the 1-pass over the dict.
It seems to be slightly faster for bzr, and slightly slower for OOo.
Not particularly noticeable in the noise of heads(), but measurable for
__init__ performance.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.32
revision-id: john at arbash-meinel.com-20090611221804-xbsmslillnb6tldf
parent: john at arbash-meinel.com-20090611210918-mk52ural4dbxteax
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 17:18:04 -0500
message:
A comment about rewriting _find_gdfo
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.31
revision-id: john at arbash-meinel.com-20090611210918-mk52ural4dbxteax
parent: john at arbash-meinel.com-20090611203456-g3z9360rdd00tjs3
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 16:09:18 -0500
message:
Change _KnownGraph.parents to be a tuple rather than a list.
We know the size as soon as we walk to a map entry.
This way, we save a malloc, and have slightly smaller objects. Not a huge
difference, but a small one.
This changes KnownGraph(OOo_parent_map) time from 922ms down to 848ms, or
about a 10% savings for __init__ time.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.30
revision-id: john at arbash-meinel.com-20090611203456-g3z9360rdd00tjs3
parent: john at arbash-meinel.com-20090611200247-zvx587wf8qyr2rg1
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 15:34:56 -0500
message:
Clean up the annotate code while using the new functionality.
modified:
bzrlib/groupcompress.py groupcompress.py-20080705181503-ccbxd6xuy1bdnrpu-8
bzrlib/knit.py knit.py-20051212171256-f056ac8f0fbe1bd9
------------------------------------------------------------
revno: 4371.3.29
revision-id: john at arbash-meinel.com-20090611200247-zvx587wf8qyr2rg1
parent: john at arbash-meinel.com-20090611192457-709bcvurmy02itd3
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 15:02:47 -0500
message:
A couple quick cleanups
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.28
revision-id: john at arbash-meinel.com-20090611192457-709bcvurmy02itd3
parent: john at arbash-meinel.com-20090611164732-yqh4dyu0i4kwtecj
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 14:24:57 -0500
message:
Finish converting away from 'cdef list' syntax.
Also, I found that casting a PyObject * directly to _KnownGraphNode avoids
the TypeTest. Since PyDict_GetItem and PyList_GET_ITEM return borrowed
references anyway, we need a cast (to auto-incref the pointer), so
we may as well use them for speed, and avoid the type check at the same
time.
Also using PyDict_Next everywhere instead of 'for x in dict.iterX'.
The nice thing about PyDict_Next is that it always gives you items, but you
can chose what you actually care about.
Also, by doing all these manipulations directly, we shave some more time out
of building a KnownGraph and out of the heads() calls.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.27
revision-id: john at arbash-meinel.com-20090611164732-yqh4dyu0i4kwtecj
parent: john at arbash-meinel.com-20090611164617-ojhy89zgig81yuez
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 11:47:32 -0500
message:
Remove some += and unused code anyway.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.26
revision-id: john at arbash-meinel.com-20090611164617-ojhy89zgig81yuez
parent: john at arbash-meinel.com-20090611162226-0r7sa3k0wbe0hfy9
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 11:46:17 -0500
message:
A few more cleanups. Start moving away from pyrex 0.9.8isms
modified:
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.25
revision-id: john at arbash-meinel.com-20090611162226-0r7sa3k0wbe0hfy9
parent: john at arbash-meinel.com-20090611042857-d9ug6gtlo867ibn2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Thu 2009-06-11 11:22:26 -0500
message:
Remove the time_graph.py tool, it has served its purpose.
removed:
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
------------------------------------------------------------
revno: 4371.3.24
revision-id: john at arbash-meinel.com-20090611042857-d9ug6gtlo867ibn2
parent: john at arbash-meinel.com-20090610221322-uv24p5wlgtic7j13
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Wed 2009-06-10 23:28:57 -0500
message:
A couple of cleanups.
left_parent/right_parent didn't show a real-world win, so they have been removed.
The code is quite a bit clearer without them.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
------------------------------------------------------------
revno: 4371.3.23
revision-id: john at arbash-meinel.com-20090610221322-uv24p5wlgtic7j13
parent: john at arbash-meinel.com-20090610220839-wmp8pe3qqra3weq6
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Wed 2009-06-10 17:13:22 -0500
message:
Using PySet_Add in the inner loop is a little better, not tremendously, though
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.22
revision-id: john at arbash-meinel.com-20090610220839-wmp8pe3qqra3weq6
parent: john at arbash-meinel.com-20090610220339-akbmevv1b0236upf
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Wed 2009-06-10 17:08:39 -0500
message:
The slowdown was that _to_cleanup wasn't getting reset.
The other slow part of the pyrex code was that we weren't properly skipping
to linear_dominator. Now .pyx is 2x faster than .py.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.21
revision-id: john at arbash-meinel.com-20090610220339-akbmevv1b0236upf
parent: john at arbash-meinel.com-20090610210222-trfxgzd242tl04nl
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Wed 2009-06-10 17:03:39 -0500
message:
Attempt to make things better by splitting out left_parent and right_parent into
individual attributes (to avoid extra type checks, etc.)
However, this seems to make things *much* worse rather than better.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.20
revision-id: john at arbash-meinel.com-20090610210222-trfxgzd242tl04nl
parent: john at arbash-meinel.com-20090610195616-alggpr46n0bmjjhf
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Wed 2009-06-10 16:02:22 -0500
message:
A few tweaks to the pyrex version.
It is now 'as fast' as the python one for heads() checks on bzr ancestry.
It is about 2s faster for heads() checks for annotating NEWS.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.3.19
revision-id: john at arbash-meinel.com-20090610195616-alggpr46n0bmjjhf
parent: john at arbash-meinel.com-20090610185802-wsybzjfil447yhy2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Wed 2009-06-10 14:56:16 -0500
message:
Get an initial pyrex implementation.
Initial results show it to actually be slightly slower than pure python.
added:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
modified:
.bzrignore bzrignore-20050311232317-81f7b71efa2db11a
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
setup.py setup.py-20050314065409-02f8a0a6e3f9bc70
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
------------------------------------------------------------
revno: 4371.3.18
revision-id: john at arbash-meinel.com-20090610185802-wsybzjfil447yhy2
parent: john at arbash-meinel.com-20090610164116-q2rbbja0szmexsry
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Wed 2009-06-10 13:58:02 -0500
message:
Change VF.annotate to use the new KnownGraph code.
This shows a significant savings in the time for 'annotate NEWS', of about 5s/20s
for knit formats, and 45s => 20s for GC formats.
Also, factor the code into a helper, so that we can prepare for writing
a pyrex version.
added:
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
bzrlib/tests/test__known_graph.py test__known_graph.py-20090610185421-vw8vfda2cgnckgb1-2
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/groupcompress.py groupcompress.py-20080705181503-ccbxd6xuy1bdnrpu-8
bzrlib/knit.py knit.py-20051212171256-f056ac8f0fbe1bd9
bzrlib/tests/__init__.py selftest.py-20050531073622-8d0e3c8845c97a64
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 4371.3.17
revision-id: john at arbash-meinel.com-20090610164116-q2rbbja0szmexsry
parent: john at arbash-meinel.com-20090610163143-unn2fkyrcuwtkf62
parent: pqm at pqm.ubuntu.com-20090610103331-ht76b0l92gj1gn9d
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Wed 2009-06-10 11:41:16 -0500
message:
merge bzr.dev 4427, mostly to get the better GC.annotate code.
removed:
bzrlib/util/tests/test_bencode.py test_bencode.py-20070713042202-qjw8rppxaz7ky6i6-1
doc/developers/performance-contributing.txt performancecontribut-20070621063612-ac4zhhagjzkr21qp-1
added:
bzrlib/_bencode_pyx.h _bencode_pyx.h-20090604155331-53bg7d0udmrvz44n-1
bzrlib/_bencode_pyx.pyx bencode.pyx-20070806220735-j75g4ebfnado2i60-3
bzrlib/benchmarks/bench_tags.py bench_tags.py-20070812104202-0q5i0mqkt72hubof-1
bzrlib/bencode.py bencode.py-20070806220735-j75g4ebfnado2i60-2
bzrlib/send.py send.py-20090521192735-j7cdb33ykmtmzx4w-1
bzrlib/tests/per_repository_reference/test_fetch.py test_fetch.py-20090511214909-25pkgmoam913lrji-1
bzrlib/tests/per_repository_reference/test_initialize.py test_initialize.py-20090527083941-4rz2urcthjet5e2i-1
bzrlib/tests/per_repository_reference/test_unlock.py test_unlock.py-20090526160031-14lvypj5pbrndnyz-1
bzrlib/tests/test_bencode.py test_bencode.py-20070806225234-s51cnnkh6raytxti-1
bzrlib/tests/test_chk_serializer.py test_chk_serializer.-20090515105921-urte9wnhknlj5dyp-1
bzrlib/util/bencode.py bencode.py-20090609141817-jtvhqq6vyryjoeky-1
doc/index.ru.txt index.ru.txt-20080819091426-kfq61l02dhm9pplk-1
doc/ru/ ru-20080818031309-t3nyctvfbvfh4h2u-1
doc/ru/mini-tutorial/ minitutorial-20080818031309-t3nyctvfbvfh4h2u-2
doc/ru/mini-tutorial/index.txt index.txt-20080818031309-t3nyctvfbvfh4h2u-4
doc/ru/quick-reference/ quickreference-20080818031309-t3nyctvfbvfh4h2u-3
doc/ru/quick-reference/Makefile makefile-20080818031309-t3nyctvfbvfh4h2u-5
doc/ru/quick-reference/quick-start-summary.pdf quickstartsummary.pd-20080818031309-t3nyctvfbvfh4h2u-6
doc/ru/quick-reference/quick-start-summary.png quickstartsummary.pn-20080818031309-t3nyctvfbvfh4h2u-7
doc/ru/quick-reference/quick-start-summary.svg quickstartsummary.sv-20080818031309-t3nyctvfbvfh4h2u-8
doc/ru/tutorials/ docrututorials-20090427084615-toum0jo7qohd807p-1
doc/ru/tutorials/centralized_workflow.txt centralized_workflow-20090531190825-ex3ums4bcuaf2r6k-1
doc/ru/tutorials/tutorial.txt tutorial.txt-20090602180629-wkp7wr27jl4i2zep-1
doc/ru/tutorials/using_bazaar_with_launchpad.txt using_bazaar_with_la-20090427084917-b22ppqtdx7q4hapw-1
doc/ru/user-guide/ docruuserguide-20090601191403-rcoy6nsre0vjiozm-1
doc/ru/user-guide/branching_a_project.txt branching_a_project.-20090602104644-pjpwfx7xh2k5l0ba-1
doc/ru/user-guide/core_concepts.txt core_concepts.txt-20090602104644-pjpwfx7xh2k5l0ba-2
doc/ru/user-guide/images/ images-20090601201124-cruf3mmq5cfxeb1w-1
doc/ru/user-guide/images/workflows_centralized.png workflows_centralize-20090601201124-cruf3mmq5cfxeb1w-3
doc/ru/user-guide/images/workflows_centralized.svg workflows_centralize-20090601201124-cruf3mmq5cfxeb1w-4
doc/ru/user-guide/images/workflows_gatekeeper.png workflows_gatekeeper-20090601201124-cruf3mmq5cfxeb1w-5
doc/ru/user-guide/images/workflows_gatekeeper.svg workflows_gatekeeper-20090601201124-cruf3mmq5cfxeb1w-6
doc/ru/user-guide/images/workflows_localcommit.png workflows_localcommi-20090601201124-cruf3mmq5cfxeb1w-7
doc/ru/user-guide/images/workflows_localcommit.svg workflows_localcommi-20090601201124-cruf3mmq5cfxeb1w-8
doc/ru/user-guide/images/workflows_peer.png workflows_peer.png-20090601201124-cruf3mmq5cfxeb1w-9
doc/ru/user-guide/images/workflows_peer.svg workflows_peer.svg-20090601201124-cruf3mmq5cfxeb1w-10
doc/ru/user-guide/images/workflows_pqm.png workflows_pqm.png-20090601201124-cruf3mmq5cfxeb1w-11
doc/ru/user-guide/images/workflows_pqm.svg workflows_pqm.svg-20090601201124-cruf3mmq5cfxeb1w-12
doc/ru/user-guide/images/workflows_shared.png workflows_shared.png-20090601201124-cruf3mmq5cfxeb1w-13
doc/ru/user-guide/images/workflows_shared.svg workflows_shared.svg-20090601201124-cruf3mmq5cfxeb1w-14
doc/ru/user-guide/images/workflows_single.png workflows_single.png-20090601201124-cruf3mmq5cfxeb1w-15
doc/ru/user-guide/images/workflows_single.svg workflows_single.svg-20090601201124-cruf3mmq5cfxeb1w-16
doc/ru/user-guide/index.txt index.txt-20090601201124-cruf3mmq5cfxeb1w-2
doc/ru/user-guide/introducing_bazaar.txt introducing_bazaar.t-20090601221109-6ehwbt2pvzgpftlu-1
doc/ru/user-guide/specifying_revisions.txt specifying_revisions-20090602104644-pjpwfx7xh2k5l0ba-3
doc/ru/user-guide/stacked.txt stacked.txt-20090602104644-pjpwfx7xh2k5l0ba-4
doc/ru/user-guide/using_checkouts.txt using_checkouts.txt-20090602104644-pjpwfx7xh2k5l0ba-5
doc/ru/user-guide/zen.txt zen.txt-20090602104644-pjpwfx7xh2k5l0ba-6
renamed:
bzrlib/tests/workingtree_implementations/test_get_file_with_stat.py => bzrlib/tests/tree_implementations/test_get_file_with_stat.py test_get_file_with_s-20080922035909-lhdovrr36jpxmu0v-1
bzrlib/util/bencode.py => bzrlib/util/_bencode_py.py bencode.py-20070220044742-sltr28q21w2wzlxi-1
modified:
.bzrignore bzrignore-20050311232317-81f7b71efa2db11a
Makefile Makefile-20050805140406-d96e3498bb61c5bb
NEWS NEWS-20050323055033-4e00b5db738777ff
bzrlib/__init__.py __init__.py-20050309040759-33e65acf91bbcd5d
bzrlib/_groupcompress_pyx.pyx _groupcompress_c.pyx-20080724041824-yelg6ii7c7zxt4z0-1
bzrlib/benchmarks/__init__.py __init__.py-20060516064526-eb0d37c78e86065d
bzrlib/branch.py branch.py-20050309040759-e4baf4e0d046576e
bzrlib/builtins.py builtins.py-20050830033751-fc01482b9ca23183
bzrlib/bundle/serializer/v4.py v10.py-20070611062757-5ggj7k18s9dej0fr-1
bzrlib/bzrdir.py bzrdir.py-20060131065624-156dfea39c4387cb
bzrlib/cache_utf8.py cache_utf8.py-20060810004311-x4cph46la06h9azm-1
bzrlib/chk_serializer.py chk_serializer.py-20081002064345-2tofdfj2eqq01h4b-1
bzrlib/diff.py diff.py-20050309040759-26944fbbf2ebbf36
bzrlib/foreign.py foreign.py-20081112170002-olsxmandkk8qyfuq-1
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/groupcompress.py groupcompress.py-20080705181503-ccbxd6xuy1bdnrpu-8
bzrlib/index.py index.py-20070712131115-lolkarso50vjr64s-1
bzrlib/inventory.py inventory.py-20050309040759-6648b84ca2005b37
bzrlib/knit.py knit.py-20051212171256-f056ac8f0fbe1bd9
bzrlib/lock.py lock.py-20050527050856-ec090bb51bc03349
bzrlib/log.py log.py-20050505065812-c40ce11702fe5fb1
bzrlib/mail_client.py mail_client.py-20070809192806-vuxt3t19srtpjpdn-1
bzrlib/multiparent.py __init__.py-20070410133617-n1jdhcc1n1mibarp-1
bzrlib/mutabletree.py mutabletree.py-20060906023413-4wlkalbdpsxi2r4y-2
bzrlib/osutils.py osutils.py-20050309040759-eeaff12fbf77ac86
bzrlib/plugins/launchpad/test_register.py test_register.py-20060315182712-40f5dda945c829a8
bzrlib/progress.py progress.py-20050610070202-df9faaab791964c0
bzrlib/python-compat.h pythoncompat.h-20080924041409-9kvi0fgtuuqp743j-1
bzrlib/reconcile.py reweave_inventory.py-20051108164726-1e5e0934febac06e
bzrlib/remote.py remote.py-20060720103555-yeeg2x51vn0rbtdp-1
bzrlib/repofmt/groupcompress_repo.py repofmt.py-20080715094215-wp1qfvoo7093c8qr-1
bzrlib/repofmt/knitrepo.py knitrepo.py-20070206081537-pyy4a00xdas0j4pf-1
bzrlib/repofmt/pack_repo.py pack_repo.py-20070813041115-gjv5ma7ktfqwsjgn-1
bzrlib/repository.py rev_storage.py-20051111201905-119e9401e46257e3
bzrlib/revisiontree.py revisiontree.py-20060724012533-bg8xyryhxd0o0i0h-1
bzrlib/serializer.py serializer.py-20090402143702-wmkh9cfjhwpju0qi-1
bzrlib/shelf.py prepare_shelf.py-20081005181341-n74qe6gu1e65ad4v-1
bzrlib/smart/medium.py medium.py-20061103051856-rgu2huy59fkz902q-1
bzrlib/smart/protocol.py protocol.py-20061108035435-ot0lstk2590yqhzr-1
bzrlib/smart/repository.py repository.py-20061128022038-vr5wy5bubyb8xttk-1
bzrlib/smart/server.py server.py-20061110062051-chzu10y32vx8gvur-1
bzrlib/tag.py tag.py-20070212110532-91cw79inah2cfozx-1
bzrlib/tests/__init__.py selftest.py-20050531073622-8d0e3c8845c97a64
bzrlib/tests/blackbox/test_add.py test_add.py-20060518072250-857e4f86f54a30b2
bzrlib/tests/blackbox/test_branch.py test_branch.py-20060524161337-noms9gmcwqqrfi8y-1
bzrlib/tests/blackbox/test_dpush.py test_dpush.py-20090108125928-st1td6le59g0vyv2-1
bzrlib/tests/blackbox/test_export.py test_export.py-20051229024010-e6c26658e460fb1c
bzrlib/tests/blackbox/test_log.py test_log.py-20060112090212-78f6ea560c868e24
bzrlib/tests/blackbox/test_push.py test_push.py-20060329002750-929af230d5d22663
bzrlib/tests/blackbox/test_send.py test_bundle.py-20060616222707-c21c8b7ea5ef57b1
bzrlib/tests/blackbox/test_serve.py test_serve.py-20060913064329-8t2pvmsikl4s3xhl-1
bzrlib/tests/blackbox/test_status.py teststatus.py-20050712014354-508855eb9f29f7dc
bzrlib/tests/branch_implementations/test_branch.py testbranch.py-20050711070244-121d632bc37d7253
bzrlib/tests/branch_implementations/test_check.py test_check.py-20080429151303-1sbfclxhddpz0tnj-1
bzrlib/tests/branch_implementations/test_push.py test_push.py-20070130153159-fhfap8uoifevg30j-1
bzrlib/tests/branch_implementations/test_reconcile.py test_reconcile.py-20080429161555-qlmccuyeyt6pvho7-1
bzrlib/tests/branch_implementations/test_sprout.py test_sprout.py-20070521151739-b8t8p7axw1h966ws-1
bzrlib/tests/inventory_implementations/basics.py basics.py-20070903044446-kdjwbiu1p1zi9phs-1
bzrlib/tests/per_repository/test_fetch.py test_fetch.py-20070814052151-5cxha9slx4c93uog-1
bzrlib/tests/per_repository/test_fileid_involved.py test_file_involved.py-20051215205901-728a172d1014daaa
bzrlib/tests/per_repository/test_iter_reverse_revision_history.py test_iter_reverse_re-20070217015036-spu7j5ggch7pbpyd-1
bzrlib/tests/per_repository/test_reconcile.py test_reconcile.py-20060223022332-572ef70a3288e369
bzrlib/tests/per_repository/test_revision.py testrevprops.py-20051013073044-92bc3c68302ce1bf
bzrlib/tests/per_repository/test_write_group.py test_write_group.py-20070716105516-89n34xtogq5frn0m-1
bzrlib/tests/per_repository_reference/__init__.py __init__.py-20080220025549-nnm2s80it1lvcwnc-2
bzrlib/tests/per_repository_reference/test_default_stacking.py test_default_stackin-20090311055345-9ajahgm58oq3wh6h-1
bzrlib/tests/test__groupcompress.py test__groupcompress_-20080724145854-koifwb7749cfzrvj-1
bzrlib/tests/test_config.py testconfig.py-20051011041908-742d0c15d8d8c8eb
bzrlib/tests/test_foreign.py test_foreign.py-20081125004048-ywb901edgp9lluxo-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
bzrlib/tests/test_groupcompress.py test_groupcompress.p-20080705181503-ccbxd6xuy1bdnrpu-13
bzrlib/tests/test_http.py testhttp.py-20051018020158-b2eef6e867c514d9
bzrlib/tests/test_mail_client.py test_mail_client.py-20070809192806-vuxt3t19srtpjpdn-2
bzrlib/tests/test_osutils.py test_osutils.py-20051201224856-e48ee24c12182989
bzrlib/tests/test_pack_repository.py test_pack_repository-20080801043947-eaw0e6h2gu75kwmy-1
bzrlib/tests/test_plugins.py plugins.py-20050622075746-32002b55e5e943e9
bzrlib/tests/test_progress.py test_progress.py-20060308160359-978c397bc79b7fda
bzrlib/tests/test_remote.py test_remote.py-20060720103555-yeeg2x51vn0rbtdp-2
bzrlib/tests/test_repository.py test_repository.py-20060131075918-65c555b881612f4d
bzrlib/tests/test_serializer.py test_serializer.py-20090403213933-q6x117y8t9fbeyoz-1
bzrlib/tests/test_smart.py test_smart.py-20061122024551-ol0l0o0oofsu9b3t-2
bzrlib/tests/test_source.py test_source.py-20051207061333-a58dea6abecc030d
bzrlib/tests/test_transform.py test_transaction.py-20060105172520-b3ffb3946550e6c4
bzrlib/tests/test_ui.py test_ui.py-20051130162854-458e667a7414af09
bzrlib/tests/tree_implementations/__init__.py __init__.py-20060717075546-420s7b0bj9hzeowi-2
bzrlib/tests/workingtree_implementations/__init__.py __init__.py-20060203003124-b2aa5aca21a8bfad
bzrlib/transform.py transform.py-20060105172343-dd99e54394d91687
bzrlib/transport/__init__.py transport.py-20050711165921-4978aa7ce1285ad5
bzrlib/transport/sftp.py sftp.py-20051019050329-ab48ce71b7e32dfe
bzrlib/tree.py tree.py-20050309040759-9d5f2496be663e77
bzrlib/ui/__init__.py ui.py-20050824083933-8cf663c763ba53a9
bzrlib/versionedfile.py versionedfile.py-20060222045106-5039c71ee3b65490
bzrlib/weave.py knit.py-20050627021749-759c29984154256b
bzrlib/win32utils.py win32console.py-20051021033308-123c6c929d04973d
bzrlib/workingtree.py workingtree.py-20050511021032-29b6ec0a681e02e3
bzrlib/workingtree_4.py workingtree_4.py-20070208044105-5fgpc5j3ljlh5q6c-1
doc/developers/performance-roadmap.txt performanceroadmap.t-20070507174912-mwv3xv517cs4sisd-2
doc/developers/planned-change-integration.txt plannedchangeintegra-20070619004702-i1b3ccamjtfaoq6w-1
doc/en/developer-guide/HACKING.txt HACKING-20050805200004-2a5dc975d870f78c
doc/en/quick-reference/Makefile makefile-20070813143223-5i7bgw7w8s7l3ae2-2
doc/en/tutorials/using_bazaar_with_launchpad.txt using_bazaar_with_lp-20071211073140-7msh8uf9a9h4y9hb-1
doc/en/user-guide/introducing_bazaar.txt introducing_bazaar.t-20071114035000-q36a9h57ps06uvnl-5
doc/en/user-guide/svn_plugin.txt svn_plugin.txt-20080509065016-cjc90f46407vi9a0-2
doc/index.txt index.txt-20070813101924-07gd9i9d2jt124bf-1
setup.py setup.py-20050314065409-02f8a0a6e3f9bc70
bzrlib/tests/tree_implementations/test_get_file_with_stat.py test_get_file_with_s-20080922035909-lhdovrr36jpxmu0v-1
bzrlib/util/_bencode_py.py bencode.py-20070220044742-sltr28q21w2wzlxi-1
------------------------------------------------------------
revno: 4371.3.16
revision-id: john at arbash-meinel.com-20090610163143-unn2fkyrcuwtkf62
parent: john at arbash-meinel.com-20090609003046-kg75mbqk000u0475
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Wed 2009-06-10 11:31:43 -0500
message:
Adding some debugging counters shows that
1) Without linear_dominator we are still a little faster. 0.68:1
2) Without linear_dominator we access 86% of the entries that Graph does
3) With linear_dominator we are *much* faster 0.46:1, and access 57% of
the same keys.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
------------------------------------------------------------
revno: 4371.3.15
revision-id: john at arbash-meinel.com-20090609003046-kg75mbqk000u0475
parent: john at arbash-meinel.com-20090608220434-mlcwz86kl038jkac
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-08 19:30:46 -0500
message:
Allow --max-combinations=0 to run everything.
modified:
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
------------------------------------------------------------
revno: 4371.3.14
revision-id: john at arbash-meinel.com-20090608220434-mlcwz86kl038jkac
parent: john at arbash-meinel.com-20090608220358-7ljjh8zvdch9cxbd
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-08 17:04:34 -0500
message:
Removing the _counters tracking helps, too.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
------------------------------------------------------------
revno: 4371.3.13
revision-id: john at arbash-meinel.com-20090608220358-7ljjh8zvdch9cxbd
parent: john at arbash-meinel.com-20090608220045-4ldppuufcutyt701
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-08 17:03:58 -0500
message:
Since we are skipping, we should set node.linear_dominator to full-width as well.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
------------------------------------------------------------
revno: 4371.3.12
revision-id: john at arbash-meinel.com-20090608220045-4ldppuufcutyt701
parent: john at arbash-meinel.com-20090608215942-um18hyyt3uo934s1
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-08 17:00:45 -0500
message:
a bit of cleanup
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
------------------------------------------------------------
revno: 4371.3.11
revision-id: john at arbash-meinel.com-20090608215942-um18hyyt3uo934s1
parent: john at arbash-meinel.com-20090608215625-dnc3fzepsc2d4nkj
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-08 16:59:42 -0500
message:
Removing the inner function calls also helps a bit.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
------------------------------------------------------------
revno: 4371.3.10
revision-id: john at arbash-meinel.com-20090608215625-dnc3fzepsc2d4nkj
parent: john at arbash-meinel.com-20090608214233-q81n5f3hc3jotnia
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-08 16:56:25 -0500
message:
Avoiding set operations when the ancestor_of field is the same helps quite a bit.
Now down to 0.65:1
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
------------------------------------------------------------
revno: 4371.3.9
revision-id: john at arbash-meinel.com-20090608214233-q81n5f3hc3jotnia
parent: john at arbash-meinel.com-20090608210315-my1czgs64q2yywyd
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-08 16:42:33 -0500
message:
Add 'ratio' to the timing script, as it makes it more obvious when something is faster.
Also add a limit to number of combinations, to make testing easier.
Add testing to ensure that the result of KnownGraph.heads() is correct.
Initial results showed the new gdfo code being quite a bit slower.
Adding in the 'linear_dominator' skipping seems to speed things up dramatically.
Probably we aren't wasting as much time in long linear regions.
Still seems to give correct results, which is nice to see.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
------------------------------------------------------------
revno: 4371.3.8
revision-id: john at arbash-meinel.com-20090608210315-my1czgs64q2yywyd
parent: john at arbash-meinel.com-20090608201222-gzehwzf2q98gmk0d
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-08 16:03:15 -0500
message:
Add the time_graph code for benchmarking.
Add a lot of debugging counters, etc.
At the moment, 'random sampling' shows a performance improvement of 4:1
however, just checking 'parents of a merge' in bzr.dev shows a
performance *loss* of about 1:2. So still need to do a bit more
probing to figure out why. It may be the overhead of using objects,
or it may be an issue of the algorithm.
added:
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
------------------------------------------------------------
revno: 4371.3.7
revision-id: john at arbash-meinel.com-20090608201222-gzehwzf2q98gmk0d
parent: john at arbash-meinel.com-20090608193114-mzex30467ukbk0dj
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-08 15:12:22 -0500
message:
Implement _heads_from_candidate_keys using a gdfo algorithm.
It seems to pass all test cases. Best guess is that gdfo solves the earlier
problem of 'shortcuts' causing invalid results.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 4371.3.6
revision-id: john at arbash-meinel.com-20090608193114-mzex30467ukbk0dj
parent: john at arbash-meinel.com-20090519141938-0xsw7i2nxxjwrzzs
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-08 14:31:14 -0500
message:
Remove the debug timing for _find_gdfo
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
------------------------------------------------------------
revno: 4371.3.5
revision-id: john at arbash-meinel.com-20090519141938-0xsw7i2nxxjwrzzs
parent: john at arbash-meinel.com-20090519062218-u44qbf6koyz2w4c6
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Tue 2009-05-19 09:19:38 -0500
message:
Change the algorithm as suggested by vila.
Only walk a child node once you have seen all parent nodes.
This is a *huge* increase in performance, as it eliminates
the double walking problem. Doing all of bzr.dev drops from
3m55s down to 1.88s. Without any micro ops.
Still need to verify that the result is correct, but all
the gdfo tests pass, so it seems to be.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
------------------------------------------------------------
revno: 4371.3.4
revision-id: john at arbash-meinel.com-20090519062218-u44qbf6koyz2w4c6
parent: john at arbash-meinel.com-20090519060202-f3d0gcqd4jphfxf9
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Tue 2009-05-19 01:22:18 -0500
message:
The initial results for _find_gdfo on bzr's ancestry:
with 25k revisions, it takes 40.8M steps, a peak todo of 10.6k and 9.7M
nodes skipped. Overall, taking 3m55s, which is pretty unusable.
Only 25% of the evaluations are 'wasted' (where we see a node from a longer
path before we evaluate the node where we thought we should).
My guess is that we get lots of 'small waves', where we number a bunch of
revisions based on path A, then find out it is reachable from path B, and
renumber all of those revisions.
Perhaps walking from the largest rather than the smallest would be advantageous,
though I have the feeling it just means we get 'long walks', where we
walk from the new longest path to the tips of everything underneath it.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
------------------------------------------------------------
revno: 4371.3.3
revision-id: john at arbash-meinel.com-20090519060202-f3d0gcqd4jphfxf9
parent: john at arbash-meinel.com-20090518201009-y0o2xad5etcbo6f2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Tue 2009-05-19 01:02:02 -0500
message:
Implement a Global Distance From Origin computation, using a heapq.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 4371.3.2
revision-id: john at arbash-meinel.com-20090518201009-y0o2xad5etcbo6f2
parent: john at arbash-meinel.com-20090518200338-jhot6ifzebd9msw3
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-05-18 15:10:09 -0500
message:
For now, thunk over to Graph.heads() since we know it gives correct answers.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 4371.3.1
revision-id: john at arbash-meinel.com-20090518200338-jhot6ifzebd9msw3
parent: pqm at pqm.ubuntu.com-20090517161026-97fgnk254qwvj4wf
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-05-18 15:03:38 -0500
message:
Start a KnownGraph code, which assumes we have cheap access to the whole graph.
This pre-computes some information, to make heads() checks, etc, cheaper.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
Diff too large for email (1504 lines, the limit is 1000).
More information about the bazaar-commits
mailing list