weave size very sensitive to insertion order

[Robert Collins]

I've been playing with the new topo sort I wrote, and have found this
with the internal launchpad code:

   779428 2006-02-18 06:04 inventory
 36698698 2006-02-25 16:30 inventory.backup.weave
101447702 2006-02-25 18:24 inventory.weave

There are 5488 revisions of inventory in the weave, and no unreferenced
inventories. 168 of them are missing parents that were ghosts when they
were first added.

The weave blows up to 3 times its size after the conciliation - I've
checked that the graph is right: there are only 168 different entries
between the two graphs and a random sample of those does indeed have
wrong parents in the old weave and correct ones in the new weave.


So insertion order appears to have a dramatic effect on the weave size.

I'm not sure how to make a minimal test of this, but as its only
inventory data I may be able to make a copy of these files if people
wish to analyze this - I'm going to check with the lp team leader about
that.

What I am seeing is a sort of toggle between inventory lines in the
weave for a known file:

{ x
COPYING ... @ rev A
....
} x
{ y
COPYING ... @ rev B
....
}
{ z
COPYING ... @ rev A
}

So its almost like the diff against the union-of-active-lines failed
some number of times and gave inappropriate full-insertions or something
like that.

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/2dc661fa/attachment.pgp