[darcs-users] darcs patch: rewrite push_coalesce_patch to avoid cal... (and 1 more)
droundy at darcs.net
Sat Oct 18 11:20:15 UTC 2008
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.
> 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
> 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.
More information about the darcs-users