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

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

Rev	Summary	Authors	Date
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
4371.3.39	Implement the fix for the python version. 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.	John Arbash Meinel	15 years ago
4371.3.38	Add a failing test for handling nodes that are in the same l... 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.	John Arbash Meinel	15 years ago
4371.3.37	cleanup passes. 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.	John Arbash Meinel	15 years ago
4371.3.36	Cache heads() results from dominator lookups. Cache heads() results from dominator lookups.	John Arbash Meinel	15 years ago
4371.3.35	Changing the heapq algorithm actually ends up with better ov... 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)	John Arbash Meinel	15 years ago
4371.3.34	Changing the code to allow a special case for not always pop... 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.	John Arbash Meinel	15 years ago
4371.3.33	Use a hybrid pass to walk all nodes. 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.	John Arbash Meinel	15 years ago
4371.3.32	A comment about rewriting _find_gdfo A comment about rewriting _find_gdfo	John Arbash Meinel	15 years ago
4371.3.31	Change _KnownGraph.parents to be a tuple rather than a list. 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.	John Arbash Meinel	15 years ago
4371.3.30	Clean up the annotate code while using the new functionality... Clean up the annotate code while using the new functionality.	John Arbash Meinel	15 years ago

Older »