I was reading an old post where Hal Daume III was analyzing Haskell performance for arrays. He proposed a test program which initializes an array, reverse it a number of times, and sums the contents. So I wrote a c++ reference program, a naive haskell version using lists and I also tweaked a little bit with the IOArray version, which should be the fastest. Unfortunately there is a huge performance gap. Haskell is slower by a factor of ten, even when using imperative style. C++ time ./arrayC 499 real 0m0.059s user 0m0.044s sys 0m0.008s HASKELL - IOUArray time ./IOMutArrayUnboxed 499 real 0m0.720s user 0m0.571s sys 0m0.019s HASKELL - list time ./list 499 real 0m1.845s user 0m1.770s sys 0m0.064s Can anyone suggest a faster version (using whatever data structure)? I like Haskell very much but I still have to figure out if the slowness of some code is due to my lack of knowledge or to some intrinsic limitation of the language (or libraries). By the way, sorry for the poor quality of the code, I am not a computer scientist. ------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------- //compile with //g++ -o arrayC arrayC.cc #include <stdio.h> #include < math.h> int main() { int array[500001]; for (int i=0;i<=500000;i++) { array[i]=(19*i+23)%911; } int tmp=0; for (int cnt=0;cnt<12;cnt++) { for (int x=0;x<=250000;x++) { tmp=array[500000-x]; array[500000-x]=array[x]; array[x]=tmp; } } int result=0; for (int i=0;i<=500000;i++) { result=result+(array[i]%911); } result=result % 911; printf("%d",result); return 0; } --------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------- -- compile with -- ghc --make -o list list.hs module Main where testArray = [ (19*i+23) `mod` 911 |i <- [0..500000]] sumArrayMod = foldl (\x y -> (y+x) `mod` 911) 0 main = print $ sumArrayMod$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ testArray --------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------- -- compile with -- ghc --make -o IOMutArrayUnboxed IOMutArrayUnboxed.hs module Main where import Monad import Data.Array.IO import Data.Array.MArray import Data.Array.Unboxed total, semiTotal ::Int total= 500000 semiTotal=250000 testArray :: IO (IOUArray Int Int) testArray = newListArray (0,total) [(19*i+23) `mod` 911 |i <- [0..total]] reverseArray :: IOUArray Int Int -> IO () reverseArray arr = mapM_ (\i -> do oldi <- readArray arr i oldj <- readArray arr (total-i) writeArray arr i oldj writeArray arr (total-i) oldi) [0..semiTotal] sumArrayMod :: IOUArray Int Int -> IO Int sumArrayMod arr = foldM (\s i -> do x <- readArray arr i return $!(s+x) `mod` 911) 0 [0..total] main::IO() main = testArray >>= \a -> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a
reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a
reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a
reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a
sumArrayMod a >>= print
--------------------------------------------------------------------------------------------------------- Federico
Frederico, On Tue, 2007-05-01 at 13:59 +0200, Federico Squartini wrote:
I was reading an old post where Hal Daume III was analyzing Haskell performance for arrays. He proposed a test program which initializes an array, reverse it a number of times, and sums the contents.
So I wrote a c++ reference program, a naive haskell version using lists and I also tweaked a little bit with the IOArray version, which should be the fastest. Unfortunately there is a huge performance gap. Haskell is slower by a factor of ten, even when using imperative style.
I think the version using lists is a bit unfair, since in C++ you don't re-allocate the array on the heap and the Haskell version gives you a very nice high-level abstraction of lists. With respect to the imperative version, I would suggest a) letting the program run for longer so you get more reliable timing. b) use a similar optimisations that we've done for a demo of modifying images in-situ for our Gtk2Hs library (in http://darcs.haskell.org/gtk2hs/demo/fastdraw/FastDraw.hs ): import Data.Array.Base ( unsafeWrite ) doFromTo 0 255 $ \y -> doFromTo 0 255 $ \x -> -- Here, writeArray was replaced with unsafeWrite. The latter does -- not check that the index is within bounds which has a tremendous -- effect on performance. -- writeArray pbData (2+x*chan+y*row) blue -- checked indexing unsafeWrite pbData (2+x*chan+y*row) blue -- unchecked indexing Here, doFromTo is much faster and using unsafeWrite instead of writeArray eliminates the array bound check, which is a big win again. Then again, it is questionable if you really want to do that kind of low-level programming in Haskell. Axel.
Of course I know that the list version is very unfair, but I wanted to see what was the trade off between elegance and speed. Regarding whether low level programming makes sense or not, I was just curious to see what are the limits of Haskell. Moreover there is not much literature on high performance Haskell programming (tricks like unsafeWrite), at least organized in a systematic and concise way. My original problem was writing a fast library for simple matrix computations (i.e. multiplication and inversion for small dense matrices). I have not been able to make GSLHaskell work with Lapack so far. :( Anyway here are the new versions and timings, I increased the number of times the vector is reversed, I also compiled everything with -O2. time ./arrayC 499 real 0m0.244s user 0m0.236s sys 0m0.005s time ./list 499 real 0m11.036s user 0m10.770s sys 0m0.118s time ./IOMutArrayUnboxed 499 real 0m2.573s user 0m2.408s sys 0m0.042s time ./IOMutUnbUnsafe 499 real 0m2.264s user 0m2.183s sys 0m0.025s ------------------------------ -------------------------------------------------- //compile with g++ -O2 -o arrayC arrayC.cc #include < stdio.h> #include <math.h> int main() { int array[500001]; for (int i=0;i<=500000;i++) { array[i]=(19*i+23)%911; } int tmp=0; for (int cnt=0;cnt<120;cnt++) { for (int x=0;x<=250000;x++) { tmp=array[500000-x]; array[500000-x]=array[x]; array[x]=tmp; } } int result=0; for (int i=0;i<=500000;i++) { result=result+(array[i]%911); } result=result % 911; printf("%d",result); return 0; } -------------------------------------------------------------------------------- -- compile with -- ghc -O2 --make -o list list.hs module Main where import Data.List testArray = [ (19*i+23) `mod` 911 |i <- [0..500000]] sumArrayMod = foldl (\x y -> (y+x) `mod` 911) 0 main = print $ sumArrayMod$ foldl (.) id (replicate 120 reverse) $testArray -------------------------------------------------------------------------------------- -- compile with -- ghc -O2 --make -o IOMutArrayUnboxed IOMutArrayUnboxed.hs module Main where import Monad import Data.Array.IO <http://data.array.io/> import Data.Array.MArray import Data.Array.Unboxed total, semiTotal ::Int total= 500000 <javascript:void(0)> semiTotal=250000 testArray :: IO (IOUArray Int Int) testArray = newListArray (0,total) [(19*i+23) `mod` 911 |i <- [0..total]] reverseArray :: IOUArray Int Int -> IO () reverseArray arr = mapM_ (\i -> do oldi <- readArray arr i oldj <- readArray arr (total-i) writeArray arr i oldj writeArray arr (total-i) oldi) [0..semiTotal] sumArrayMod :: IOUArray Int Int -> IO Int sumArrayMod arr = foldM (\s i -> do x <- readArray arr i return $!(s+x) `mod` 911) 0 [0..total] main::IO() main = testArray >>= \a -> sequence (replicate 120 $reverseArray a)>> sumArrayMod a >>= print ------------------------------------------------------------------------------------ -- compile with -- ghc -O2 --make -o IOMutUnbUnsafe IOMutUnbUnsafe.hs module Main where import Monad import Data.Array.IO <http://data.array.io/> import Data.Array.MArray import Data.Array.Unboxed import Data.Array.Base ( unsafeWrite, unsafeRead ) total, semiTotal ::Int total= 500000 <javascript:void(0)> semiTotal=250000 testArray :: IO (IOUArray Int Int) testArray = newListArray (0,total) [(19*i+23) `mod` 911 |i <- [0..total]] reverseArray :: IOUArray Int Int -> IO () reverseArray arr = mapM_ (\i -> do oldi <- unsafeRead arr i oldj <- unsafeRead arr (total-i) unsafeWrite arr i oldj unsafeWrite arr (total-i) oldi) [0..semiTotal] sumArrayMod :: IOUArray Int Int -> IO Int sumArrayMod arr = foldM (\s i -> do x <- unsafeRead arr i return $!(s+x) `mod` 911) 0 [0..total] main::IO() main = testArray >>= \a -> doFromTo 1 120 (\_ -> reverseArray a) >> sumArrayMod a >>= print {-# INLINE doFromTo #-} -- do the action for [from..to], ie it's inclusive. doFromTo :: Int -> Int -> (Int -> IO ()) -> IO () doFromTo from to action = let loop n | n > to = return () | otherwise = do action n loop (n+1) in loop from -----------------------------------------------------------------------
federico.squartini:
Of course I know that the list version is very unfair, but I wanted to see what was the trade off between elegance and speed. Regarding whether low level programming makes sense or not, I was just curious to see what are the limits of Haskell. Moreover there is not much literature on high performance Haskell programming (tricks like unsafeWrite), at least organized in a systematic and concise way. My original problem was writing a fast library for simple matrix computations (i.e. multiplication and inversion for small dense matrices). I have not been able to make GSLHaskell work with Lapack so far. :( Anyway here are the new versions and timings, I increased the number of times the vector is reversed, I also compiled everything with -O2.
Probably a good idea to use techniques from Data.ByteString (ie. use strict Ptr loops, and Foreign arrays), or techniques from the shootout, if you're chasing C speed. Good examples are: http://shootout.alioth.debian.org/gp4/benchmark.php?test=nsievebits&lang=ghc... (mutable bit arrays) http://shootout.alioth.debian.org/gp4/benchmark.php?test=nsieve&lang=ghc&id=... (mutable byte (foreign) arrays) http://shootout.alioth.debian.org/gp4/benchmark.php?test=spectralnorm&lang=g... (more mutable arrays) When I really really care about speed, I use Foreign.Marshal.Array Data.ByteString and apply ! patterns liberally, checking the Core output for inner loops. -O2 -optc-O2 -optc-march=pentium4 often helps. 1-4x C is around what you can best hope for. 10x says "still room for improvement" in my experience. -- Don
Thanks for the hints. It's a pity that (as far as I know) no one has written a tutorial on those techniques, because I think it would be appreciated. Some of them are quite involved and learning them just by reading code is very time consuming. Federico
On 5/1/07, Federico Squartini <federico.squartini@googlemail.com> wrote:
Thanks for the hints. It's a pity that (as far as I know) no one has written a tutorial on those techniques, because I think it would be appreciated. Some of them are quite involved and learning them just by reading code is very time consuming.
I personally recommend to people that if sections of your code are really performance-critical, you should consider writing them in a lower-level lanaguage like C and using FFI for access. P.S. I wonder if jhc could improve the output code? -- Taral <taralx@gmail.com> "You can't prove anything." -- Gödel's Incompetence Theorem
Federico Squartini wrote:
Thanks for the hints. It's a pity that (as far as I know) no one has written a tutorial on those techniques, because I think it would be appreciated. Some of them are quite involved and learning them just by reading code is very time consuming.
There's the Performance section of the Haskell wiki: http://haskell.org/haskellwiki/Performance Some of the techniques are described there, but by no means all. It's a good place to put knowledge that you acquire while doing these experiments, though. FWIW I vaguely recall there was a performance problem with initialising IOUArrays that we haven't got around to fixing yet. If you can narrow down the test case, then please submit a bug report. Cheers, Simon
Hello Federico, Tuesday, May 1, 2007, 7:23:45 PM, you wrote:
Thanks for the hints. It's a pity that (as far as I know) no one has written a tutorial on those techniques,
except for me :) - http://haskell.org/haskellwiki/Modern_array_libraries -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
Sorry, I was very silly! This is the correct version of the program using the doFromto loop. And it runs fast! I hope there are no further mistakes. Thanks Axel. time ./IOMutUnbUnsafe 499 real 0m0.708s user 0m0.573s sys 0m0.008s ----------------------------------------------------------------------------- -- compile with -- ghc --make -o IOMutUnbUnsafe IOMutUnbUnsafe.hs module Main where import Monad import Data.Array.IO import Data.Array.MArray import Data.Array.Unboxed import Data.Array.Base ( unsafeWrite, unsafeRead ) total, semiTotal ::Int total= 500000 semiTotal=250000 testArray :: IO (IOUArray Int Int) testArray = newListArray (0,total) [(19*i+23) `mod` 911 |i <- [0..total]] reverseArray :: IOUArray Int Int -> IO () reverseArray arr = doFromTo 0 semiTotal (\i -> do oldi <- unsafeRead arr i oldj <- unsafeRead arr (total-i) unsafeWrite arr i oldj unsafeWrite arr (total-i) oldi) sumArrayMod :: IOUArray Int Int -> IO Int sumArrayMod arr = foldM (\s i -> do x <- unsafeRead arr i return $!(s+x) `mod` 911) 0 [0..total] main::IO() main = testArray >>= \a -> doFromTo 1 120 (\_ -> reverseArray a) >> sumArrayMod a >>= print {-# INLINE doFromTo #-} -- do the action for [from..to], ie it's inclusive. doFromTo :: Int -> Int -> (Int -> IO ()) -> IO () doFromTo from to action = let loop n | n > to = return () | otherwise = do action n loop (n+1) in loop from ----------------------------------------------------------------------------------- Federico
federico.squartini:
Sorry, I was very silly!
This is the correct version of the program using the doFromto loop. And it runs fast! I hope there are no further mistakes. Thanks Axel.
time ./IOMutUnbUnsafe 499 real 0m0.708s user 0m0.573s sys 0m0.008s
Here's an improved version, using Foreign.Marshal.Array. I spent about 2 minutes inspecting the core, as well. Before, with your IOUArray version: $ time ./T 499 ./T 1.46s user 0.02s system 97% cpu 1.515 total with the new version: $ time ./S 499 ./S 1.15s user 0.01s system 99% cpu 1.168 total Here's the source, its more idiomatic high-perf Haskell, I'd argue. Cheers, Don ------------------------------------------------------------------------ {-# OPTIONS -O2 -optc-O -optc-march=pentium4 -fbang-patterns #-} import Control.Monad import Foreign.Marshal.Array import Foreign total :: Int total = 500001 type Arr = Ptr Int testArray :: IO Arr testArray = do u <- mallocArray total :: IO Arr forM_ [0 .. total] $ \i -> pokeElemOff u i ((19*i+23) `mod` 911) return u reverseArray :: Arr -> Int -> Int -> IO () reverseArray !p !i !j | i < j = do x <- peekElemOff p i y <- peekElemOff p j pokeElemOff p i y pokeElemOff p j x reverseArray p (i+1) (j-1) | otherwise = return () sumArrayMod :: Arr -> Int -> Int -> IO Int sumArrayMod !p !s !i | i < total = do x <- peekElemOff p i sumArrayMod p ((s + x) `rem` 911) (i+1) | otherwise = return s main :: IO () main = do a <- testArray replicateM_ 120 (reverseArray a 0 (total-1)) print =<< sumArrayMod a 0 0
Hello Donald, Wednesday, May 2, 2007, 7:38:25 AM, you wrote:
Here's an improved version, using Foreign.Marshal.Array. I spent about 2 minutes inspecting the core, as well.
i think that using just the "!" on array arguments should be enough. there is nothing magic in "usafeReadArray" calls, they should be the same as peek -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
On 5/1/07, Federico Squartini <federico.squartini@googlemail.com> wrote:
Moreover there is not much literature on high performance Haskell programming (tricks like unsafeWrite), at least organized in a systematic and concise way.
Look at: http://haskell.org/haskellwiki/Performance regards, Bas van Dijk
On Tue, May 01, 2007 at 01:59:01PM +0200, Federico Squartini wrote:
I was reading an old post where Hal Daume III was analyzing Haskell performance for arrays. He proposed a test program which initializes an array, reverse it a number of times, and sums the contents.
So I wrote a c++ reference program, a naive haskell version using lists and I also tweaked a little bit with the IOArray version, which should be the fastest. Unfortunately there is a huge performance gap. Haskell is slower by a factor of ten, even when using imperative style.
I'd recommend using -O2 or -O. GHC doesn't even try to generate fast code if you don't use them. Stefan
While scanning my Inbox I read 'fast' and 'array' in the context of functional programming. Well, of course SaC instantly came to my mind (what a surprise ;) ). So I did some measurements myself. I used your programs, except that I increased the array size by a factor of 10. For the C++ version I had to move the array to the heap and fix the order of function applications within the fold. Here are the timings: C++ 520 real 0m0.204s user 0m0.182s sys 0m0.023s Haskell IOArray (the extended version with unsafe accesses that was posted shortly after yours) 520 real 0m5.542s user 0m5.453s sys 0m0.068s Haskell Lists (just to be complete) 520 real 0m27.596s user 0m26.650s sys 0m0.870s and finally SaC Dimension: 0 Shape : < > 520 real 0m0.057s user 0m0.048s sys 0m0.000s The corresponding SaC program follows. I have compiled it with sac2c -O3. I used the current compiler from the website http://www.sac-home.org. use Structures : all; use StdIO : all; inline int sumMod( int a, int b) { return( (a + b) % 911); } inline int sumArrayMod( int[*] A) { res = with { ( shape(A) * 0 <= iv < shape(A)) : A[iv]; } : fold( sumMod, 0); return( res); } int main() { testArray = (19*iota(5000001)+23) % 911; print( sumArrayMod( reverse( reverse( reverse( reverse( reverse( reverse( reverse( reverse( reverse( reverse( reverse( reverse( reverse( reverse( reverse( reverse( testArray)))))))))))))))))); return( 0); } On 5/1/07, Federico Squartini <federico.squartini@googlemail.com> wrote:
I was reading an old post where Hal Daume III was analyzing Haskell performance for arrays. He proposed a test program which initializes an array, reverse it a number of times, and sums the contents.
So I wrote a c++ reference program, a naive haskell version using lists and I also tweaked a little bit with the IOArray version, which should be the fastest. Unfortunately there is a huge performance gap. Haskell is slower by a factor of ten, even when using imperative style.
C++ time ./arrayC 499 real 0m0.059s user 0m0.044s sys 0m0.008s
HASKELL - IOUArray time ./IOMutArrayUnboxed 499 real 0m0.720s user 0m0.571s sys 0m0.019s
HASKELL - list time ./list 499 real 0m1.845s user 0m1.770s sys 0m0.064s
Can anyone suggest a faster version (using whatever data structure)? I like Haskell very much but I still have to figure out if the slowness of some code is due to my lack of knowledge or to some intrinsic limitation of the language (or libraries).
By the way, sorry for the poor quality of the code, I am not a computer scientist.
-------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------- //compile with //g++ -o arrayC arrayC.cc #include <stdio.h> #include < math.h>
int main() { int array[500001];
for (int i=0;i<=500000;i++) { array[i]=(19*i+23)%911; } int tmp=0; for (int cnt=0;cnt<12;cnt++) { for (int x=0;x<=250000;x++) { tmp=array[500000-x]; array[500000-x]=array[x]; array[x]=tmp; } } int result=0; for (int i=0;i<=500000;i++) { result=result+(array[i]%911); } result=result % 911; printf("%d",result); return 0; }
---------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------- -- compile with -- ghc --make -o list list.hs module Main where
testArray = [ (19*i+23) `mod` 911 |i <- [0..500000]]
sumArrayMod = foldl (\x y -> (y+x) `mod` 911) 0
main = print $ sumArrayMod$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ reverse$ testArray
---------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------- -- compile with -- ghc --make -o IOMutArrayUnboxed IOMutArrayUnboxed.hs module Main where
import Monad import Data.Array.IO import Data.Array.MArray import Data.Array.Unboxed
total, semiTotal ::Int total= 500000 semiTotal=250000
testArray :: IO (IOUArray Int Int) testArray = newListArray (0,total) [(19*i+23) `mod` 911 |i <- [0..total]]
reverseArray :: IOUArray Int Int -> IO () reverseArray arr = mapM_ (\i -> do oldi <- readArray arr i oldj <- readArray arr (total-i) writeArray arr i oldj writeArray arr (total-i) oldi) [0..semiTotal]
sumArrayMod :: IOUArray Int Int -> IO Int sumArrayMod arr = foldM (\s i -> do x <- readArray arr i return $!(s+x) `mod` 911) 0 [0..total]
main::IO() main = testArray >>= \a -> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> reverseArray a >> sumArrayMod a >>= print
---------------------------------------------------------------------------------------------------------
Federico
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-- Stephan Herhut Centre for Computer Science and Informatics Research University of Hertfordshire
participants (9)
-
Axel Simon -
Bas van Dijk -
Bulat Ziganshin -
dons＠cse.unsw.edu.au -
Federico Squartini -
Simon Marlow -
Stefan O'Rear -
Stephan Herhut -
Taral