Hard to understand Haskell memory allocation behaviour

Question

I stumbled upon Haskell and FP and got stunned by the possibilities. And the old maths nerd inside me had no trouble writing naive code for actual useful purposes. However inspite of all the reading I still really have a hard time understanding how not to hit some surprising performance bottlenecks.

So I write very short pieces of code with naive implementations and then try little changes to see how the performance responds. And here's one example I really can't get around to understand... I wrote this function that finds a solution to Josephus problem, on purpose with a naive list implementation.

m = 3
n = 3000
main = putStr $ "Soldier #" ++ (show $ whosLeft [1..n]) ++ " survived...\n"

whosLeft [lucky] = lucky
whosLeft soldiers = whosLeft $ take (length soldiers -1) $ drop m $ cycle soldiers

The latter runs in 190 ms, with a productivity of 63% according to the RTS.

Then the first thing I wanted to try was to remove the (length soldier -1) and replace it with a decrementing integer.

The running time leaped up to 900 ms and productivity down to 16%, and uses 47 times more memory than the simpler code above ! So I added strict evaluation, forced the Int type, tried things like removing the global variables and others, yet not to much avail. And I just can't understand this slowdown.

m = 3::Int
n = 3000::Int
main = putStr $ "Soldier #" ++ (show $ whosLeft n [1..n]) ++ " survived...\n"

whosLeft 1 [lucky] = lucky
whosLeft n' soldiers = n' `seq` left `seq` whosLeft (n'-1) left
                where left = take (n'-1) $ drop m $ cycle soldiers

I have sieved through performance related articles and posts, but I just don't seem to get a hint about this. Still being a Haskell noob I must be missing something big... How can this one added parameter (pre-chewed computation...) reduce the speed so much ?

PS : I know, if Josephus really had been with 3000 soldiers, they wouldn't have needed to suicide...

Answer 1

The first solution forces the whole spine of the soldiers list by taking its length. The second solution only forces (using seq) the head of the soldiers list. Replace the left in-between the seqs with a length left and you'll get your performance back.