Array operations get slower inside loop

13 views
Skip to first unread message

Ethan Brooks

unread,
Sep 27, 2017, 10:25:35 PM9/27/17
to Haskell Repa
I have the following code:

#!/usr/bin/env stack
-- stack --resolver lts-8.12 script --optimize
{-# OPTIONS_GHC -Wall -Werror #-}

module Main
  ( main
  ) where

import qualified Data.Array.Repa as R
import Data.Array.Repa (Array, DIM1, (+^), D, Z(..), (:.)(..), (!))
import Data.Time
import Prelude hiding (sum)
import qualified System.Random as Random

n :: Int
n = round (1e6 :: Double)

addLargeRandomArrays :: Array D DIM1 Int -> Array D DIM1 Int
addLargeRandomArrays array = array +^ array'
  where
    i = array ! (Z :. 0) -- use the first element in the array as the random seed
    array' =
      R.fromListUnboxed (Z :. n) . take n $ Random.randoms (Random.mkStdGen i) -- random array

main :: IO ()
main = do
  start <- getCurrentTime
  loop start zeros
  where
    zeros = R.fromFunction (Z :. n) $ const 0 -- all zeros
    loop prev array = do
      let array' = addLargeRandomArrays array
      sum <- (! Z) <$> R.sumP array'
      now <- getCurrentTime
      print (diffUTCTime now prev, sum)
      loop now array'

For some reason, the execution time for each iteration of the loop keeps getting slower:

(1.032166806s,2800541561548865196)
(1.179660843s,-2028702759150123772)
(1.270479104s,4490058364035702598)
(1.438625015s,3665177830385523617)
(1.608387404s,7642130176018406570)
(1.708253711s,4711939266492313927)
(1.857334362s,-6870409763904305554)
(2.05369752s,-2099373253931113423)
(2.101834085s,-1376969400381574539)
(2.334134717s,2918951703665812958)
(2.530702978s,-1577758356363651853)
(2.606746963s,7608490931496987974)
(2.841643195s,3672299153820034522)
(2.988611585s,1029404858630974257)
(2.884691073s,-331399684382111615)
(3.240190308s,-8742327991973025592)
...

This is causing serious performance issues for one of my applications. Please help. Thank you.

Mike Ledger

unread,
Sep 28, 2017, 2:17:33 AM9/28/17
to Ethan Brooks, Haskell Repa
D is used for "delayed" arrays. Is it possible you're accumulating "delays" (thunks? I don't know about repa internals) in 'loop'?

I'd try force the array to the 'U' representation on each iteration or just start with a U array to begin with. See computeUnboxed{P,S}

Cheers,
Mike

--
You received this message because you are subscribed to the Google Groups "Haskell Repa" group.
To unsubscribe from this group and stop receiving emails from it, send an email to haskell-repa+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Alex Mason

unread,
Sep 28, 2017, 9:07:23 PM9/28/17
to Haskell Repa
I believe Mike is correct, by using delay representations, you're building lots of functions which look like (\i -> arr1 ! i + arr ! 2), then \i -> (arr1 ! 1 + arr2 !) + arr3 ! i) etc.This is because the definition of a Delayed array is:

instance Source D a where
 data Array D sh a
        = ADelayed  
                !sh 
                (sh -> a)

i.e., it is just a shape and a function which can return a value of type a for each index in that shape, so in your example you're building up a function whose complexity grows linearly. To fix it, you need to force the result into some form of manifest representation, such as Unboxed. You can do this by using:

addLargeRandomArrays :: Array D DIM1 Int -> Array U DIM1 Int
addLargeRandomArrays array = computeUnboxedS (array +^ array') 
                       -- or computeUnboxedP if you find parallelism helps at this array size
    ...

To get the most out of Repo, you should probably read the paper: http://benl.ouroborus.net/papers/2012-guiding/guiding-Haskell2012.pdf

Ethan Brooks

unread,
Sep 29, 2017, 2:35:59 PM9/29/17
to Mike Ledger, Haskell Repa
Ok. This makes perfect sense. Moreover, this really explains what the issue was in the original code. Thank you.

To unsubscribe from this group and stop receiving emails from it, send an email to haskell-repa...@googlegroups.com.
Reply all
Reply to author
Forward
0 new messages