Slowdown by removing useless code (Project Euler 23)

Question

I'm trying to optimize my old code from Project Euler #23 and noticed some strange slowdown while removing useless comparisons in a function for list merging.

My code:

import Data.List
import Debug.Trace

limit = 28123

-- sum of all integers from 1 to n
summe :: Int -> Int
summe n = div (n*(n+1)) 2

-- all divisors of x excluding itself
divisors :: Int -> [Int]
divisors x = l1 ++ [x `div` z | z <- l1, z*z /= x, z /= 1]
               where m = floor $ sqrt $ fromIntegral x
                     l1 = [y | y <- [1..m] , mod x y == 0]

-- list of all abundant numbers
liste :: [Int]
liste = [x | x <- [12..limit] , x < sum (divisors x)]

-- nested list with sums of abundent numbers
sumliste :: [[Int]]
sumliste = [[x+y | x <- takeWhile (<=y) liste, x + y <= limit] | y <- liste]

-- reduced list
rsl :: [[Int]] -> [Int]
rsl (hl:[]) = hl
rsl (hl:l) = mergelists hl (rsl l)

-- build a sorted union of two sorted lists
mergelists :: [Int] -> [Int] -> [Int]
mergelists [] [] = []
mergelists [] b = b
mergelists a [] = a
mergelists as@(a:at) bs@(b:bt)
--  | a == b = a : mergelists at bt
--  | a > b = b : mergelists as bt
--  | a < b = a : mergelists at bs
  | a == b = if a == hl1
               then trace "1" l1
               else a : l1
  | a > b = if b == hl2
              then trace "2" l2
              else b : l2
  | a < b = if a == hl3
              then trace "3" l3
              else a : l3
                where l1 = mergelists at bt
                      hl1 = if null l1 then a + 1 else head l1
                      l2 = mergelists as bt
                      hl2 = head l2
                      l3 = mergelists at bs
                      hl3 = head l3

-- build the sum of target numbers by subtracting sum of nontarget numbers from all numbers
main = print $ (summe limit) - (sum $ rsl sumliste)

My problem is the function mergelists. The body of this functions contains some useless if clauses (as can be seen by the missing trace output) and could be refactored to the three commented lines. The problem with this is an increase of execution time from 3.4s to 5.8s what I can't understand.

Why is the shorter code slower?

Answer 1

As Thomas M. DuBuisson suggested, the problem has to do with the lack of strictness. The following code is a slight modification of the code that you have commented out, which uses the $! operator to ensure that the mergelists call is evaluated before forming the list.

mergelists :: [Int] -> [Int] -> [Int]
mergelists [] [] = []
mergelists [] b  = b
mergelists a  [] = a
mergelists as@(a:at) bs@(b:bt)
  | a == b = (a :) $! mergelists at bt
  | a >  b = (b :) $! mergelists as bt
  | a <  b = (a :) $! mergelists at bs

The function $! ensures if the result of (_ :) $! mergelists _ _ is evaluated, then mergelists _ _ must be evaluated as well. Thanks to the recursion, this implies that if the result of mergelists is evaluated, then the entire list must be evaluated.

In the slow version,

mergelists as@(a:at) bs@(b:bt)
  | a == b = a : mergelists at bt
  | a >  b = b : mergelists as bt
  | a <  b = a : mergelists at bs

you can inspect the first element of the result without evaluating the remainder of the list. The call to mergelists in the tail of the list is stored as an unevaluated thunk. This has various implications:

• This is good if you only need a small portion of the merged list, or if the inputs are infinitely long.
• On the other hand, if the lists aren't that big to begin with and/or you need all the elements eventually, this adds extra overhead due to the presence of the thunk. It also means that the garbage collector doesn't get to free any of the inputs since the thunks will retain references to them.

I don't understand exactly why it's slower for your particular problem though — perhaps someone more experienced can shed some light on this.

I've noticed that, at -O0, the "slow version" is actually the fastest of the three approaches, so I suspect that GHC was able to take advantage of the strictness and produce more optimized code.