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:

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

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

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?

It is better to use the mutable array directly because safe freezing operation will make a copy of the whole array, which has real cost to it. However, it really is better to use unsafe freeze with runST and then use `!`, because then you are not restricted to some IO like monad and in case of boxed arrays, as @Andreas pointed out, GC doesn't have to traverse it. — lehins, Feb 27 '21 at 18:20
@lehins but my `processElement` uses IO in a non-trivial way regardless of item access, so being in `IO` is not a limitation. — Cactus, Feb 28 '21 at 00:24
Of course, I didn't mean that you have to get out of IO, I am just saying that if you have a choice between effectful and immutable it is usually best to go for the latter, after all that's why we love Haskell, right? ;) My comment was mostly about freeze copying the array, which is an important thing to keep in mind when arguing performance. — lehins, Feb 28 '21 at 00:55

András Kovács · Accepted Answer · 2021-02-27T08:40:20.180

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.

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

1 Answers1