performance - `modify` 什么时候复制向量？

Question

来自 https://hackage.haskell.org/package/vector-0.12.0.1/docs/Data-Vector.html#v:modify

Apply a destructive operation to a vector. The operation will be performed in place if it is safe to do so and will modify a copy of the vector otherwise.

这听起来像它可能具有截然不同的性能特征，具体取决于是否认为修改向量是“安全的”。这激发了这些问题......

什么时候修改到位，什么时候复制向量？有没有办法通过使用类型系统来确保它会被修改到位？

Answer 1

修改来电Data.Vector.Generic.modify调用 clone它具有以下重写规则:

"clone/new [Vector]" forall p.
  clone (new p) = p

因此，当某事物的语法形式为 new p它不是复制的。出现 modify , slice , init , tail , take , drop , unstream , 和 clone是在这里融合得很好的主要东西。这一切都与支撑矢量设计的流融合工作(谷歌能够深入研究的论文)密切相关。

编辑:根据您的评论，我会详细说明。仅语法形式为 new p 的事物将避免复制。因为你可能没有写 new那么它只会作为内联使用矢量包中的函数的结果出现。看矢量图 1 ，看来我上面确定的函数使用 new因此应该允许 modify如果东西被内联而不复制，即使这样大多数只保留新鲜感，向量仍然必须通过 create 之类的东西重新构建。 , force , modify , 或 unstream .

例如，如果您有以下代码:

v = fromList [1..10]
g = modify f v
f = undefined

然后 v将被内联，向量的形式为 new p (因为 fromList 使用 unstream 即 new )，因此 modify不必复制数组。

另一方面，考虑:

v = let v0 = fromList [1..10] in 
{-# NOINLINE v #-}
g = modify f v

现在 v没有显式内联 - 它也不能被内联，因为它来自不同的模块或表达式是共享的。因此，没有语法上符合 modify f (new p) 的代码。并且重写规则不会触发。

不那么做作，考虑:

g = let v = fromList [1..10]
        t = v ! 4
        v2 = modify f v
    in t + (v2 ! 4)

这是一个常见的模式，其中一个向量既被读取又被修改——它显然不能在读取之前被修改，并且重写规则要么不会触发(因为那里没有 new)，要么你将不得不输分享 v .

1见 here例如，对于规则“slice/new [Vector]”。