Is Python faster than compiled Haskell?

Question

Please feel free to flag this as irrelevant if you think it does not belong here.

I have a simple script written in both Python and Haskell. It reads a file with an integer consisting of 1,000,000 integers separated by a newline, analyzes this file in a list of integers, quickly sorts it, and then writes it to another file, sorted. This file has the same format as unsorted. Plain.

Here is the Haskell:

quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) where lesser = filter (< p) xs greater = filter (>= p) xs main = do file <- readFile "data" let un = lines file let f = map (\x -> read x::Int ) un let done = quicksort f writeFile "sorted" (unlines (map show done)) 

And here is Python:

 def qs(ar): if len(ar) == 0: return ar p = ar[0] return qs([i for i in ar if i < p]) + [p] + qs([i for i in ar if i > p]) def read_file(fn): f = open(fn) data = f.read() f.close() return data def write_file(fn, data): f = open('sorted', 'w') f.write(data) f.close() def main(): data = read_file('data') lines = data.split('\n') lines = [int(l) for l in lines] done = qs(lines) done = [str(l) for l in done] write_file('sorted', "\n".join(done)) if __name__ == '__main__': main() 

Very simple. Now I will compile Haskell code with

 $ ghc -O2 --make quick.hs 

And I am the time when these two:

 $ time ./quick $ time python qs.py 

Results:

Haskell:

 real 0m10.820s user 0m10.656s sys 0m0.154s 

Python:

 real 0m9.888s user 0m9.669s sys 0m0.203s 

How can Python be faster than native Haskell code?

thank

EDIT

• Python Version: 2.7.1
• GHC Version: 7.0.4
• Mac OSX 10.7.3
• 2.4GHz Intel Core i5

List Generated

 from random import shuffle a = [str(a) for a in xrange(0, 1000*1000)] shuffle(a) s = "\n".join(a) f = open('data', 'w') f.write(s) f.close() 

Thus, all numbers are unique.

Answer 1

In short, do not use read . Replace read a function such as:

 import Numeric fastRead :: String -> Int fastRead s = case readDec s of [(n, "")] -> n 

I get pretty good acceleration:

 ~/programming% time ./test.slow ./test.slow 9.82s user 0.06s system 99% cpu 9.901 total ~/programming% time ./test.fast ./test.fast 6.99s user 0.05s system 99% cpu 7.064 total ~/programming% time ./test.bytestring ./test.bytestring 4.94s user 0.06s system 99% cpu 5.026 total 

Just for fun, the above results include a version that uses ByteString (and therefore does not pass the "ready for the 21st century" test, completely ignoring the file encoding problem) for ULTIMATE BARE-METAL SPEED. It also has several other differences; for example, it is sent to the standard library sort function. Full code below.

 import qualified Data.ByteString as BS import Data.Attoparsec.ByteString.Char8 import Control.Applicative import Data.List parser = many (decimal <* char '\n') reallyParse p bs = case parse p bs of Partial f -> f BS.empty v -> v main = do numbers <- BS.readFile "data" case reallyParse parser numbers of Done tr | BS.null t -> writeFile "sorted" . unlines . map show . sort $ r 

Answer 2

Haskell Original Code

There are two problems in the Haskell version:

• You are using an IO string that builds linked character lists
• You are using non-quicksort, which looks like quicksort.

This program takes 18.7 seconds to work on my 2.5 GHz Intel Core2 laptop. (GHC 7.4 using -O2)

Daniel ByteString Version

This has improved a lot, but note that it still uses inefficient inline merge sort.

Its version takes 8.1 seconds (and does not process negative numbers, but this is no longer a problem for this study).

Note

The following packages are used in this answer: Vector , attoparsec , text and vector-algorithms . Also note that my device runs a free version using timsort for 2.8 seconds (editing: and 2 seconds using pypy).

Text version

I ripped off the Daniel version, translated it into Text (so that it handles different encodings) and added a better sort using mutable Vector in the ST monad:

 import Data.Attoparsec.Text.Lazy import qualified Data.Text.Lazy as T import qualified Data.Text.Lazy.IO as TIO import qualified Data.Vector.Unboxed as V import qualified Data.Vector.Algorithms.Intro as I import Control.Applicative import Control.Monad.ST import System.Environment (getArgs) parser = many (decimal <* char '\n') main = do numbers <- TIO.readFile =<< fmap head getArgs case parse parser numbers of Done tr | T.null t -> writeFile "sorted" . unlines . map show . vsort $ r x -> error $ Prelude.take 40 (show x) vsort :: [Int] -> [Int] vsort l = runST $ do let v = V.fromList l m <- V.unsafeThaw v I.sort m v' <- V.unsafeFreeze m return (V.toList v') 

