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

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

Rev	Summary	Authors	Date
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
4371.3.4	The initial results for _find_gdfo on bzr's ancestry: The initial results for _find_gdfo on bzr's ancestry: with 25k revisions, it takes 40.8M steps, a peak todo of 10.6k and 9.7M nodes skipped. Overall, taking 3m55s, which is pretty unusable. Only 25% of the evaluations are 'wasted' (where we see a node from a longer path before we evaluate the node where we thought we should). My guess is that we get lots of 'small waves', where we number a bunch of revisions based on path A, then find out it is reachable from path B, and renumber all of those revisions. Perhaps walking from the largest rather than the smallest would be advantageous, though I have the feeling it just means we get 'long walks', where we walk from the new longest path to the tips of everything underneath it.	John Arbash Meinel	15 years ago
4371.3.3	Implement a Global Distance From Origin computation, using a... Implement a Global Distance From Origin computation, using a heapq.	John Arbash Meinel	15 years ago
4371.3.2	For now, thunk over to Graph.heads() since we know it gives ... For now, thunk over to Graph.heads() since we know it gives correct answers.	John Arbash Meinel	15 years ago
4371.3.1	Start a KnownGraph code, which assumes we have cheap access ... Start a KnownGraph code, which assumes we have cheap access to the whole graph. This pre-computes some information, to make heads() checks, etc, cheaper.	John Arbash Meinel	15 years ago
4371	(Jelmer) Make dpush help/error a bit more generic. (Jelmer) Make dpush help/error a bit more generic.	Canonical.com Patch ...	15 years ago

Older »