[darcs-users] darcs for /etc very slow
David Roundy
droundy at abridgegame.org
Thu Dec 16 00:49:33 UTC 2004
On Wed, Dec 15, 2004 at 08:55:24PM +0100, Karel Gardas wrote:
> On Wed, 15 Dec 2004, Phil Frost wrote:
> > I have encountered times where 'darcs record' takes hours before I
> > interrupt it, but 'darcs record -a' works in under 30 s. Saying 'a' in
> > the interactive prompt is aparently not the same as the '-a' option.
>
> You are right! I've seen also the same behaviour, but haven't tried to
> debug it more...
It's because when run interactively darcs sorts the changes, which it
doesn't bother with when run with --all. The sorting unfortunately is an
O(N^2) operation. We can't use an O(NlogN) sort because reordering patches
in general requires commutation. Actually, for the common case (many
different files with a few changes to each, and few renames) we *could*
write an O(NlogN) sort, but it would be a pain, and would require that we
be able to bin patches in sets that trivially commute (i.e. AB <-> BA, no
modification involved).
At one time I put a fair amount of thought into this, but then ended up
just reducing the prefactors, which helped a lot. Of course, eventually
the O(n^2) is going to catch up with you...
If we did this O(nlogn) stuff right, it would also be possible to speed up
certain commutations, but that would be even more of a pain, and nowdays
the commutations that most commonly cause slowdown trouble are
conflict-related commutations where this binning trick wouldn't help.
--
David Roundy
http://www.darcs.net
More information about the darcs-users
mailing list