[darcs-users] darcs patch: rewrite push_coalesce_patch to avoid cal... (and 1 more)

David Roundy 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.
>   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


More information about the darcs-users mailing list