对于密集访问，先冻结数组是好是坏？

Question

假设我有一个Data.Array.IO.IOArray i e（来自array包），我想从中读取元素，根据一些索引顺序在 IO 中一个一个地处理每个元素：

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

（正如我们所见，一切都是单态的）。

有两种明显的方法可以做到这一点：

1. freeze首先将数组放入不可变数组中，然后使用!运算符：

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

2. readArray'ing 原始可变数组中的每个元素：

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

中的索引ordering是“密集”的，因为大多数索引arr出现在 中ordering。

哪一种更有效率？此外，答案是否取决于以下因素：

• 索引是否ordering有重复索引？
• 指数ordering是否单调递增？
• 指数ordering是完全随机还是有大的连续延伸？

Answer 1

没关系。从可变数组中读取与从不可变数组中读取相同，除非在实现中存在明显问题，例如一个版本内联/解包而另一个版本没有。

如果您希望写入数组，则无需为了索引而冻结。如果您不希望写入数组，冻结可能是有益的，因为它将数组从可变列表中移除，从而降低 GC 开销。然而，由于竞技场的大小和可变数组的数量很少，即使这也无关紧要。

对于读取访问的模式，适用一般的局部性考虑。越密集越好，此外，如果可能，我们应该避免以 2 的更大幂的步幅进行迭代，以减少缓存冲突。