[MERGE] Improvements to find_unique_ancestors()

[Ian Clatworthy]

John Arbash Meinel wrote:

> For a performance comparison...
> 
> If I run a graph search on the last 100 merge nodes in bzr.dev, it takes an
> average of 320ms to find the unique nodes. With this code, it takes an
> average
> of 115ms. So it is approx 2x as fast.

Really well done on these improvements! I'm rather keen to see this
land so I've spent much of this afternoon/evening reviewing it. I can't
see anything wrong code wise but I'm not comfortable approving it yet.

I think it needs 2 changes made:

1. find_unique_ancestors() is simply too long - it covers 4+ pages
   when printed - making it unmaintainable by people like me with
   smaller brains. I'm aware of the performance emphasis here but
   still feel it could be broken up into a master method that calls
   two or three helper methods. Those helper methods can contain the
   loops, rather than being called inside the loops, so performance
   shouldn't be impacted by a noticeable amount.

2. The algorithm outlined in the opening large comment needs updating
   to cover the information contained in your email.

As a minor note, several of the _mutter calls probably ought to be
using %d instead of %s. It's pretty minor compared to the issues above
though.

bb:resubmit.

I realise that this patch doesn't necessarily make things that much
less readable than the existing code. FWIW, I was happy to approve the
earlier patch because I knew you had a follow-on one coming.
Let's hope we don't need to come back to this method again for a while
now - let's leave it both faster and easier to read please.

Ian C.