Rev 4466: (jam, vila) Improve the KnownGraph.heads() code, in file:///home/pqm/archives/thelove/bzr/%2Btrunk/
Canonical.com Patch Queue Manager
pqm at pqm.ubuntu.com
Sun Jun 21 05:30:32 BST 2009
At file:///home/pqm/archives/thelove/bzr/%2Btrunk/
------------------------------------------------------------
revno: 4466
revision-id: pqm at pqm.ubuntu.com-20090621043025-one1vuhpnsgdv5tv
parent: pqm at pqm.ubuntu.com-20090620025819-9fkf33yr3dvtwh2o
parent: john at arbash-meinel.com-20090621033120-2yzh32vjtdr6y7xm
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Sun 2009-06-21 05:30:25 +0100
message:
(jam, vila) Improve the KnownGraph.heads() code,
using a min_gdfo value (can be another 10-100x faster on complex
graphs).
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
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
------------------------------------------------------------
revno: 4371.4.32
revision-id: john at arbash-meinel.com-20090621033120-2yzh32vjtdr6y7xm
parent: john at arbash-meinel.com-20090619203535-ddfmpm4c9ey1ijrp
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Sat 2009-06-20 22:31:20 -0500
message:
Update NEWS to include Vincent since he contributed significantly.
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
------------------------------------------------------------
revno: 4371.4.31
revision-id: john at arbash-meinel.com-20090619203535-ddfmpm4c9ey1ijrp
parent: john at arbash-meinel.com-20090619201707-1zruedh20651c14q
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 15:35:35 -0500
message:
Apply the same 'never pop' logic to the heads() code.
Turns out to be another big win, going from 409ms down to 362ms.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.30
revision-id: john at arbash-meinel.com-20090619201707-1zruedh20651c14q
parent: john at arbash-meinel.com-20090619200803-0s181hhkbo4sf9mh
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 15:17:07 -0500
message:
We don't need self._tails anymore, nor does it need to be a set.
Bring back '_find_tails' because walking the dictionary is faster than pushing/popping
into the set. Also we can use a list rather than a set, and populate it right away.
Down to 42.8ms bzr.dev and 550ms for OOo.
Note that _initialize_nodes time is 35ms and 407ms, and that _find_tails is approx 40ms for OOo.
So we are down to ~8ms for _find_tails + _find_gdfo for bzr.dev, which is probably
about as low as we can make it.
Any further improvements are going to be from _initialize_nodes.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.29
revision-id: john at arbash-meinel.com-20090619200803-0s181hhkbo4sf9mh
parent: john at arbash-meinel.com-20090619195441-svubgww09wvmqh40
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 15:08:03 -0500
message:
Pre-allocating self._nodes turned out to be slower.
I guess it doesn't realloc very often, and save on dict lookups while it is small.
Also, you don't end up with the incref/decref to None, but I would imagine that is
a trivial amount of time.
I wish it was easier to define an allocator for Pyrex objects. (It is fairly easy
in the Python C api.)
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.28
revision-id: john at arbash-meinel.com-20090619195441-svubgww09wvmqh40
parent: john at arbash-meinel.com-20090619194927-re2ony3ebgp2a1lg
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 14:54:41 -0500
message:
We spent a lot of time adding and removing keys from tails.
Because we walk parent_map randomly, we don't know early on whether we will see
a parent node again or not. And it turns out that we rarely do, but we often
have to enqueue lots of nodes in case they show up later.
My getting rid of add/remove and instead iterating over the dict a second time,
we are down to 547ms and 44ms for OOo and bzr.dev.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.27
revision-id: john at arbash-meinel.com-20090619194927-re2ony3ebgp2a1lg
parent: john at arbash-meinel.com-20090619194226-kjutz0x3s29mzwc5
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 14:49:27 -0500
message:
Re-use the child.seen attribute for tracking num parents.
Down to 49.8ms and 618ms for bzr and OO.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.26
revision-id: john at arbash-meinel.com-20090619194226-kjutz0x3s29mzwc5
parent: john at arbash-meinel.com-20090619193650-mfz7c42s0s8c33sr
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 14:42:26 -0500
message:
Don't shrink the pending list.
Instead track which item we are on, and append if we have to, but just decrement
the counter when consuming an item.
Down to 51.8ms for bzr.dev, 644ms for OOo.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.25
revision-id: john at arbash-meinel.com-20090619193650-mfz7c42s0s8c33sr
parent: john at arbash-meinel.com-20090619192632-1a4ntoq61fkhlp2x
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 14:36:50 -0500
message:
We had an 'child_node.gdfo is None' check in the inner loop.
This caused us to create a PyInt when we have a long which *can't* ever be None.
Speeds up OOo a little bit, bzr is 54.5ms from ~69ms.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.24
revision-id: john at arbash-meinel.com-20090619192632-1a4ntoq61fkhlp2x
parent: john at arbash-meinel.com-20090619191337-804ochxdkeri6g07
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 14:26:32 -0500
message:
Make a note of the 'worst case' for heads.
modified:
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
------------------------------------------------------------
revno: 4371.4.23
revision-id: john at arbash-meinel.com-20090619191337-804ochxdkeri6g07
parent: john at arbash-meinel.com-20090619183653-m5k5roph4yc2rclw
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 14:13:37 -0500
message:
Clean up the imports at the top.
Remove PySet references. Give nice ordering to PyTuple, PyDict and PyList.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.22
revision-id: john at arbash-meinel.com-20090619183653-m5k5roph4yc2rclw
parent: john at arbash-meinel.com-20090619183001-xy6dp466kh3cwd1j
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 13:36:53 -0500
message:
Changing from a set of seen to a list to cleanup and a seen attribute.
Known: 1.682s
Known (pyx): 0.440s
ratio: 3.8:1 faster
Breaks the 2x faster barrier.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.21
revision-id: john at arbash-meinel.com-20090619183001-xy6dp466kh3cwd1j
parent: john at arbash-meinel.com-20090619175337-uozt3bntdd48lh4z
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 13:30:01 -0500
message:
Spend some time optimizing the inner heads() loop, approx 2x faster.
Various tweaks and their effect:
# Baseline
Found 25382 nodes, loaded in 2.194s
7581 combinations
Known: 1.626s
Known (pyx): 0.993s
ratio: 1.6:1 faster
# Tweaks for NULL_REVISION and PyDict_Size, min_gdfo as long
Known (pyx): 0.945s
ratio: 1.7:1 faster
# PySet_Contains, PySet_Add
Known (pyx): 0.846s
ratio: 1.9:1 faster
# Avoid pop & push
Known (pyx): 0.564s
ratio: 2.9:1 faster
# pending_pop
Known (pyx): 0.542s
ratio: 3.1:1 faster
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.20
revision-id: john at arbash-meinel.com-20090619175337-uozt3bntdd48lh4z
parent: john at arbash-meinel.com-20090619174059-jzowjv0d86vzjg4m
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 12:53:37 -0500
message:
Update time_graph to use X:1 ratios rather than 0.xxx ratios.
It is just easier to track now that the new code is much faster.
modified:
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
------------------------------------------------------------
revno: 4371.4.19
revision-id: john at arbash-meinel.com-20090619174059-jzowjv0d86vzjg4m
parent: john at arbash-meinel.com-20090619173701-56p7yg3ionug2slb
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 12:40:59 -0500
message:
Update the python code to do the same checking around known_parent_gdfos being present.
modified:
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
------------------------------------------------------------
revno: 4371.4.18
revision-id: john at arbash-meinel.com-20090619173701-56p7yg3ionug2slb
parent: john at arbash-meinel.com-20090619173033-0opvbm5ubonl0jo2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 12:37:01 -0500
message:
Big performance win, back to 650ms.
Note that we don't need to grow known_parent_gdfos indefinitely.
Once we have queued up a node to be walked, we should never walk
it again, so we can remove the entry.
We also can avoid ever *setting* the item if we resolve it in
the first pass.
Will update the python version as well.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.17
revision-id: john at arbash-meinel.com-20090619173033-0opvbm5ubonl0jo2
parent: john at arbash-meinel.com-20090619172010-1g5aj28byaxko408
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 12:30:33 -0500
message:
tried a different tack, to use a new list and append.
This would cause us to tend to walk from low gdfo to high gdfo, but it
didn't seem to be a big win.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.16
revision-id: john at arbash-meinel.com-20090619172010-1g5aj28byaxko408
parent: john at arbash-meinel.com-20090619170818-9yi5nqmgo0x09983
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 12:20:10 -0500
message:
Document some perf issues with using known_parent_gdfos, but leave it as a dict.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.15
revision-id: john at arbash-meinel.com-20090619170818-9yi5nqmgo0x09983
parent: john at arbash-meinel.com-20090619170356-wfb1l9smtoafxxsy
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 12:08:18 -0500
message:
Using a dict drops us to 767ms
Slower than we could be, but still 'fast enough' and still 2x faster than
the unoptimized form.
Will look into a little bit of tuning.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.14
revision-id: john at arbash-meinel.com-20090619170356-wfb1l9smtoafxxsy
parent: v.ladeuil+lp at free.fr-20090619124127-3boejbn0h5nb499h
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: jam-gdfo-heads
timestamp: Fri 2009-06-19 12:03:56 -0500
message:
Optimize _find_gdfo and make known_parent_gdfos a member of KnownGraphNode
This drops the _find_gdfo for OOo from 1.46s down to 621ms, which is even faster
than previous.
Will look into restoring known_parent_nodes with a PyDict_GetItem check instead
of a try/except key error. But I expect it will be quite a bit slower.
(note original time was about 740ms, so this code is about 2x slower than it was.)
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.13
revision-id: v.ladeuil+lp at free.fr-20090619124127-3boejbn0h5nb499h
parent: v.ladeuil+lp at free.fr-20090618212056-syvh83qj7tpffhgf
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: gdfo-heads
timestamp: Fri 2009-06-19 14:41:27 +0200
message:
Fixed as per John's review.
* bzrlib/_known_graph_pyx.pyx:
(_KnownGraphNode.gdfo): Is now a true C long.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.12
revision-id: v.ladeuil+lp at free.fr-20090618212056-syvh83qj7tpffhgf
parent: v.ladeuil+lp at free.fr-20090618200024-fdrav7hxlz3soot2
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Thu 2009-06-18 23:20:56 +0200
message:
Fix typos.
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.11
revision-id: v.ladeuil+lp at free.fr-20090618200024-fdrav7hxlz3soot2
parent: v.ladeuil+lp at free.fr-20090618194524-poedor61th3op5dm
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Thu 2009-06-18 22:00:24 +0200
message:
Cleanup tools/time_graph.py and add a --quick option.
modified:
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
------------------------------------------------------------
revno: 4371.4.10
revision-id: v.ladeuil+lp at free.fr-20090618194524-poedor61th3op5dm
parent: v.ladeuil+lp at free.fr-20090618182610-o59r8149nlzb3b68
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Thu 2009-06-18 21:45:24 +0200
message:
Cleanup.
* bzrlib/tests/test__known_graph.py:
(TestKnownGraph): Delete dominator tests.
* bzrlib/_known_graph_pyx.pyx:
Cleanup all references to old version and linear dominators :-/
* bzrlib/_known_graph_py.py:
Cleanup all references to old version and 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
bzrlib/tests/test__known_graph.py test__known_graph.py-20090610185421-vw8vfda2cgnckgb1-2
------------------------------------------------------------
revno: 4371.4.9
revision-id: v.ladeuil+lp at free.fr-20090618182610-o59r8149nlzb3b68
parent: v.ladeuil+lp at free.fr-20090618141237-k9u7mrithzstg15z
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Thu 2009-06-18 20:26:10 +0200
message:
Simplify gdfo computing by finding tails when at graph build time.
* bzrlib/_known_graph_pyx.pyx:
(KnownGraph._get_or_create_node): We need to know if the ndoe as
created.
(KnownGraph._initialize_nodes): Calulate tails ahead of time to
intialize gdfo computing.
(KnownGraph._find_gdfo): Use tails directly.
* bzrlib/_known_graph_py.py:
(KnownGraph._initialize_nodes): Calulate tails ahead of time to
intialize gdfo computing.
(KnownGraph._find_gdfo): Use tails directly.
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.4.8
revision-id: v.ladeuil+lp at free.fr-20090618141237-k9u7mrithzstg15z
parent: v.ladeuil+lp at free.fr-20090618095138-rha25usmqwsfwoxv
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Thu 2009-06-18 16:12:37 +0200
message:
Replace the existing KnownGraph._find_gdfo.
* bzrlib/_known_graph_pyx.pyx:
(_find_gdfo): pyrex version, almost as fast as the previous one,
but we don't need the linear dominator so we can potentially save
some time during __init__.
* bzrlib/_known_graph_py.py:
(KnownGraph._find_gdfo): Get rid of the inner function to stay in
sync with the pyrex version.
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.4.7
revision-id: v.ladeuil+lp at free.fr-20090618095138-rha25usmqwsfwoxv
parent: v.ladeuil+lp at free.fr-20090617163711-iqubyv0tlqr8ayvl
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Thu 2009-06-18 11:51:38 +0200
message:
Simple Pyrex version for the new heads() method.
* tools/time_graph.py:
Also display parent_map loading.
* bzrlib/_known_graph_pyx.pyx:
(KnownGraph.heads): pyrex version faster by ~20% than the previous
pyrex version, without using linears dominators. Strictly speaking
linear dominators breaks the algorithm as jumping from one node to
its dominator may miss a candidate. Trying to compensate that
seems to cost more than the benefits it provides :-/ Their use
will surely come back later.
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
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
------------------------------------------------------------
revno: 4371.4.6
revision-id: v.ladeuil+lp at free.fr-20090617163711-iqubyv0tlqr8ayvl
parent: v.ladeuil+lp at free.fr-20090617162802-gcbr56os427emput
parent: pqm at pqm.ubuntu.com-20090617100437-gavn9zkum4dj5yjz
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Wed 2009-06-17 18:37:11 +0200
message:
Merge trunk at 4454
added:
bzrlib/help_topics/en/diverged-branches.txt divergedbranches.txt-20090608035534-mb4ry8so4hw238n0-1
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
bzr bzr.py-20050313053754-5485f144c7006fa6
bzrlib/__init__.py __init__.py-20050309040759-33e65acf91bbcd5d
bzrlib/_dirstate_helpers_c.pyx dirstate_helpers.pyx-20070503201057-u425eni465q4idwn-3
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/branch.py branch.py-20050309040759-e4baf4e0d046576e
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/chk_serializer.py chk_serializer.py-20081002064345-2tofdfj2eqq01h4b-1
bzrlib/commands.py bzr.py-20050309040720-d10f4714595cf8c3
bzrlib/commit.py commit.py-20050511101309-79ec1a0168e0e825
bzrlib/config.py config.py-20051011043216-070c74f4e9e338e8
bzrlib/dirstate.py dirstate.py-20060728012006-d6mvoihjb3je9peu-1
bzrlib/errors.py errors.py-20050309040759-20512168c4e14fbd
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/help_topics/en/configuration.txt configuration.txt-20060314161707-868350809502af01
bzrlib/help_topics/en/eol.txt eol.txt-20090327060429-todzdjmqt3bpv5r8-3
bzrlib/push.py push.py-20080606021927-5fe39050e8xne9un-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/revisiontree.py revisiontree.py-20060724012533-bg8xyryhxd0o0i0h-1
bzrlib/serializer.py serializer.py-20090402143702-wmkh9cfjhwpju0qi-1
bzrlib/shellcomplete.py shellcomplete.py-20050822153127-3be115ff5e70fc39
bzrlib/smart/bzrdir.py bzrdir.py-20061122024551-ol0l0o0oofsu9b3t-1
bzrlib/smart/repository.py repository.py-20061128022038-vr5wy5bubyb8xttk-1
bzrlib/smart/request.py request.py-20061108095550-gunadhxmzkdjfeek-1
bzrlib/tests/blackbox/test_diff.py test_diff.py-20060110203741-aa99ac93e633d971
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/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/branch_implementations/test_push.py test_push.py-20070130153159-fhfap8uoifevg30j-1
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/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__known_graph.py test__known_graph.py-20090610185421-vw8vfda2cgnckgb1-2
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_knit.py test_knit.py-20051212171302-95d4c00dd5f11f2b
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/test_ui.py test_ui.py-20051130162854-458e667a7414af09
bzrlib/tests/tree_implementations/test_list_files.py test_list_files.py-20070216005501-cjh6fzprbe9lbs2t-1
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/transform.py transform.py-20060105172343-dd99e54394d91687
bzrlib/ui/text.py text.py-20051130153916-2e438cffc8afc478
bzrlib/workingtree.py workingtree.py-20050511021032-29b6ec0a681e02e3
bzrlib/workingtree_4.py workingtree_4.py-20070208044105-5fgpc5j3ljlh5q6c-1
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
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.4.5
revision-id: v.ladeuil+lp at free.fr-20090617162802-gcbr56os427emput
parent: v.ladeuil+lp at free.fr-20090617162550-uz7q6k8ber62y2r5
parent: john at arbash-meinel.com-20090617144058-lfn4u111x6cn3ihr
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Wed 2009-06-17 18:28:02 +0200
message:
Merge min_gdfo patch by jam
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.5.1
revision-id: john at arbash-meinel.com-20090617144058-lfn4u111x6cn3ihr
parent: v.ladeuil+lp at free.fr-20090617123221-ijscdmxhxds026c0
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: gdfo-heads
timestamp: Wed 2009-06-17 09:40:58 -0500
message:
Simply add min_gdfo to the pyrex search func
modified:
bzrlib/_known_graph_pyx.pyx _known_graph_pyx.pyx-20090610194911-yjk73td9hpjilas0-1
------------------------------------------------------------
revno: 4371.4.4
revision-id: v.ladeuil+lp at free.fr-20090617162550-uz7q6k8ber62y2r5
parent: v.ladeuil+lp at free.fr-20090617123221-ijscdmxhxds026c0
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Wed 2009-06-17 18:25:50 +0200
message:
Feedback from John, 'seen' is a set().
* bzrlib/_known_graph_py.py:
(KnownGraph.heads): Make 'seen' a set() instead of a dict(), perf
difference seems to be lost in the noise though :-/
modified:
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
------------------------------------------------------------
revno: 4371.4.3
revision-id: v.ladeuil+lp at free.fr-20090617123221-ijscdmxhxds026c0
parent: v.ladeuil+lp at free.fr-20090616134841-mu1e58vknaend6dz
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Wed 2009-06-17 14:32:21 +0200
message:
A new heads() method based on gdfo.
* bzrlib/tests/test__known_graph.py:
(TestKnownGraph.test_heads_with_ghost): Add tests to ensure ghosts
are corectly handled.
* bzrlib/_known_graph_py.py:
(KnownGraph.heads): A new version taking avantage of gdfo to
reduce the number of nodes processed. This implementation passes
all the currenlty defined tests and then some. Using time_graph.py
reports 0.220s instead of the previous 7.350s.
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.4.2
revision-id: v.ladeuil+lp at free.fr-20090616134841-mu1e58vknaend6dz
parent: v.ladeuil+lp at free.fr-20090616093753-ihx32neot2jqhqqn
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Tue 2009-06-16 15:48:41 +0200
message:
Same gdfo processing, without recursion.
* bzrlib/_known_graph_py.py:
(KnownGraph._find_gdfo): Push nodes into pending, since the order
doesn't matter, there is no need to recurse.
modified:
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
------------------------------------------------------------
revno: 4371.4.1
revision-id: v.ladeuil+lp at free.fr-20090616093753-ihx32neot2jqhqqn
parent: john at arbash-meinel.com-20090612202108-blsyks1kdxod0lsk
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Tue 2009-06-16 11:37:53 +0200
message:
A new recursive gdfo processing method.
* bzrlib/_known_graph_py.py:
(KnownGraph._find_gdfo): A new version in O(n) processing each
node only once.
modified:
bzrlib/_known_graph_py.py _known_graph_py.py-20090610185421-vw8vfda2cgnckgb1-1
tools/time_graph.py time_graph.py-20090608210127-6g0epojxnqjo0f0s-1
Diff too large for email (1256 lines, the limit is 1000).
More information about the bazaar-commits
mailing list