repa nested sequential warning
rickmurphy
I have been building experience with REPA with a solution to the first
genetic algorithm problem in Melanie Mitchell's "Intro to GAs." I am
using REPA 2.2.0.1 and GHCi 7.2.1.
REPA reports that the solution is "performing nested parallel
computation sequentially" and "You probably called the force function"
and recommends "use deepSeqArray."
I believe that I have identified three source of the nested parallel
computation. Before I invest time into more refactoring, I had a few
questions:
1. The documentation for the toVector and toList functions says they
will "convert an array ... forcing if required." What are the conditions
for "required?"
2. The documentation says that fromVector "creates a manifest array,"
but doesn't say whether fromList creates a manifest array. Does fromList
create a manifest array? Does the snippet below fully evaluate s?
-- |Create the population of chromosomes
pop :: IO (R.Array R.DIM2 Bool)
pop = do
r' <- r
-- (d >>= cs) >>= return . (R.fromList (R.Z R.:. r' R.:. r'))
cs' <- (d >>= cs)
let s = R.fromList (R.Z R.:. r' R.:. r') cs'
s `R.deepSeqArray` return s
3. The docs say withManifest forces an array, but only deepSeqArray
causes the array to be fully evaluated. The snippet below appears to
allow full evaluation of a slice. Does REPA 2.2 allow this? I've seen
reference to REPA 3. As an alternative, I assume I can just take this
slice into an array of that shape, then fully evaluate that.
-- |Select a chromosome from the population
sel :: Int -> IO [Bool]
sel x = do
v <- pop
let s = R.slice v (R.Z R.:. R.All R.:. ( x :: Int))
s `R.deepSeqArray` return (R.toList s)
--return (R.toList (R.slice v (R.Z R.:. R.All R.:. ( x ::
Int))))
4. Is toVector attempting to force a suspended evaluation in the snippet
below? Even if I were to refactor to deepSeqArray, I'm guessing I can't
use a slice as in #3 above, right?
-- |Candidate values (int) from each chromosome in the population,
vector
cval :: [Int] -> R.Array R.DIM2 Bool -> U.Vector Int
cval [] _ = U.empty
cval (x:xs) p = (U.cons (packInt $ R.toVector (R.slice p (R.Z R.:. R.All
R.:. (x::Int))))) (cval xs p)
5. In the snippet below cx call pop and cval. Assuming they've been
fully evaluated with deepSeqArray, I can exclude pop' as the source of
the "nested sequential" warning, right?
-- |create the next generation (2) from the parents by crossover
pop' :: IO (R.Array R.DIM2 Bool)
pop' = do
r' <- r
cx' <- cx
return (R.fromList (R.Z R.:. r' R.:. r') (concat (fst (unzip
(take (div r' 2) (repeat cx'))) ++ snd (unzip (take (div r' 2) (repeat
cx')))))
Thanks much in advance for the great work on REPA and the advice on
this. Here's a link to the complete source.
http://www.rickmurphy.org/G.hs
BTW - I haven't compiled this sample outside GHCi. I'm guessing GHCi
isn't the cause of the "nested sequential" warning, right?
--
Rick
Ben Lippmeier
On 28/01/2012, at 3:33 AM, rickmurphy wrote:
> Ben and All:
>
> I have been building experience with REPA with a solution to the first
> genetic algorithm problem in Melanie Mitchell's "Intro to GAs." I am
> using REPA 2.2.0.1 and GHCi 7.2.1.
You'd be much better off with the head version of Repa 3 straight from the repo. Using this should solve most of the problems below. I haven't pushed this to Hackage yet because I'm still working on the stencils support, but if you're not using that then it should be fine. I'm hoping to finish this in the next week or so.
> REPA reports that the solution is "performing nested parallel
> computation sequentially" and "You probably called the force function"
> and recommends "use deepSeqArray."
>
> I believe that I have identified three source of the nested parallel
> computation. Before I invest time into more refactoring, I had a few
> questions:
>
> 1. The documentation for the toVector and toList functions says they
> will "convert an array ... forcing if required." What are the conditions
> for "required?"
It'll be implicitly forced if it's not already a manifest array. In Repa3, whether an array is delayed or manifest is visible in the type, so this should be much less confusing in the new version.
> 2. The documentation says that fromVector "creates a manifest array,"
> but doesn't say whether fromList creates a manifest array. Does fromList
> create a manifest array?
From the user's point of view, fromList only creates a list.
> Does the snippet below fully evaluate s?
> -- |Create the population of chromosomes
> pop :: IO (R.Array R.DIM2 Bool)
> pop = do
> r' <- r
> -- (d >>= cs) >>= return . (R.fromList (R.Z R.:. r' R.:. r'))
> cs' <- (d >>= cs)
> let s = R.fromList (R.Z R.:. r' R.:. r') cs'
> s `R.deepSeqArray` return s
No, you need to use the 'force' function to actually compute the array. The deepSeqArray part is to avoid turning the 's' binding into a thunk, so the application of 'force' doesn't just get suspended via lazy evaluation.
For Repa2 use something like:
do let s = R.force $ R.fromList ..
s `R.deepSeqArray` return s
This paper: http://www.cse.unsw.edu.au/~benl/papers/repa/repa-icfp2010.pdf discusses why we need 'force'.
In Repa3 the 'force' function has been renamed to 'computeP', so see the Haddocks for that library. In Repa3 you should write the above code like:
do s <- now $ computeP $ R.fromList ...
In this style the 'now' function takes the place of 'deepSeqArray'.
> 3. The docs say withManifest forces an array, but only deepSeqArray
> causes the array to be fully evaluated. The snippet below appears to
> allow full evaluation of a slice.
There are two different notions of "evaluation" here, and two different notions of "force". It's really a disaster of terminology, which is why I renamed the "force" function to "computeP" in Repa 3.
The "force" *function* takes a delayed array and produces a manifest array. A delayed array is a description of how to compute an array, represented as a data type. A manifest array is real data (like integers) sitting in a flat buffer in memory. The "force" function takes the description of an array, computes all the elements, and produces a manifest array.
Sadly, if you just write:
let s = R.force $ R.fromList ...
then a Haskell program may suspend the application of the 'force' function due to lazy evaluation. Because of this, if you actually want an array to be computed at a particular point in the program you need to use 'deepSeqArray' as well. This insures that all thunks in the representation of the array have been "forced". (second meaning, I'm so sorry).
> Does REPA 2.2 allow this? I've seen
> reference to REPA 3.
You really want to use Repa3 instead.
> As an alternative, I assume I can just take this
> slice into an array of that shape, then fully evaluate that.
>
> -- |Select a chromosome from the population
> sel :: Int -> IO [Bool]
> sel x = do
> v <- pop
> let s = R.slice v (R.Z R.:. R.All R.:. ( x :: Int))
> s `R.deepSeqArray` return (R.toList s)
> --return (R.toList (R.slice v (R.Z R.:. R.All R.:. ( x ::
> Int))))
>
> 4. Is toVector attempting to force a suspended evaluation in the snippet
> below? Even if I were to refactor to deepSeqArray, I'm guessing I can't
> use a slice as in #3 above, right?
>
> -- |Candidate values (int) from each chromosome in the population,
> vector
> cval :: [Int] -> R.Array R.DIM2 Bool -> U.Vector Int
> cval [] _ = U.empty
> cval (x:xs) p = (U.cons (packInt $ R.toVector (R.slice p (R.Z R.:. R.All
> R.:. (x::Int))))) (cval xs p)
Yes, toVector will try to call the force function to compute the array in parallel. If you then try to compute the outer vector as part of another parallel computation you'll get the warning about nested arrays.
> Thanks much in advance for the great work on REPA and the advice on
> this.
Use Repa 3. It's got a much saner API.
> BTW - I haven't compiled this sample outside GHCi. I'm guessing GHCi
> isn't the cause of the "nested sequential" warning, right?
Running a program under GHCi should never affect the value of a Haskell program (not including IO actions and floating point error wibbles). If you get the warning in compiled code but not in GHCi (or vis-versa) then it's a bug.
Ben.