On Fri, Oct 03, 2008 at 12:26:42AM +0100, Eric Kow wrote: > Hi David, > > I'm hoping things get a little less crazy after 10 October. > Sorry for the delays.
Sorry for the further delay in getting back to you! > rewrite push_coalesce_patch to avoid calls to lengthFL. > ------------------------------------------------------- > > -sort_coalesceFL2 (x:>:xs) = push_coalesce_patch x $ sort_coalesceFL2 xs > > +sort_coalesceFL2 (x:>:xs) = either id id $ push_coalesce_patch x $ > > sort_coalesceFL2 xs > > Makes sense to me. I keep thinking the either id ids can be simplified > away, but nothing I come up with seems particularly satisfactory. > > Maybe returning (FL Prim C(x z), Bool), or alternatively passing down > some sort of accumulator. But I'm not convinced these are any better. > Anyway, it's a small matter. > > > + Just new' | IsEq <- nullP new' -> Right ps' > > + | otherwise -> Right $ either id id $ push_coalesce_patch > > new' ps' > > This makes sense because coalescing inherently shrinks things, so we > don't particularly care if we suceeded last time > > > + Right r -> Right $ either id id $ > > + push_coalesce_patch p' r > > And this too makes sense because we are checking if a 'previous' > push_coalesce_patch managed to shrink things down > > keep changepref patches from breaking the toSimple optimization. > ---------------------------------------------------------------- > The patch seems fine otherwise, I'm afraid I didn't get very far > understanding this the toSimple optimisation behind it. I'll just make > a note of my progress for future reference. > > Interestingly, I notice that there is a notion of 'simplicity' already > used by the pending code. > http://lists.osuosl.org/pipermail/darcs-users/2008-September/013810.html > Alas, these do not appear to be quite the same notion. > > I notice it is disabled with type witnesses. Is that just for purposes > of making life easier in the interim? In other words, the day type > witnesses become the default, we will also be using something like the > toSimple optimisation there? No, it's not quite the same. That pending optimization is unsafe, which is why it's disabled with type witnesses, and I probably we'll want to rewrite it to use unsafeCoerceP when we want to compile the entire code with type witnesses. > Anyway, the context is that we have a function > > mapPrimFL :: (forall x y. FL Prim C(x y) -> FL Prim C(x y)) > -> FL Prim C(w z) > -> FL Prim C(w z) > > whose purpose is not entirely clear to me. > So question 1: what is mapPrimFL for? Well, it's just an implementation of map, only for FL rather than lists. > For what it's worth, the code says we can treat mapPrimFL f x as being > equivalent to just f. > > The optimisation says something along the lines "if all the patches in > this list (x) are 'simple', then group together all the patches which > affect the same filename (in addition to applying f to all of them)". > Now all this indiscriminate re-ordering of patches could be scary, which > is why we do this check to make sure that all patches are simple first. > Our definition of simplicity is more lax than in the pending code: > - addir, rmfile, addfile [note the absence of rmdir] > - hunk, binary > - tokreplace > - changepref > The point is simply to assure that none of the patches involve a > file changing name midstream. > > And question 2: how is this grouping of patches which affect the > same file an aptimisation? Is it to help the coalescing code find > clumps faster? It changes the scaling from O(N^2) in the total number of changes to O(m n^2) where m is the number of files and is the number of changes per file. David _______________________________________________ darcs-users mailing list [email protected] http://lists.osuosl.org/mailman/listinfo/darcs-users
