Performance horrors

[Adrian Hey]

Neil Mitchell wrote:
> There are 12 instances in
> Hoogle, for example. If profiling later shows it to be a problem, I'd
> fix it - but I can't ever actually remember that being the case.
> Premature optimisation is the root of all evil.

I'm sure most of the community would agree with you, but I have to
say that if the consequence of this philosophy is horrors like this
in the standard libs, it should come as no surprise that Haskell has
a reputation for being "slow". What else is lurking there I wonder?
What's really bad is that the terrible performance isn't even
documented. It may be obvious, but it should still be documented.

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 :-)

> Having nubOrd is a great idea, I even proposed it previously, but
> people disagreed with me. Propose it and add it by all means.

Like I said, I'm not proposing it, as it doesn't seem to possible to
implement it efficiently using anything else in the standard libs.
You could do nubOrd (but not nubOrdBy) using Data.Set.

But there are 2 problems..
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.

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 :-)

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.

>> So could nub and nubBy be deprecated and an appropriate health warning
>> added to the Haddock?
> 
> No. They should say O(n^2) in the haddock documentation, but O(n^2) /= useless.

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.

Regards
--
Adrian Hey