3 ms·
From a complexity theory perspective, the Darcs patch application algorithm runs in time O(2^n) in the worst case, where n is the number of patches since the be
by pmeunier 7y ago
From a complexity theory perspective, the Darcs patch application algorithm runs in time O(2^n) in the worst case, where n is the number of patches since the beginning of the repository. That exponential merge happens in practice.
In Pijul, it is always O(log n + c), where c is the size of the largest conflict between the current repository and the patch you're trying to apply.
So, it is a double-exponential improvement in practical uses, even though you could totally make c = n for the sake of the argument.
The tradeoff is that Pijul doesn't handle the very cool (but rarely usable in practice) "darcs replace".
From an implementation perspective, Pijul is in Rust, relies on less external stuff than Darcs (for example no need for Putty on Windows), is available as a library.
edit: also, Pijul has branches, too, and Darcs doesn't. But branches are far from being as useful as in Git, and in fact most Git workflows use short-lived branches, which are essentially just patches in both Pijul and Darcs.
- carterschonwald 7y agoAre we talking about the Darcs version < 2 merge algorithm or the merge algorithm in current darcs?
- pmeunier 7y agoThe current darcs. Conflict fights are still exponential, and happen sometimes. I'm a really happy darcs user, but I was talking about complexity theory here, which considers worst cases. For the sake of completeness, I don't know the full story for the complexity of Darcs "in most cases", but I believe it to be linear in the size of history in the normal case (as it needs to try and commute all the patches with your new patch).
- gnufx 7y ago"Current" might mean the latest release or the current darcs.net repo with v3 patches, which I can't claim to have followed.
- gnufx 7y agoI can't find the details off-hand, but doesn't Darcs actually have the facility to define different types of patches as well as normal ones and "replace"? I don't know whether that's ever been done, but it could be useful, whether or not it's a worthwhile trade-off.