This is done in 4 seconds (and also does not process negatives)

Return to Bytestring

So, now we know that we can make a more general program faster, how to quickly make an ASCii version? No problems!

 import qualified Data.ByteString.Lazy.Char8 as BS import Data.Attoparsec.ByteString.Lazy (parse, Result(..)) import Data.Attoparsec.ByteString.Char8 (decimal, char) import Control.Applicative ((<*), many) import qualified Data.Vector.Unboxed as V import qualified Data.Vector.Algorithms.Intro as I import Control.Monad.ST parser = many (decimal <* char '\n') main = do numbers <- BS.readFile "rands" case parse parser numbers of Done tr | BS.null t -> writeFile "sorted" . unlines . map show . vsort $ r vsort :: [Int] -> [Int] vsort l = runST $ do let v = V.fromList l m <- V.unsafeThaw v I.sort m v' <- V.unsafeFreeze m return (V.toList v') 

This is done in 2.3 seconds.

Create a test file

Just in case anyone is interested, my test file was created:

 import Control.Monad.CryptoRandom import Crypto.Random main = do g <- newGenIO :: IO SystemRandom let rs = Prelude.take (2^20) (map abs (crandoms g) :: [Int]) writeFile "rands" (unlines $ map show rs) 

If you're wondering why vsort n't packaged in a simpler form in Hackage ... so do I.

Answer 3

More Pythonista than Haskellite, but I'll take a hit:

• Your measured runtime has quite a bit of overhead just by looking at and writing files, which is probably very similar to two programs. Also, be careful that you have warmed up the cache for both programs.

• Most of your time is spent copying lists and snippets of lists. Python list operations are highly optimized, being one of the most frequently used parts of the language, and are also usually quite effective at compiling lists, spending most of their time in C space inside the Python interpreter. In Python, there are not many things that are slow in Python, but in static languages, such as searching for attributes on object instances, are growing fast.

• Your Python implementation throws numbers that are equal to the axis, so by the end it can sort fewer elements, which gives it an obvious advantage. (If there are no duplicates in the data sorting in this dataset, this is not a problem.) Correcting this error probably requires creating another copy of most of the list in each qs() call, which will slow down Python a bit more.

• You do not specify which version of Python you are using. If you are using 2.x, you can probably get Haskell to beat Python just by switching to Python 3.x. :-)

I'm not too surprised that the two languages ​​here are mostly neck and neck (a 10% difference is not noticeable). Using C as a benchmark for performance, Haskell loses a certain performance due to its lazy functional nature, while Python loses a certain performance due to the interpreted language. A decent match.

Since Daniel Wagner published an optimized version of Haskell using the built-in sort , here is a similarly optimized version of Python using list.sort() :

 mylist = [int(x.strip()) for x in open("data")] mylist.sort() open("sorted", "w").write("\n".join(str(x) for x in mylist)) 

3.5 seconds on my machine, about 9 for the source code. Quite a lot of neck and neck with optimized Haskell. Reason: He spends most of his time in C-programmed libraries. In addition, TimSort (the sorting used in Python) is a beast.

Answer 4

This is after that fact, but I think most of the problem is with writing Haskell. The next module is pretty primitive - you need to use builders, probably, and, of course, avoid ridiculous roundtrip through String to show - but it is simple and noticeably better than pypy with impeccably improved python and better than 2 and 4 seconds. Haskell modules elsewhere on this page (it surprised me how many lists they used, so I did a couple more revolutions of the crank.)

 $ time aa.hs real 0m0.709s $ time pypy aa.py real 0m1.818s $ time python aa.py real 0m3.103s 

I use the class recommended for unboxed vectors from vector algorithms. Using Data.Vector.Unbox in one form or another is clearly the standard, naive way to do such things - this is the new Data.List (for Int, Double, etc.). Everything except sort is annoying IO Management, which I think will still be greatly improved, in particular at the end of the recording. Reading and sorting together takes about 0.2 seconds, as you can see, asking him to print what is on a bunch of indices, instead of writing to a file, so twice as much time is spent on writing, as on anything else. If pypy spends most of his time using timsort or something like that, then it seems that sorting itself is definitely much better in Haskell, and just as simple - if you can just take your hands on the damn vector ...

