weave size very sensitive to insertion order

[Robert Collins]

On Mon, 2006-02-27 at 20:01 -0600, John A Meinel wrote:
> Robert Collins wrote:


> It depends how topo_sort works. If you have an ancestry of:
> 
> A   B
> |   |
> C   D
> |   |
> E   F
>  \ / \
>   G   H
> 
> There are 2 obvious sortings:
> A,B,C,D,E,F,G
> and
> A,C,E,B,D,F,G

The current bzr - the one producing a 30Mb weave - generates ABCDEFGH
The one I found this with - the subsecond topo_sort - *can* generate
ABCDEFGH but is more likely to generate something like ACEBDFGH or
BDFHACEG or even ACBDFHEG depending on what nodes form the starting
position.

> I would guess that the former would cause difficulties with weave, but I
> couldn't guarantee that.

As it happens, the former generates the smaller weave :).

> I am a decent hand at reading weaves, so I might be interested in
> comparing them.

ok. Shall see what can be done. For interest there is only one root
here:
>>> roots = [(name, i.parent_names(name)) for name in i.names() if
i.parent_names(name) == []]
>>> print roots
[('Arch-1:rocketfuel at canonical.com%soyuz--devel--0--base-0', [])]

> Oh... And the other thing that would cause lots of problems is having an
> ancestry like above, because A & B are both children of the 'null:'
> revision, which means they can't share any lines. So even if the
> contents are identical, you would end up with duplicated lines. And then
> if you merge G, it would have to pick which set to delete. Which would
> mean that H might be using the lines that G deleted, which means that
> when it is merged (in the future), the lines would have to be deleted again.

Hmm, I don't see that as being a requirement of a weave per se - theres
no reason that revisions with differing heritage cannot share lines, as
long as appropriate control instructions are there. I know our inserter
does not try for that, but its feasible.

Rob

-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 191 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060228/9c8c6a53/attachment.pgp