Thanks for all the insightfull answers! I've decided to split the tread
into two pieces to ease reading & responding...
Nathaniel Smith wrote:
On Thu, Oct 13, 2005 at 12:15:50AM +0200, Zbynek Winkler wrote:
Nathaniel Smith wrote:
No, different problem entirely -- do_export is currently quadratic in
the history length, mostly because it uses a separate invocation of
monotone to request each manifest delta, and since monotone still does
unbounded delta chaining, it takes linear time to retrieve an
arbitrary manifest. (This also applies to files, but files tend to
have much shallower histories than the tree as a whole, so it doesn't
matter there as much.)
I am not that familiar with monotone codebase, so please forgive the
question - but why does this cause do_export to be quadratic? Does it
actually retrieve arbitrary manifests? Shouldn't the request for
manifest delta be constant if that is the way it is stored in the db?
Two reasons:
-- I don't think the code happens to make the optimization that when
the requested delta is already stored in the db, it should just
return it instead of recomputing it. (This is actually not as
lazy of us as it sounds; monotone currently makes the guarantee
that data pulled from the database is never corrupted, and we
only have
-- as you correctly notice, we store reverse deltas, but the dumb
server wants forward deltas. So we can't pull deltas straight
out of the db anyway, they have to be computed.
Aren't the deltas the same no matter if they are forward or reverse?
Given a revision B and C does it matter if you say "we store B->C" or
"B<-C"? In both cases once you have one of the revisions you can
reconstruct the other. No? The only difference would be where it starts...
And where does the linear search come
from when getting the deltas?
Say we have a history:
A -> B -> C -> D -> E
Because we store reverse deltas, this is actually stored on disk as:
A <- B <- C <- D <- E
Suppose we want the delta from A to B. To get this, we need to
reconstruct A and B. Doing this requires starting from E, then
using the E->D link to get to D, then the D->C link to get to C, etc.,
until we reach A and B. (There are some optimizations here, but they
don't affect the algorithmic complexity.) This takes time linear in
length of that chain, and ATM that chain can get as long as the total
history graph.
I take it you are talking about the current implementation in monotone?
Otherwise I do not see the need to reconstruct A and B to get their
delta...?
On a related note: how does monotone deal with deltas and multiple
parents? When a merge is done, is a separate delta created against each
of the parents? Which source files should I take a look at when
wondering about things like this?
Thanks.
Zbynek
--
http://zw.matfyz.cz/ http://robotika.cz/
Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
_______________________________________________
Monotone-devel mailing list
[email protected]
http://lists.nongnu.org/mailman/listinfo/monotone-devel
