find_difference shortcut failure without walking out

John Arbash Meinel john at arbash-meinel.com
Wed Dec 12 21:34:24 GMT 2007


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

John Arbash Meinel wrote:
> So I did some testing of my version of the code on our bzr.dev history. And I
> found that it still fails under certain conditions. This is a graph which shows it.
> 
> NULL_REVISION
>     |
>     a
>     |
>     b
>     |
>     c
>     |
>     d
>     |\
>     e f
>     | |\
>     | g h
>     |/| |
>     i j |
>     | | |
>     | k |
>     | | |
>     | l |
>     |/|/
>     m n
> 

...

> One thing I considered. Get rid of the "common searcher". Instead, when
> searchers find common nodes, they use "find_seen_ancestors" to jump to the tip
> of the ancestry. And then search terminates once all searchers are on the same
> nodes.

I ended up implementing this. And it passes all tests (including the above
graph). However it still fails for part of the Bazaar ancestry. I've attached a
PNG image showing the ancestry.

I haven't quite figured out what is going on. In the graph the white nodes were
searched normally. The light blue nodes are when the algorithm had all
searchers converge onto the same nodes, and thus stop. The red nodes are ones
it considers to be unique which are actually common. The green nodes are ones
it would find if I continued to search for 4 more steps. The pink are red nodes
that would have been found.

Each node is marked with the step it was found by what searcher. So "8l" is
found at step 8 by the 'left' searcher, '8r' is right searcher. When a node is
found to be common it gets 'c' for 'Common'. The code searches the seen
ancestors whenever it finds a new common, and for that it gives c_a (Common
Ancestor).

In general, the history is really messy, so if someone wants to help me track
down why the searchers are failing, I would appreciate the help.

The specifically interesting nodes seem to be that revision 1420 merged in a
feature branch. Which had more development done on it, and was then merged into
yet another feature branch, before that branch was merged into whatever was
mainline.

The other thing I notice is that there are 8 'terminal' nodes. Which means
something like having 8 concurrent branches in flight.

The best I can come up with at this point is multiple merging of the same node.
A feature branch was merged into integration both sides had more work done, and
then feature merged integration. And at the same time trunk was merging
occasionally with integration.

Note that I think the numbers are a bit screwy, because when we renormalized
ancestry, it turned out that bzr.dev decided to pick up some of Robert's
integration branch as its mainline. So while it is bzr.dev numbers, looking at
them, the mbp ones are getting dots, while Robert's are getting mainline revisions.

Anyway, hopefully I can create a test case with fewer than 100 nodes to
experiment with this. Certainly it is a form of race condition, since stepping
3 more nodes would catch it. I just haven't figured out why yet.

John
=:->

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHYFPfJdeBCYSNAAMRAtz+AJ0QQp12eWa62+WTjVhxfBlZLLmv6ACdGA6Z
8cG1DHVcVjOVQncxJhTzMwc=
=f25d
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.png
Type: image/png
Size: 158925 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20071212/b66c8531/attachment-0001.png 


More information about the bazaar mailing list