Code review comment for lp:~vila/bzr/gdfo-heads

This is a new implementation of KnownGraph.heads() and a companion _find_gdfo().

The main target is annotate, this doesn't address the revno
calculation which is certainly the next target (all numbers below
referring to annotate are with --show-ids (aka, the improvements
are due to the per-file graph better processing, not the revision
graph)).

Climbing on Jonh's shoulders (all the test and the pyrex plumbing
was there, waiting ;-P) I was able to improve the performances for
"dense" graphs (think mysql). The performance for bzr improves
too, but in a less spectacular way.

This patch also includes a fix by John for its implementation
that also give some spectacular results, keep that in mind when
reading the numbers.

Below are some results for 1.16, bzr.dev@4459, john's version
(aka an unreleased one, see
revid:<email address hidden> in
this branch) and this proposed version (which supersedes John's
one).

I've used NEWS for bzr as a reference point in the bzr.dev@4459
tree, and sql/mysqld.cc in dev6 conversion of mysql-6.0@2791.

I've also used tools/time_graph.py to measure the performances
more precisely.

Annotate bzr NEWS:
1.16: real 12.36 user 12.27 sys 0.04
trunk: real 6.84 user 6.80 sys 0.03
john: real 6.76 user 6.11 sys 0.12
this: real 6.00 user 5.96 sys 0.03

Annotate mysql sql/mysqld.cc:
1.16: real 21.66 user 21.52 sys 0.14
trunk: real
john: real 19.97 user 19.62 sys 0.17
this: real 18.69 user 18.56 sys 0.14

time_graph bzr, 25378 nodes, 7586 combinations:
1.16: N.A.
trunk: python 127.070s pyrex 49.800s
john: python 1.030s pyrex 0.700s
this: python 0.960s pyrex 0.540s

time_graph mysql, 67633 nodes, 33740 combinations:
1.16: N.A.
trunk: python 3470.620s pyrex 1751.760s
john: python 34.190s pyrex 36.480s
this: python 33.750s pyrex 17.670s

So while John fixed version vastly improves that specific part
(gdfo rules), the proposed new algorithms goes even further for
'bushy' graphs.

Unlike John, I couldn't find a way to make good use of 'linear
dominators' (either my pyrex fu is weak (two days old) or they'll
be useful elsewhere (I'm sure about that ;-)). Anyway, trying to
use them only decrease the performance and increase the memory
consumption, so, finally I get rid of them.

There are certainly better optimisations to put in place at the
pyrex level, but I thought the improvement was worth a review.