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

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

Rev	Summary	Authors	Date
4371.4.31	Apply the same 'never pop' logic to the heads() code. Apply the same 'never pop' logic to the heads() code. Turns out to be another big win, going from 409ms down to 362ms.	John Arbash Meinel	15 years ago
4371.4.30	We don't need self._tails anymore, nor does it need to be a ... 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.	John Arbash Meinel	15 years ago
4371.4.29	Pre-allocating self._nodes turned out to be slower. 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.)	John Arbash Meinel	15 years ago
4371.4.28	We spent a lot of time adding and removing keys from tails. 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.	John Arbash Meinel	15 years ago
4371.4.27	Re-use the child.seen attribute for tracking num parents. Re-use the child.seen attribute for tracking num parents. Down to 49.8ms and 618ms for bzr and OO.	John Arbash Meinel	15 years ago
4371.4.26	Don't shrink the pending list. 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.	John Arbash Meinel	15 years ago
4371.4.25	We had an 'child_node.gdfo is None' check in the inner loop. 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.	John Arbash Meinel	15 years ago
4371.4.24	Make a note of the 'worst case' for heads. Make a note of the 'worst case' for heads.	John Arbash Meinel	15 years ago
4371.4.23	Clean up the imports at the top. Clean up the imports at the top. Remove PySet references. Give nice ordering to PyTuple, PyDict and PyList.	John Arbash Meinel	15 years ago
4371.4.22	Changing from a set of seen to a list to cleanup and a seen ... 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.	John Arbash Meinel	15 years ago
4371.4.21	Spend some time optimizing the inner heads() loop, approx 2x... 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	John Arbash Meinel	15 years ago
4371.4.20	Update time_graph to use X:1 ratios rather than 0.xxx ratios... 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.	John Arbash Meinel	15 years ago
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

Older »