[Haskell-cafe] Are there performant mutable Arrays in Haskell?

Don Stewart dons at galois.com
Thu Mar 19 12:57:22 EDT 2009


Brettschneider:
> Hey There, 
> 
> I am trying to write a hash-algorithm that in fact is working, but as you might have guessed the problem is the performance :) At the moment I am 40 times worse than the same implementation in C. 
> 
> My problem is, I need mutable arrays which are the heart of that hash.
> The algorithm is round-based and within each round I need the value of certain positions in that array. 
> 
> At the moment I work with an unboxed ST-Array at the crucial part 
> 
> --- snip ---
> test list = runSTUArray $ do
>     a_arr <- newListArray (0, 1752) list
> 
>     let round i = do
>             ain <- readArray a_arr (i-n)
>             at0 <- readArray a_arr (i-t0)
>             at1 <- readArray a_arr (i-t1)
>             at2 <- readArray a_arr (i-t2)
>             at3 <- readArray a_arr (i-t3)
>             at4 <- readArray a_arr (i-t4)
>             let li     = ls $ (i - n) mod 16
>                 ri     = rs $ (i - n) mod 16
> 
>             writeArray a_arr i $ (step4 li) 
>                                . (step3 ri) 
>                                . (step2 at1 at2 at3 at4)
>                                $ (step1 ain at0 i)
>     mapM_ round [n..(n+t-1)]
> 
>     return a_arr
> --- snap ---
> 
> I also played around with peekElemOff and pokeElemOff, but this isn't much faster. 
> It took ~30sec with my Haskell-Code while the C-implementation need only ~1sec.
> 
> Is there someone who may have some hints for me, what I can do better, or just 
> lead me in the right direction? :) 


You should be able to directly translate C into approximmately the same
kind of code using STUArrays.

Make sure to compile with -O2 and use unsafeRead/Write where you also do
unchecked read/writes in C.

An example:

    http://shootout.alioth.debian.org/gp4/benchmark.php?test=nsievebits&lang=ghc&id=1

-- Don


More information about the Haskell-Cafe mailing list