~bzr-pqm/bzr/bzr.dev : changes

~bzr-pqm/bzr/bzr.dev » Changes from revision 4371.4.20

Rev	Summary	Authors	Date
4371.4.19	Update the python code to do the same checking around Update the python code to do the same checking around known_parent_gdfos being present.	John Arbash Meinel	15 years ago
4371.4.18	Big performance win, back to 650ms. 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.	John Arbash Meinel	15 years ago
4371.4.17	tried a different tack, to use a new list and append. 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.	John Arbash Meinel	15 years ago
4371.4.16	Document some perf issues with using known_parent_gdfos, but... Document some perf issues with using known_parent_gdfos, but leave it as a dict.	John Arbash Meinel	15 years ago
4371.4.15	Using a dict drops us to 767ms 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.	John Arbash Meinel	15 years ago
4371.4.14	Optimize _find_gdfo and make known_parent_gdfos a member of ... 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.)	John Arbash Meinel	15 years ago
4371.4.13	Fixed as per John's review. Fixed as per John's review. * bzrlib/_known_graph_pyx.pyx: (_KnownGraphNode.gdfo): Is now a true C long.	Vincent Ladeuil	15 years ago
4371.4.12	Fix typos. Fix typos.	Vincent Ladeuil	15 years ago
4371.4.11	Cleanup tools/time_graph.py and add a --quick option. Cleanup tools/time_graph.py and add a --quick option.	Vincent Ladeuil	15 years ago
4371.4.10	Cleanup. 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 :-/	Vincent Ladeuil	15 years ago
4371.4.9	Simplify gdfo computing by finding tails when at graph build... 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.	Vincent Ladeuil	15 years ago
4371.4.8	Replace the existing KnownGraph._find_gdfo. 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.	Vincent Ladeuil	15 years ago
4371.4.7	Simple Pyrex version for the new heads() method. 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.	Vincent Ladeuil	15 years ago
4371.4.6	Merge trunk@4454 Merge trunk@4454	Vincent Ladeuil	15 years ago
4371.4.5	Merge min_gdfo patch by jam Merge min_gdfo patch by jam	Vincent Ladeuil	15 years ago
4371.4.4	Feedback from John, 'seen' is a set(). 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 :-/	Vincent Ladeuil	15 years ago
4371.4.3	A new heads() method based on gdfo. 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.	Vincent Ladeuil	15 years ago
4371.4.2	Same gdfo processing, without recursion. 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.	Vincent Ladeuil	15 years ago
4371.4.1	A new recursive gdfo processing method. 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.	Vincent Ladeuil	15 years ago
4371.3.40	Fixes for linear_nodes in the pyrex version. Fixes for linear_nodes in the pyrex version. Doesn't seem to specifically impact performance.	John Arbash Meinel	15 years ago

Older »