For dense access, is it better or worse to freeze an array first?

Question

Let's say I have an Data.Array.IO.IOArray i e (from the array package) and I would like to read elements from it, processing each element, one by one, in IO, according to some index ordering:

arr :: IOArray I E
ordering :: [I]
processElement :: I -> E -> IO ()

(as we can see, everything is monomorphic).

There are two obvious ways of doing this:

1. freezeing the array first into an immutable array, and using the ! operator:

   do
       arr' <- freeze arr
       forM_ ordering $ \i -> processElement i (arr' ! i)
   

2. readArray'ing each element from the original, mutable array:

   forM_ ordering $ \i -> do
       e <- readArray arr i
       processElement i e
   

The indices in ordering are "dense" in the sense that most indices of arr appear in ordering.

Which one is more efficient? Also, does the answer depend on these factors:

• Whether the index ordering has duplicate indices?
• Whether the index ordering is monotonically increasing?
• Whether the index ordering is completely random vs. has large continuous stretches?

Answer 1

It does not matter. Reading from a mutable array is the same as reading from an immutable one, barring obvious issues in implementation, e.g. where one version inlines/unpacks and the other does not.

If you expect to write to the array, freezing just for the sake of indexing is unnecessary. If you don't expect to write to the array, freezing could be beneficial as it would take the array off the mutable list, thereby lowering GC overhead. However, with generous arena sizes and small number of mutable arrays, even this does not matter that much.

As to pattern of read access, general locality considerations apply. The denser, the better, plus we should avoid iteration with strides of larger powers of 2, if possible, to reduce cache conflicts.