[darcs-users] new feature in HEAD: exponential backoff test strategy

Guillaume Hoffmann guillaumh at gmail.com
Sat May 12 23:03:17 UTC 2012


Hi everyone,

First, for those who have missed it, since darcs 2.8 all code testing
features of darcs belong to the command "darcs test". Without flags,
"darcs test" runs a test on the latest recorded state of the
repository. However, flags --trackdown and --bisect look for the most
recent recorded version passing a given test.

We already know how --trackdown  and --bisect work: --trackdown runs a
test agains the last recorded version, then the last version minus one
patch, then minus two patches... until finding a passing test.
--bisect sort of does the same by jumping back and forth in the
history by dichotomy.  See http://wiki.darcs.net/Using/Trackdown for
more information and unusually friendly drawings :-)

So, the new interesting feature in HEAD is the exponential backoff
strategy, implemented by Michael Hendricks.  As explained by Michael
himself on the bug tracker:

----8<----
This patch series defines a new "darcs test" search strategy named
--backoff.  It's aimed at finding regressions which are closer to the
head than to the middle of the repository.  Under these conditions, in
the screened repository, it performs between 30 and 70% faster than
bisect.  It will perform relatively better on repositories with more
patches.

The search strategy starts by unapplying 4 patches (chosen to match
the break-even point with linear search).  If the test fails, it
unapplies 8 more patches and tests again.  On each test failure, it
removes twice the number of patches as before.  Once the test passes,
it bisects the patches it just skipped.
---->8----

I think it's quite cool, and I'm not aware of any other VCS that have
this kind of test strategy.

Guillaume


More information about the darcs-users mailing list