[darcs-users] Delta Debugging

David Roundy droundy at abridgegame.org
Tue May 25 11:24:24 UTC 2004

On Mon, May 24, 2004 at 09:34:44AM -0700, Kenneth Knowles wrote:
> On Mon, May 24, 2004 at 08:10:02AM -0400, David Roundy wrote:
> > One question is whether to use a clean copy for each test.  Trackdown
> > doesn't do this currently, which is nice because it means you only have
> > to recompile files that are modified from one version to the next, but
> > could lead to "interesting" histeresis effects if there are bugs in the
> > build system.
> I left this out, but there are optimizations inherent in the algorithm
> where you can leave some patches applied.  I implemented the ddmin
> algorithm instead of the dd+ because it has more of these opportunities.
> There are a lot of domain-specific optimization suggestions in the
> papers, and things like whether patches commute will really reduce the
> search space.
> However, this is never going to "fast" as you can imagine.  (I've never
> used trackdown, but I assume it is kind of a linear search of the same
> space).

Yeah, it's pretty primitive.  I just wrote it up quickly when I found
myself manually running "darcs unpull; make; sh test.sh" again and again in
a scratch repo.

> Oh, and in a previous post I said the worst-case was O(n log n) but I
> must have been thinking of something else.  If every single change is
> required to cause the failure, it takes O(n^2) tests, but that is a reall
> pathological case; if there is just one failure-inducing change then it
> is O(log n).

Hmmm.  Yes, that sounds like a nicely-scaling algorithm, and if it can be
implemented with compile reuse, it ought to be fast enough to be quite

> > So yes, there is interest in implementing such a feature in darcs... :)
> Excellent, this should be fun.


I recommend looking at the PatchChoices module.  It's a bit complicated,
but encapsulates a lot of the dependency and commutation issues that might
plague you.  It allows you to provide a sequence of patches, and then group
into three sets, "first", "middle" (i.e. undecided) and "last".  So the
"first" group will be the patches that are applied, unless you want to
default to applying all but those patches you've removed.  When you remove
a patch, any patches that depend on it are also added to the "last"
group--and all the commutations and stuff are done for you.
David Roundy

More information about the darcs-users mailing list