[darcs-users] darcs patch: refactor Slurpy to common up name compon... (and 9 more)

[Ganesh Sittampalam]

On Wed, 29 Oct 2008, Jason Dagit wrote:

> I like that it's an overall win.  Whatsnew is a commonly used command
> that people have often complained is too slow, so I don't like hearing
> that is worse.  Do you have future plans for improving whatsnew?
>
> Oh, so whatsnew/get-lazy may not be representative of real use cases?
> Or the slow down is ignorable assuming it will scale better now?

Yes, I think it's an ok trade-off for fixing a quadratic blowup. Now I've 
dealt with all those I'll take a look at what else makes it slow.

>> To reiterate what I said before about the patches:
>>
>> The work is motivated by issue711, where darcs whatsnew -ls is
>> slow on a large tree. A simple experiment with a directory
>> with a large number of files in it showed quadratic blowups
>> in the slurpy code, and in speedy_commute. Here I'm trying to
>> address the slurpy code. The basic idea is to switch over
>> from storing the files in a directory in a list, to using
>> Data.Map.
>
> I think someone attempted to make a version of map with better complexity:
> http://hackage.haskell.org/trac/summer-of-code/ticket/1560
>
> I wonder if it's worth trying out.

It might be - should be reasonably easy to swap out. My gut feeling is 
that it won't be a big deal as filenames are fairly cheap to compare and 
not all that likely to have very long common prefixes (the slurpy 
structure already does something trie-like with the directory elements of 
the path to the files).

> I started to look at your patches but it's a lot of stuff and all in
> the Slurpy code (which I have a very weak grasp on).

I understand that quite well now so feel free to draw my attention to 
other patches in that area that I could review, as I don't always read the 
list in full.

Cheers,

Ganesh