I'm not sure why there are no convenient functions for reading and writing vectors of unrelated things from natural formats - if it were, it would be three lines long and avoid String and be much faster, but maybe I just did not see them.

 import qualified Data.ByteString.Lazy.Char8 as BL import qualified Data.ByteString.Char8 as B import qualified Data.Vector.Unboxed.Mutable as M import qualified Data.Vector.Unboxed as V import Data.Vector.Algorithms.Radix import System.IO main = do unsorted <- fmap toInts (BL.readFile "data") vec <- V.thaw unsorted sorted <- sort vec >> V.freeze vec withFile "sorted" WriteMode $ \handle -> V.mapM_ (writeLine handle) sorted writeLine :: Handle -> Int -> IO () writeLine h int = B.hPut h $ B.pack (show int ++ "\n") toInts :: BL.ByteString -> V.Vector Int toInts bs = V.unfoldr oneInt (BL.cons ' ' bs) oneInt :: BL.ByteString -> Maybe (Int, BL.ByteString) oneInt bs = if BL.null bs then Nothing else let bstail = BL.tail bs in if BL.null bstail then Nothing else BL.readInt bstail 

Answer 5

To follow the interesting @kindall answer, these timings depend both on the python / Haskell implementation you are using, and on the hardware configuration on which you run the tests, and the implementation of the algorithm in both languages.

Nevertheless, we can try to get some good recommendations regarding the relative performance of one language implementation compared to another or from one language to another. With famous alorites like qsort, this is a good start.

To illustrate the python / python comparison, I just tested your script on CPython 2.7.3 and PyPy 1.8 on the same machine:

• CPython: ~ 8s
• PyPy: ~ 2.5s

This shows that there may be room for better language implementation, possibly compiled. Haskell does not at best interpret and compile your corresponding code. If you are looking for speed in Python, also consider switching to pypy if necessary, and if your coverage code allows you to do this.

Answer 6

I noticed some problem that everyone else did not notice for some reason; you have haskell and python code. (please tell me if this has been fixed in automatic optimizations, I don't know anything about optimizations). for this I will demonstrate in haskell. in your code you define smaller and larger lists, for example:

 where lesser = filter (<p) xs greater = filter (>=p) xs 

this is bad because you are comparing with p each element in xs twice, once to get a smaller list and again to get a larger list. this (theoretically, I did not check the time) makes your variety twice as many comparisons; this is a catastrophe. instead, you should create a function that splits the list into two lists using a predicate, so that

 split f xs 

equivalently

 (filter f xs, filter (not.f) xs) 

using this function, you will only need to compare each element in the list once to find out which side of the tuple to put it on.
ok let's do this:

 where split :: (a -> Bool) -> [a] -> ([a], [a]) split _ [] = ([],[]) split f (x:xs) |fx = let (a,b) = split f xs in (x:a,b) |otherwise = let (a,b) = split f xs in (a,x:b) 

now allows you to replace the smaller / larger generator with

 let (lesser, greater) = split (p>) xs in (insert function here) 

full code:

 quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = let (lesser, greater) = splitf (p>) xs in (quicksort lesser) ++ [p] ++ (quicksort greater) where splitf :: (a -> Bool) -> [a] -> ([a], [a]) splitf _ [] = ([],[]) splitf f (x:xs) |fx = let (a,b) = splitf f xs in (x:a,b) |otherwise = let (a,b) = splitf f xs in (a,x:b) 

for some reason I cannot change the role of getter / lesser in where clauses, so I had to do this in let clauses. also, if it's not a recursive tail, let me know and fix it for me (I don't know yet how the tailing dump works)

you should now do the same for python code. I do not know python, so I can not do this for you.

EDIT: in fact, such a function already exists in a Data.List, called a section. Please note that this proves the need for such a function, because otherwise it will not be defined. this compresses the code:

 quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = let (lesser, greater) = partition (p>) xs in (quicksort lesser) ++ [p] ++ (quicksort greater) 

Answer 7

Python is really optimized for this kind of thing. I suspect Haskell doesn't. Here's a similar question that gives some very good answers.