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

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

From Revision 4593.5.3 to 4592

Rev	Summary	Authors	Date
4593.5.3	Bring in the optimized tsort code. Bring in the optimized tsort code. It turns out we needed a way to detect that there was graph cycles. The easiest way to do it, is by noticing that we end up with a node that has no gdfo. That means it has a parent that was not reached before the child was reached, when walking from nodes with no known parents. I'm 90% sure that this is correct, but arguably it should be detected when creating the KnownGraph, and not during topo_sort.	John Arbash Meinel	15 years ago
4593.5.2	Implement a very basic version of KnownGraph.topo_sort that ... Implement a very basic version of KnownGraph.topo_sort that just thunks over to the tsort implementation. Add some tests which ensure that things are working.	John Arbash Meinel	15 years ago
4593.5.1	Merge the improved topo_sort code. Merge the improved topo_sort code.	John Arbash Meinel	15 years ago
4593.4.15	Remove NOTES and ancestry_test as they were just steps along... Remove NOTES and ancestry_test as they were just steps along the way.	John Arbash Meinel	15 years ago
4593.4.14	Revert the previous change, in preparation for doing it 'rig... Revert the previous change, in preparation for doing it 'right'.	John Arbash Meinel	15 years ago
4593.4.13	Hack in a quick change to expose the new functionality to th... Hack in a quick change to expose the new functionality to the higher levels. This changes 'time bzr log -n0 -r -10..-1' on bzr.dev from 2.7s down to 1.4s \o/	John Arbash Meinel	15 years ago
4593.4.12	Name the specific index api _find_ancestors, and the public Name the specific index api _find_ancestors, and the public CombinedGraphIndex api find_ancestry()	John Arbash Meinel	15 years ago
4593.4.11	Snapshot the work in progress. Snapshot the work in progress.	John Arbash Meinel	15 years ago
4593.4.10	Notes for improvement on the OOo tree. Notes for improvement on the OOo tree. Better than 3x faster even when there is only a single pack file. So sure, it would be nice to not load the whole ancestry, and that is important to try to do. But it is also nice to be 3x faster in those cases where we haven't figured out how to do less.	John Arbash Meinel	15 years ago
4593.4.9	Add some debugging statements for now. Add some debugging statements for now. It seems that using get_ancestry in a real-world scenario is an even bigger improvement. I see a 5x improvement in getting the ancestry of bzr.dev. It is ~300ms instead of being 1.5s. Time to try testing it on an OOo tree.	John Arbash Meinel	15 years ago
4593.4.8	Implement CombinedGraphIndex.get_ancestry() Implement CombinedGraphIndex.get_ancestry() This is the appropriate wrapper around GraphIndex/BtreeIndex.get_ancestry. It should allow quick access to getting the complete ancestry graph of the given set of keys and do so in a fairly efficient fashion.	John Arbash Meinel	15 years ago
4593.4.7	Basic implementation of a conforming interface for GraphInde... Basic implementation of a conforming interface for GraphIndex. Add some simple tests, for now we won't try to do anything fancier. Time to start working on CombinedGraphIndex's interface.	John Arbash Meinel	15 years ago
4593.4.6	Add a test that we can walk some of the keys on a given page Add a test that we can walk some of the keys on a given page and that we stop at the boundary, but we could resume walking from there.	John Arbash Meinel	15 years ago
4593.4.5	Start adding some tests. Start adding some tests. Extend the code a little bit, to make parent_map and missing_keys be state that is passed in and then mutated, rather than one and not the other. We need the state since we are walking more than the minimal, though passing in the 'goal' of the function does seem a little silly.	John Arbash Meinel	15 years ago
4593.4.4	Trying out a few more tweaks. Trying out a few more tweaks.	John Arbash Meinel	15 years ago
4593.4.3	Some minor attribute lookup cleanus, doesn't make a big diff... Some minor attribute lookup cleanus, doesn't make a big difference.	John Arbash Meinel	15 years ago
4593.4.2	Removing the min(keys) and max(keys) calls saves 100ms in th... Removing the min(keys) and max(keys) calls saves 100ms in the inner loop (get_ancestry() over all of bzr.dev in a single index is 347ms => 245ms). The current breakdown is roughly: 0.4789 0.1127 bzrlib.btree_index:1129(get_ancestry) 0.0418 0.0418 +<method 'update' of 'set' objects> 0.0480 0.0325 +bzrlib.btree_index:966(_multi_bisect_right) 0.0274 0.0274 +<method 'difference' of 'set' objects> 0.0081 0.0081 +<method 'add' of 'set' objects> 0.0075 0.0075 +<sorted> 0.0048 0.0004 +bzrlib.btree_index:899(_get_internal_nodes) 0.2275 0.0004 +bzrlib.btree_index:917(_get_leaf_nodes) 0.0002 0.0002 +<method 'extend' of 'list' objects> 0.0009 0.0001 +bzrlib.btree_index:1375(key_count) So we have a bit of just general overhead (112ms), and then 50ms spent in _multi_bisect_right, which we could move to a C extension. 50ms in set.update and 28ms in set.difference 227ms in reading and parsing the 222 nodes from disk. It seems a little unfortunate that parsing is the primary overhead, but previous investigation did not reveal much fat that could be trimmed. It is 3.8MB of uncompressed data that is being parsed. That's got to take some amount of time. 200ms might be reasonable. Which would hint that the only way to speed it up would be: 1) a different format 2) don't read the whole thing, stupid :)	John Arbash Meinel	15 years ago
4593.4.1	Implement a function on btree that inlines the get_parent_ma... Implement a function on btree that inlines the get_parent_map loop. It basically looks for direct parents within a single LeafNode, until it hits one that goes outside that node. Also include some performance notes. At least for the number of calls, the new function is much better than get_parent_map. It takes only 50 calls to walk all of bzr.dev, while for get_parent_map it takes 1108 calls. Part of that is the 'long tail problem', which is better, albeit not perfect with the new function.	John Arbash Meinel	15 years ago
4593	(robertc) Partial overhaul of check to do less duplicate wor... (robertc) Partial overhaul of check to do less duplicate work. (Robert Collins)	Canonical.com Patch ...	15 years ago
4592	Updates to buildout.cfg etc to have 'make installer-all' sta... Updates to buildout.cfg etc to have 'make installer-all' start being the preferred way to build win32 installer.	Canonical.com Patch ...	15 years ago

Older »