On 10/16/07, Alexander Staubo <[EMAIL PROTECTED]> wrote: > On 10/16/07, Hilary Oliver <[EMAIL PROTECTED]> wrote: > > We have used darcs at my workplace for a couple of years now, and it has > > proved to be an extremely useful tool. In my opinion darcs was the > > first system to make revision control so easy that only an idiot > > wouldn't do it (and I could never return to a centralized system). We > > have, however, run into the infamous "exponential time" merge problem > > twice, and when that happens it is effectively an insurmountable barrier > > to most users.
It's insurmountable, period; you have to go outside of Darcs. As far as I know, nobody has yet claimed that the merge problem isn't fundamentally exponential. Note that that doesn't keep the simplex algorithm from being the method of choice for linear programming in most cases even today. There are probably equally good algorithms for merging (sez the optimist in me). > Darcs has many good things going for it; development momentum is not > one of them, I am afraid. (If you're curious, nobody took up the > bounty offer.) I think that's unfair. There's plenty of activity going on, but mostly on routine programming stuff: better testing, refactoring, using new features of GHC to prepare for algorithmic revisions, etc. Combinatoric explosion is just a hard nut to crack. Again, look at linear programming, which has the advantage of a number of simple canonical examples of bad-to-worst case behavior. As people come to understand those examples, modern programs learn to avoid, mitigate, or at least warn about them. AFAIK, there are no simple examples of how to generate exponential merge problems. This might be something non-Haskell programmers could help with, in fact. If you do encounter an exponential merge, create partial repos both in history terms and in terms of the file tree dealt with, until you've reduced the problem to a "small" example. Then the patch theorists can work on exposing the features of the tree that lead to the exponential behavior. (This is a way-off-the-wall suggestion, you probably should wait for comments from David et al before spending time and effort on it!) _______________________________________________ darcs-users mailing list [email protected] http://lists.osuosl.org/mailman/listinfo/darcs-users
