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