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

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

Rev	Summary	Authors	Date
4371.3.24	A couple of cleanups. A couple of cleanups. left_parent/right_parent didn't show a real-world win, so they have been removed. The code is quite a bit clearer without them.	John Arbash Meinel	15 years ago
4371.3.23	Using PySet_Add in the inner loop is a little better, not Using PySet_Add in the inner loop is a little better, not tremendously, though	John Arbash Meinel	15 years ago
4371.3.22	The slowdown was that _to_cleanup wasn't getting reset. The slowdown was that _to_cleanup wasn't getting reset. The other slow part of the pyrex code was that we weren't properly skipping to linear_dominator. Now .pyx is 2x faster than .py.	John Arbash Meinel	15 years ago
4371.3.21	Attempt to make things better by splitting out left_parent a... Attempt to make things better by splitting out left_parent and right_parent into individual attributes (to avoid extra type checks, etc.) However, this seems to make things much worse rather than better.	John Arbash Meinel	15 years ago
4371.3.20	A few tweaks to the pyrex version. A few tweaks to the pyrex version. It is now 'as fast' as the python one for heads() checks on bzr ancestry. It is about 2s faster for heads() checks for annotating NEWS.	John Arbash Meinel	15 years ago
4371.3.19	Get an initial pyrex implementation. Get an initial pyrex implementation. Initial results show it to actually be slightly slower than pure python.	John Arbash Meinel	15 years ago
4371.3.18	Change VF.annotate to use the new KnownGraph code. Change VF.annotate to use the new KnownGraph code. This shows a significant savings in the time for 'annotate NEWS', of about 5s/20s for knit formats, and 45s => 20s for GC formats. Also, factor the code into a helper, so that we can prepare for writing a pyrex version.	John Arbash Meinel	15 years ago
4371.3.17	merge bzr.dev 4427, mostly to get the better GC.annotate cod... merge bzr.dev 4427, mostly to get the better GC.annotate code.	John Arbash Meinel	15 years ago
4371.3.16	Adding some debugging counters shows that Adding some debugging counters shows that 1) Without linear_dominator we are still a little faster. 0.68:1 2) Without linear_dominator we access 86% of the entries that Graph does 3) With linear_dominator we are much faster 0.46:1, and access 57% of the same keys.	John Arbash Meinel	15 years ago
4371.3.15	Allow --max-combinations=0 to run everything. Allow --max-combinations=0 to run everything.	John Arbash Meinel	15 years ago
4371.3.14	Removing the _counters tracking helps, too. Removing the _counters tracking helps, too.	John Arbash Meinel	15 years ago
4371.3.13	Since we are skipping, we should set node.linear_dominator t... Since we are skipping, we should set node.linear_dominator to full-width as well.	John Arbash Meinel	15 years ago
4371.3.12	a bit of cleanup a bit of cleanup	John Arbash Meinel	15 years ago
4371.3.11	Removing the inner function calls also helps a bit. Removing the inner function calls also helps a bit.	John Arbash Meinel	15 years ago
4371.3.10	Avoiding set operations when the ancestor_of field is the sa... Avoiding set operations when the ancestor_of field is the same helps quite a bit. Now down to 0.65:1	John Arbash Meinel	15 years ago
4371.3.9	Add 'ratio' to the timing script, as it makes it more obviou... Add 'ratio' to the timing script, as it makes it more obvious when something is faster. Also add a limit to number of combinations, to make testing easier. Add testing to ensure that the result of KnownGraph.heads() is correct. Initial results showed the new gdfo code being quite a bit slower. Adding in the 'linear_dominator' skipping seems to speed things up dramatically. Probably we aren't wasting as much time in long linear regions. Still seems to give correct results, which is nice to see.	John Arbash Meinel	15 years ago
4371.3.8	Add the time_graph code for benchmarking. Add the time_graph code for benchmarking. Add a lot of debugging counters, etc. At the moment, 'random sampling' shows a performance improvement of 4:1 however, just checking 'parents of a merge' in bzr.dev shows a performance loss of about 1:2. So still need to do a bit more probing to figure out why. It may be the overhead of using objects, or it may be an issue of the algorithm.	John Arbash Meinel	15 years ago
4371.3.7	Implement _heads_from_candidate_keys using a gdfo algorithm. Implement _heads_from_candidate_keys using a gdfo algorithm. It seems to pass all test cases. Best guess is that gdfo solves the earlier problem of 'shortcuts' causing invalid results.	John Arbash Meinel	15 years ago
4371.3.6	Remove the debug timing for _find_gdfo Remove the debug timing for _find_gdfo	John Arbash Meinel	15 years ago
4371.3.5	Change the algorithm as suggested by vila. Change the algorithm as suggested by vila. Only walk a child node once you have seen all parent nodes. This is a huge increase in performance, as it eliminates the double walking problem. Doing all of bzr.dev drops from 3m55s down to 1.88s. Without any micro ops. Still need to verify that the result is correct, but all the gdfo tests pass, so it seems to be.	John Arbash Meinel	15 years ago