I've found the cause of slowness, but don't have time to fix it. The time is all spent in sift_for_pending, which is O(N^2) in the number of primitive patches being applied. We need to be very careful when modifying this, as if we don't, we'll get a return of the "buggy pending" errors.
There are two solutions (and eventually, ideally, we'd implement both). In the case of put and many applies/pushes, there are no local changes. In this case, unless there is a conflict, sift_for_pending always gives an empty patch. If we check first whether there was a conflict or local changes, we could skip the call to sift_for_pending. This would be optimal for these cases. The other, longer fix would be to implement an O(NlogN) commute. It's possible, but very tedious (and potentially very bug-prone), and only pays off for very large patches (such as this one). I say we should implement the first for now, and save the tricky commute for later. But I'm not going to implement either at the moment, so this bug is waiting for a volunteer... -- David Roundy http://www.darcs.net _______________________________________________ darcs-devel mailing list [email protected] http://www.abridgegame.org/cgi-bin/mailman/listinfo/darcs-devel
