How can I speed up my Haskell program (to the level of Python)

Question

I have the following toy program which cyclic shifts a vector and adds it to itself (under a mod). It does that for different shifts and high number of iterations (compared to the size of the vector). Program works, but its dog slow. I am still learning Haskell, so my question is: am I doing something wrong?

import Data.List (foldl')
import qualified Data.Sequence as Seq
import Data.Sequence (index, zipWith, Seq, (><), (<|), (|>))

seqSize = 100
numShifts = 10000 

cycleShift :: Integer -> Seq a -> Seq a
cycleShift s l = Seq.drop (fromInteger s) l >< Seq.take (fromInteger s) l

modAdd :: Seq Integer -> Seq Integer -> Seq Integer 
modAdd s t = Seq.zipWith (\ a b -> (a + b) `mod` 10^16) s t

step :: Seq Integer -> Integer -> Seq Integer
step l shift = modAdd l (cycleShift shift l)

allshifts = [i `mod` seqSize |i <- [1..numShifts]]
start = Seq.fromList (1 : [0 | i <- [1..(seqSize - 1)]])
end = foldl' step start allshifts

main :: IO ()
main = print (Seq.index end 0)

The same program in Python

seq_size = 100 
num_shifts = 10000

S = [i % seq_size for i in xrange(1, num_shifts + 1)]
ssums = [1] + [0 for i in range(seq_size - 1)]

for s in S: 
    shift = ssums[s:] + ssums[:s]  
    ssums = [(ssums[i] + shift[i]) % 10**16 for i in range(seq_size)]  

print ssums[0]

Here are the timings. Haskell: real 0m5.596s Python: real 0m0.551s

Python is not known for it's speed and yet is x10 times faster ?!?

You might want to check out Real World Haskell's performance tuning section first. It helped me learn some of the basics. book.realworldhaskell.org/read/profiling-and-optimization.html — gatoatigrado
– gatoatigrado, Commented Aug 9, 2011 at 23:20

porges · Accepted Answer · 2011-08-09 22:37:04Z

21

How are you running it?

I get 1.6 seconds for the Haskell version. (Compiled with ghc.exe -O2 seq.hs.)

Also, is there a reason you're using Seq? If I change it to use lists, I get 0.3 seconds execution time.

Here it is with lists:

import Data.List (foldl')

seqSize = 100
numShifts = 10000 

cycleShift s l = drop (fromInteger s) l ++ take (fromInteger s) l

modAdd s t = zipWith (\ a b -> (a + b) `mod` 10^16) s t

step l shift = modAdd l (cycleShift shift l)

allshifts = [i `mod` seqSize |i <- [1..numShifts]]
start = (1 : [0 | i <- [1..(seqSize - 1)]])
end = foldl' step start allshifts

main :: IO ()
main = print (end !! 0)

answered Aug 9, 2011 at 22:37

porges

30.7k4 gold badges88 silver badges115 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Axman6 Over a year ago

Using rem instead of mod should also provide some speedup.

porges Over a year ago

I tested it and it didn't make a difference.

fuz · Accepted Answer · 2011-08-10 09:29:03Z

20

Use plain lists. They are heavily optimized. Using Data.Vector is even faster.
Use rem instead of mod
Avoid unnecessary work. (see cycleShift. Before, you splitted the list twice)
Use Int instead of Integer if your calculation may not exceed the bounds. The former is a hardware int, while the later is arbitrary precision, but emulated via software.

Result: 3.6 secs to 0.5 secs. More is probably possible.

Code:

import Data.List (foldl')
import Data.Tuple

seqSize, numShifts :: Int
seqSize = 100

numShifts = 10000 

cycleShift :: Int -> [a] -> [a]
cycleShift s = uncurry (++) . swap . splitAt s

modAdd :: [Int] -> [Int] -> [Int]
modAdd = zipWith (\ a b -> (a + b) `rem` 10^16)

step :: [Int] -> Int -> [Int]
step l shift = modAdd l (cycleShift shift l)

allshifts = map (`rem` seqSize) [1..numShifts]
start = 1 : replicate (seqSize - 1) 0
end = foldl' step start allshifts

main :: IO ()
main = print (head end)

Edit

It gets even faster by using Data.Vector. I get around 0.4 sec on my machine using this code:

import Data.List (foldl')
import Data.Tuple

import Data.Vector (Vector)
import qualified Data.Vector as V

seqSize, numShifts :: Int
seqSize = 100

numShifts = 10000 

cycleShift :: Int -> Vector a -> Vector a
cycleShift s = uncurry (V.++) . swap . V.splitAt s

modAdd :: Vector Int -> Vector Int -> Vector Int
modAdd = V.zipWith (\ a b -> (a + b) `rem` 10^16)

step :: Vector Int -> Int -> Vector Int
step l shift = modAdd l (cycleShift shift l)

allshifts = map (`rem` seqSize) [1..numShifts]
start = 1 `V.cons` V.replicate (seqSize - 1) 0
end = foldl' step start allshifts

main :: IO ()
main = print (V.head end)

Edit 2

Using Data.Vector.Unboxed (Just change the imports and fix up the signatures), the runtime drops down to 0.074 secs. But the results are only correct, if an Int has 64 bit. It may also be that fast using Int64 though.

edited Aug 10, 2011 at 9:29

answered Aug 9, 2011 at 22:34

fuz

94.8k27 gold badges217 silver badges392 bronze badges

11 Comments

chrisdb Over a year ago

There's a slight problem here in that a Haskell Int is officially only guaranteed to cover the range [ - 2^29, 2^29 - 1]. Note that 10^16 is greater than 2^29, so you could easily get Int wraparound happening in this code if that rem actually ever kicks in.

fuz Over a year ago

@chrisdb Sorry. GHC uses all 32 bits on x86 and 64 bits on x64 so I get no overflow. IMHO it changes not too much if you switch back to Integer.

chrisdb Over a year ago

I agree that an Int64 (or just Int on x64 if that's what GHC uses) is OK. An Int32 won't be in the general case (2^31 < 10^16, so wraparound happens before you hit the rem), so you'll just silently get the wrong answer. I'm not sure if it's an issue for numShifts = 10000 and seqSize = 100, so for this particular case you might get the right answer anyway.

porges Over a year ago

Just a note: The first two changes make no difference for me. I get exactly the same results after as before.

porges Over a year ago

And I get 0.15 for Vector version (twice as fast as lists) and 0.016 for Int32-unboxed version (but the wrong answer ;)).

|

mcandre · Accepted Answer · 2011-08-14 19:50:22Z

2

Ensure the Haskell code is compiled and the resulting executable is being timed, not the interpreted version of the code.

TheGeekStuff

answered Aug 14, 2011 at 19:50

mcandre

25k21 gold badges93 silver badges150 bronze badges

Collectives™ on Stack Overflow

How can I speed up my Haskell program (to the level of Python)

3 Answers 3

2 Comments

Edit

Edit 2

11 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Edit

Edit 2

11 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related