[darcs-users] State of new patch format (darcs 3)

[Ben Franksen]

On 25.08.24 16:33, Alexis Praga wrote:
> I was pleasantly surprised to see in the Changelog for 2.161
> "Preliminary UNSTABLE support for a new patch theory named
> "darcs-3". It looks quite exciting as "It also reduces the worst
> case asymptotic runtime for commutation and merging from exponential
> to merely quadratic in the number of patches involved." As this was
> in Augut 2020, what it the current state of affairs (and future
> plans) ? Is it possible to enable it ?

There is one main issue which is keeping us from making darcs-3 format
"official", and (I guess) also the default for new reposotories. This is
that we still do not have an acceptable solution for converting
repositories from the old formats. The requirement here is that this
should enable users to incrementally convert existing branches of their
project, something that we failed to do when introduing darcs-2 format
and which caused a lot of trouble for users.

We worked out a rough plan for this some time ago, one with a decent
compromise between usability and implementation effort. But it is still
not implemented, mostly because I didn't have the time and energy to
work on it, as I have been distracted by various issues over the last
few years.

Regarding the (worst case) quadratic behavior of merge in darcs-3, we do
have one test that actually measures runtimes
(tests/conflict-fight-failure.sh). At least in this particular scenario
the test shows that where darcs-1 and darcs-2 run into exponential
blow-up, darcs-3 indeed limits the increase in runtime to quadratic (in
the number of conflicting patches). This is not a proof for all possible
situations of course, but if you look at the implementation of the core
algorithms in src/Darcs/Patch/V3/Core.hs and take the time to understand
what is happening there, it is pretty obvious that resource usage must
be roughly quadratic in the number of patches involved.

BTW, some time ago I wrote (informal) proofs of "impossibility" for all
partial function calls in there. These proofs are embedded as comments
in the code and may or may not help to understand it; it's hard to tell
from my perspective.

> Also, I would be glad to update the FAQ about that as the latest
> update is from 2012 https://darcs.net/FAQ/Performance. So any
> information would be great, especially about the tests used and
> performance application. Documents about the theory would be nice
> too,

Updates of the wiki are always greatly appreciated. Please feel free to
make changes there, and don't hesitate to contact me personally if you
have more concrete questions. I am willing to explain some of the theory
(informally speaking), but I am not sure which level of abstraction or
detail is appropriate for the wiki.

Cheers
Ben