Ganesh Sittampalam wrote: > On 05/03/2012 17:05, Owen Stephens wrote: >> On 5 March 2012 16:18, Michael Hendricks <mich...@ndrix.org >> <mailto:mich...@ndrix.org>> wrote: >>>Since I'm not yet familiar with Darcs' internal workings, can someone >>>help me understand why calculating a minimal context is so expensive? >> >> Because you need to do a whole bunch of commutes - working out which of >> *all* >> the patches in the repository cleanly commute past a given patch. >> >>>Is it because Darcs doesn't have quick access to patch summaries and >>>must load every patch, in its entirety, from disk to perform a >>>commutation? >> >> Yeah, I think that's pretty much it. > > It's also that, whether or not you have the patch data, the naive > algorithm is O(n^2) to commute the minimal context of a single patch, > and I don't know a more sophisticated one (though I have some vague > ideas). > > Consider a repo ABCDEF, and you want to calculate the minimal context of > F. First you commute F past E, and that succeeds so you can drop E. I'm > ignoring the fact that the representation changes as you do it: > > ABCDF > > Now you try D. That fails. Now you need to try C. But to try C, you > first have to commute it past D. So now what we really have is a list of > patches we need to try to commute everything else past: > > ABC|DF > > In general the lists on the left-hand side and right-hand side of the | > may be O(n), so each operation to reduce the list on the left by 1 is > O(n) and the whole job is O(n^2). > > In practice it may be that the list on the right doesn't grow too much, > but I actually tried this on the darcs repo itself a while back and it > did seem to be quite slow in practice.
Hey Ganesh thank you very much for the explanation. The problem is a lot clearer to me now. I wonder if this process could be optimized somehow. What darcs could at least do, I think, is to cache whether two patches commute or not. Darcs already has a global cache for patches, why not add a global cache for commutability/dependency information? For instance, every time I try to amend-record a patch from somewhere in the past, darcs seems to calculate some patch dependencies, so it can tell me whether the amend is possible. I have often wished for a graphical tool for viewing the dependencies (or maybe the opposite i.e. commutability) between patches. Such a tool could also contribute to the global cache, speeding up future requests. Just raw ideas, of course. Cheers Ben _______________________________________________ darcs-users mailing list darcs-users@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-users
