Performance horrors

[Neil Mitchell]

Hi

> Has anybody even the remotest clue why darcs is (apparently) so slow?
> Maybe the community itself should share some of the blame for this. Like
> it wasn't obvious to me that the uses of nub I saw in darcs could rely
> on very short lists (<=1 element :-)

I'd be very surprised if it has anything to do with nub!

> You could do nubOrd (but not nubOrdBy) using Data.Set.

You can do nubOrdBy, just use the data type:

data Elem a = Elem (a -> a -> Ordering) a

> 1- This not only introduces a cyclic dependency between modules, but
> also packages. I'm not sure how well various compilers and cabal would
> deal with this between them, but I'm not optimistic.

Yep, that would be a pain.

> 2- Data.Set is not obviously the best underlying implementation (in
> fact it is obviously not the best underlying implementation, this and
> Data.Map etc really should be pensioned off to hackage along with the
> rest of the badly documented, unreliable, inefficient and unstable
> junk :-)

Data.Set is an interface, which you seem to think is not the fastest
implementation of that interface. If you can expose the same
interface, but improve the performance, and demonstrate that the
performance is better, then go for it! I'd support such a library
change proposal.

> So I still think they should be deprecated. It seems like the least bad
> option if we can agree that their use should be strongly discouraged.

Nope. I love nub. It's a beautiful function, which does exactly what
it says on the tin (albeit the tin is labelled in Latin).

> I would say it is if there are many obvious O(n.(log n)) or better
> implementations that can be used in in 99%+ of cases. I mean so
> obvious that users can quite easily roll their own in 3 lines
> of code or less.

None of them are Eq a => [a] -> [a].

If designing things from scratch I'd say its fine to have a debate
about whether you make nub require Eq or Ord, and then provide the
other as an option. But that time has passed.

Thanks

Neil