[Haskell-beginners] Why is this function that slow?

[Daniel Fischer]

On Thursday 29 July 2010 00:29:56, Andreas Flierl wrote:
> Hello everyone,
>
> I am a newbie to Haskell coming from a Java/Scala/Ruby background. As
> first few exercises, I was trying to translate my Scala solutions for
> some Project Euler [1] problems to Haskell. The function that solves
> problem 4 turns out to be quite slow (6s in Haskell as opposed to 400ms
> in Scala) and I cannot understand why. Here's the function:
>
> euler4 = solve 100 999
>   where solve min max = maximum palindromes
>           where palindromes    = [n | a <- range, b <- range, let n = a
> * b, isPalindrome n] range          = [max, max - 1 .. min]
>                 isPalindrome n = (n :: Int) == (read $ reverse $ show n)

Try

        isPalindrome n = let s = show n in s == reverse s

`read' is slow, though I didn't expect it to be that slow, to be honest.
The above change brought time down from ~5.1 secs to 0.22 secs here.

You can make it still faster if you make an arithmetic palindrome check 
instead of converting to String (0.1 secs).

With algorithmic improvements more can be gained.

>
> Using +RTS -sstderr I see that the allocation rate is 12M/s, which seems
> rather high to me. My guess would be that this is somehow related to
> lazy evaluation but all in all, I've got no real clue and would be
> thankful for any advice.

The problem (part of it at least) is that the Read instances for number 
types has been written more with elegance in mind than efficiency, 
apparently.
Thus when you want to read an Int, first a generic number, possibly 
including a fractional part and an exponent or represented in base 8 or 16 
is tried to be read.
That number is read as an Integer or a Rational (depending on the presence 
of a fractional part and an exponent [and its value]).
If the read produced an Integer, that is then converted to the appropriate 
number type [Int in this case].

That gives very elegant, but not very fast code.

>
> Thank you
> Andreas
>

Cheers,
Daniel