Re: darcs cannot apply some patch bundles
Ben Franksen <benjamin.franksen <at> bessy.de>
2012-03-07 23:59:41 GMT
Ganesh Sittampalam wrote:
> On 05/03/2012 17:05, Owen Stephens wrote:
>> On 5 March 2012 16:18, Michael Hendricks <michael <at> ndrix.org
>> <mailto:michael <at> 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
>> 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
>> 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
> 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:
> 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:
> 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.
thank you very much for the explanation. The problem is a lot clearer to me
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.