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.
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.