17

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...

Community
  • 1
  • 1
Mathias Dolidon
  • 3,775
  • 1
  • 20
  • 28
  • 1
    There is no need to seq n', whosLeft is already strict in n'. But you should compile with optimization. – augustss Aug 30 '11 at 22:02

1 Answers1

10

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.

sclv
  • 38,665
  • 7
  • 99
  • 204
  • 1
    Amazing. So I had completely missed the point, and it WAS simple after all :D Thank you very much sclv. That's an interesting trick to know. – Mathias Dolidon Aug 30 '11 at 18:37
  • Is this the sort of thing that the [deepseq](http://hackage.haskell.org/package/deepseq) package is good for? – Antal Spector-Zabusky Aug 30 '11 at 22:26
  • 1
    @Antal: I dislike using deepseq, because it's a blunt instrument. In this case for example, you just need to force the spine of the list. Deepseq forces the values as well. It's relatively cheap, since they're essentially already forced, but there is a minor cost, and if you multiply it by the length of the list and number of recursive calls it adds up. Deepseq is fine if you're in a hurry, but I think its better when possible to mix laziness and strictness in an optimal way, forcing where it makes sense operationally rather than indiscriminately. – sclv Aug 31 '11 at 05:01
  • @sclv: Makes sense. I just found the use of `length` odd, although I see why it works, so I cast around in my head for relevant-sounding abstractions I'd heard of. I haven't had occasion to use deepseq yet, but I'll keep that in mind for the future. – Antal Spector-Zabusky Aug 31 '11 at 06:11