One observation is that you're doing a lot of redundant Bool -> Int conversion.

 

As you iterate across the array in fillArray, the rule you are using for the next cell is almost entirely determined by the rule you are using for the current cell; lop off the top bit, shift left by one, and add the new bit.  Instead, you're recalculating the entire rule at that point.

 

Sadly, (at least as of GHC 6.6.1) the performance of the operations in Data.Bits was horrendous, and any time I wanted to use them for performance, I ended up going through the FFI and writing C code.  I haven't had a chance to test this on GHC 6.8.

 

In this case, that might not be so bad, however.  You can probably write a 10-20 line C function that implements "fill" and call it via the FFI.

 

Alternatively, you could create a new rule table which maps a rule and a bool into a new rule index.  This would only be twice the size of the rule table, and you can index that way.

 

Also, what stops getRule from going off the end of the array?  I didn't see anything that prevented that in the code, and you're using unsafeAt, which seems like a potential bug.

 

  -- ryan

 

On 11/13/07, Justin Bailey <jgbailey@gmail.com> wrote:

I've been working on a program over the last few days to evolve
cellular automata rules using a genetic algorithm. Luckily, this email
has nothing to do with CAs but everything to do with Haskell
performance.

For those who don't know, a CA is represented as a row of cells, where
each can be either black (on/1) or white (off/0). A CA is "run" by
generating a new row from the previous row according to some rule.
Each cell is examined in turn and based on the state of it's neighbors
and itself, a new cell in the next row is generated that is either
black or white.

The function below is my "step" function that generates this new row.
It's at the heart of my program and where all  the execution time is
spent. In this scenario it's executed around 800 million times. On my
relatively modest desktop using GHC 6.8.1, the program takes about 30
seconds to run. Here's the function, with some of the type
declarations:

data Rule = Rule { ruleWidth :: Int, rules :: UArray Int Bool }
data Ring = Ring { currIdx :: !Int, vals :: (UArray Int Bool), lower,
upper, size:: !Int }
type CA = Ring

currR :: Int -> Ring -> Bool
currR amt r@(Ring curr arr l u s) = unsafeAt arr ((curr + amt) `mod` s)

stepWithUArray :: Int -> Rule -> CA -> CA
stepWithUArray rowLen rule@(Rule width rules) row =
let upper = rowLen - 1
     getRule currIdx = pattern' start 0
       where
         start = currIdx - width
         end = currIdx + width
         pattern' cnt !result
           | cnt > end = result
           | otherwise = if (currR cnt row)
                           then pattern' (cnt + 1) (result * 2 + 1)
                           else pattern' (cnt + 1) (result * 2)
     makeNewRow :: ST s (ST.STUArray s Int Bool)
     makeNewRow =
       do
         arr <- ST.newArray_ (0, upper)
         let fill idx
               | idx > upper = return ()
               | otherwise = do
                   unsafeWrite arr idx (unsafeAt rules (getRule idx))
                   fill (idx + 1)
         fill 0
         return $! arr
in fromUArray (ST.runSTUArray makeNewRow)

fromUArray produces a new Ring (i.e. CA) from an array. 'makeNewRow'
iterates over every cell in the current row using getRule to get the
new value for each cell and returns the new row as an array. getRule
essentially treats the neighbors of the current cell as bits, with the
most significant to the left. An index into the rules array is
constructed based on the values around the cell being examined (which
wrap on the ends, thus the Ring construct). That index is used to get
the value of the new cell from the rules array.

Profiling shows that the following lines take up the most execution
and allocation:

makeNewRow = ... -- 20.5% execution,  26.7% allocation
if (currR cnt row) ... -- 14.7% execution, 26.6% allocation,  in pattern'
currR ... -- 14.7% execution, 0% allocation

Any suggestions for improving this code? Thanks in advance!

Justin

p.s. The entire program is attached. Compile with ghc -O2
-funbox-strict-fields -fbang-patterns --make GA-CA.hs. It runs 25
rules on each of 25 initial CAs for 2 generations.
p.p.s. On the bright side, this program has excellent memory
performance. It uses a constant 2 - 7 MB depending on the initial
parameters for the entire run. Beautiful!

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe