Euler #4 with bigger domain

Question

Consider the modified Euler problem #4 -- "Find the maximum palindromic number which is a product of two numbers between 100 and 9999."

rev :: Int -> Int
rev x = rev' x 0

rev' :: Int -> Int -> Int
rev' n r
    | n == 0 = r
    | otherwise = rev' (n `div` 10) (r * 10 + n `mod` 10)

pali :: Int -> Bool
pali x = x == rev x

main :: IO ()
main = print . maximum $ [ x*y | x <- nums, y <- nums, pali (x*y)]
    where
        nums = [9999,9998..100]

• This Haskell solution using -O2 and ghc 7.4.1 takes about 18 seconds.
• The similar C solution takes 0.1 second.

So Haskell is 180 times slower. What's wrong with my solution? I assume that this type of problems Haskell solves pretty well.

Appendix - analogue C solution:

#define A   100
#define B   9999
int ispali(int n)
{
    int n0=n, k=0;
    while (n>0) {
        k = 10*k + n%10;
        n /= 10;
    }
    return n0 == k;
}
int main(void)
{
    int max = 0;
    for (int i=B; i>=A; i--)
        for (int j=B; j>=A; j--) {
            if (i*j > max && ispali(i*j))
                max = i*j;      }
    printf("%d\n", max);
}

Answer 1

The similar C solution

That is a common misconception.

Lists are not loops!

And using lists to emulate loops has performance implications unless the compiler is able to eliminate the list from the code.

If you want to compare apples to apples, write the Haskell structure more or less equivalent to a loop, a tail recursive worker (with strict accumulator, though often the compiler is smart enough to figure out the strictness by itself).

Now let's take a more detailed look. For comparison, the C, compiled with gcc -O3, takes ~0.08 seconds here, the original Haskell, compiled with ghc -O2 takes ~20.3 seconds, with ghc -O2 -fllvm ~19.9 seconds. Pretty terrible.

One mistake in the original code is to use div and mod. The C code uses the equivalent of quot and rem, which map to the machine division instructions and are faster than div and mod. For positive arguments, the semantics are the same, so whenever you know that the arguments are always non-negative, never use div and mod.

Changing that, the running time becomes ~15.4 seconds when compiling with the native code generator, and ~2.9 seconds when compiling with the LLVM backend.

The difference is due to the fact that even the machine division operations are quite slow, and LLVM replaces the division/remainder with a multiply-and-shift operation. Doing the same by hand for the native backend (actually, a slightly better replacement taking advantage of the fact that I know the arguments will always be non-negative) brings its time down to ~2.2 seconds.

We're getting closer, but are still a far cry from the C.

That is due to the lists. The code still builds a list of palindromes (and traverses a list of Ints for the two factors).

Since lists cannot contain unboxed elements, that means there is a lot of boxing and unboxing going on in the code, that takes time.

So let us eliminate the lists, and take a look at the result of translating the C to Haskell:

module Main (main) where

a :: Int
a = 100

b :: Int
b = 9999

ispali :: Int -> Bool
ispali n = go n 0
  where
    go 0 acc = acc == n
    go m acc = go (m `quot` 10) (acc * 10 + (m `rem` 10))

maxpal :: Int
maxpal = go 0 b
  where
    go mx i
        | i < a = mx
        | otherwise = go (inner mx b) (i-1)
          where
            inner m j
                | j < a = m
                | p > m && ispali p = inner p (j-1)
                | otherwise = inner m (j-1)
                  where
                    p = i*j

main :: IO ()
main = print maxpal

The nested loop is translated to two nested worker functions, we use an accumulator to store the largest palindrome found so far. Compiled with ghc -O2, that runs in ~0.18 seconds, with ghc -O2 -fllvm it runs in ~0.14 seconds (yes, LLVM is better at optimising loops than the native code generator).

Still not quite there, but a factor of about 2 isn't too bad.

Maybe some find the following where the loop is abstracted out more readable, the generated core is for all intents and purposes identical (modulo a switch of argument order), and the performance of course the same:

module Main (main) where

a :: Int
a = 100

b :: Int
b = 9999

ispali :: Int -> Bool
ispali n = go n 0
  where
    go 0 acc = acc == n
    go m acc = go (m `quot` 10) (acc * 10 + (m `rem` 10))

downto :: Int -> Int -> a -> (a -> Int -> a) -> a
downto high low acc fun = go high acc
  where
    go i acc
        | i < low   = acc
        | otherwise = go (i-1) (fun acc i)

maxpal :: Int
maxpal = downto b a 0 $ \m i ->
            downto b a m $ \mx j ->
                let p = i*j
                in if mx < p && ispali p then p else mx

main :: IO ()
main = print maxpal

Answer 2

@axblount is at least partly right; the following modification makes the program run almost three times as fast as the original:

maxPalindrome = foldl f 0
  where f a x | x > a && pali x = x
              | otherwise       = a

main :: IO ()
main = print . maxPalindrome $ [x * y | x <- nums, y <- nums]
  where nums = [9999,9998..100]

That still leaves a factor 60 slowdown, though.

Answer 3

This is more true to what the C code is doing:

maxpali :: [Int] -> Int
maxpali xs = go xs 0
  where
    go [] m     = m
    go (x:xs) m = if x > m && pali(x) then go xs x else go xs m

main :: IO()
main = print . maxpali $ [ x*y | x <- nums, y <- nums ]
  where nums = [9999,9998..100]

On my box this takes 2 seconds vs .5 for the C version.