[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