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

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

Rev	Summary	Authors	Date
4593.5.17	No need to pop one item off the stack after another. No need to pop one item off the stack after another. We can just iterate over the group and append to the output. Use direct function calls, rather than ordered.append. Down to: # 103ms graph.KnownGraph().merge_sort() # 55ms kg.merge_sort()	John Arbash Meinel	15 years ago
4593.5.16	Change the revno handling code. Change the revno handling code. # 112ms graph.KnownGraph().merge_sort() # 64ms kg.merge_sort()	John Arbash Meinel	15 years ago
4593.5.15	Use the same implementation of stack handling to avoid appen... Use the same implementation of stack handling to avoid append/pop. Instead we track what the 'current' entry is, and then grow the stack only when we need more space. This also turns into using direct list access, rather than python apis. Drops the time down: - # 138ms graph.KnownGraph().merge_sort() - # 89ms kg.merge_sort() + # 127ms graph.KnownGraph().merge_sort() + # 77ms kg.merge_sort()	John Arbash Meinel	15 years ago
4593.5.14	Merge bzr.dev 4615 Merge bzr.dev 4615 Bring in the latest faster-iter-ancestry.	John Arbash Meinel	15 years ago
4593.5.13	Moving into attributes instead of dicts improves performance... Moving into attributes instead of dicts improves performance: - # 194ms graph.KnownGraph().merge_sort() - # 143ms kg.merge_sort() + # 138ms graph.KnownGraph().merge_sort() + # 89ms kg.merge_sort() Probably the biggest win is that we can walk directly to the _MergeSortNode parent, without having to do dict lookups.	John Arbash Meinel	15 years ago
4593.5.12	Move some sets/dicts into attributes. Move some sets/dicts into attributes. This does expose an open question about 'merge_sort_race'.	John Arbash Meinel	15 years ago
4593.5.11	Without doing any real tuning yet, we see a decent speedup f... Without doing any real tuning yet, we see a decent speedup for merge_sort: Current performance numbers for merge_sort(bzr_dev_parent_map): 310ms tsort.merge_sort() 194ms graph.KnownGraph().merge_sort() 143ms kg.merge_sort()	John Arbash Meinel	15 years ago
4593.5.10	finish getting the revno numbers working correctly. finish getting the revno numbers working correctly.	John Arbash Meinel	15 years ago
4593.5.9	Fix a bug in MergeSorter that was fixed only in the inlined ... Fix a bug in MergeSorter that was fixed only in the inlined pop_node	John Arbash Meinel	15 years ago
4593.5.8	Approximate implementation in Pyrex. Approximate implementation in Pyrex. Mostly just a carbon copy of the python version, having some weird issues with the numbering of roots/ghosts. Which is why the test existed in the first place :).	John Arbash Meinel	15 years ago
4593.5.7	start working on a pyrex implementation of MergeSorter start working on a pyrex implementation of MergeSorter This is based on the KnownGraph code. One of the key insights is that hopefully we can use a single stack with smart objects, rather than a bunch of stacks with various objects. Also, if we find information from gdfo or children lists to be helpful, we can make use of them. For now, I'm just going to port the existing MergeSorter code into pyrex using objects.	John Arbash Meinel	15 years ago
4593.5.6	Create the crude merge_sort implementation that just thunks ... Create the crude merge_sort implementation that just thunks over to the old implementation. The main win here is that we get to copy across all the tests so far, and they all pass. :)	John Arbash Meinel	15 years ago
4593.5.5	We don't need to compare the lists multiple times. We don't need to compare the lists multiple times.	John Arbash Meinel	15 years ago
4593.5.4	Split up the tests a bit. Split up the tests a bit. Only the heads() tests need to be run 4 times, the rest only need to be run 2x.	John Arbash Meinel	15 years ago
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