什么时候修改复制向量？ [英] When does `modify` copy the vector?

问题描述

从 https：// hackage .haskell.org / package / vector-0.12.0.1 / docs / Data-Vector.html＃v：modify

对矢量应用破坏性操作。如果安全的话，该操作将在适当的位置执行，否则将修改该矢量的副本。

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

何时进行修改，以及何时将复制向量？是否有某种方法可以通过使用类型系统来确保它将被修改到位？

解决方案修改调用 Data.Vector.Generic.modify ，它调用 clone ，它具有以下重写规则：

 clone / new [Vector]forall p。 
 clone（new p）= p 
  

所以当某些东西的语法形式为新的p 它不会被复制。它显示为修改，切片， init ， tail ， take ， drop ， unstream 和克隆是在这里融合得很好的主要内容。这与所有支持向量设计的流媒体融合工作密切相关。编辑：根据你的评论，我将详细说明。只有格式 new p 的语句才会避免复制。既然你可能不是自己编写 new ，那么它只会出现在向量包中内联使用函数的结果。查看矢量 1 ，看起来上面使用 new 标识的函数，并且应该允许修改不复制，如果事情是内嵌的，即使那时大多数人只保留新的东西，矢量仍然必须通过像 create ， force ，修改或 unstream 。

例如，如果您有代码：

  v = fromList [1..10] 
g =修改fv 
f = undefined 
  

然后 v 将被内联，并且该向量的格式为 new p （因为 $ from $ 使用 unstream 它是 new ），因此 modify 不需要复制数组。

另一方面，考虑：

  v = let v0 = fro mList [1..10] in 
 { - ＃NOINLINE v＃ - } 
g =修改fv 
  

现在 v 没有显式内联 - 它也可能不能内联，因为它来自不同的模块或共享表达式。因此，没有代码是语法 修改f（new p）并且重写规则不会触发。

少花点心思，考虑：

  g = let v = fromList [1..10 ] 
t = v！ 4 
 v2 =修改fv 
 in t +（v2！4）
  

这是一种常见的模式，在这种模式下，矢量既可以被读取也可以被修改 - 在读取和重写规则不会被触发前显然不能被修改（因为没有 new v 的共享。

1 参见此处为规则slice / new [Vector]，例如。

From 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.

This sounds like it can have drastically different performance characteristics depending on whether it is deemed "safe" to modify the vector in place. This motivates the questions...

When will the modify be performed in place, and when will the vector be copied? Is there some way to ensure, by use of the type-system for example, that it will be modified in place?

解决方案

Modify calls Data.Vector.Generic.modify which calls clone which has the following rewrite rule:

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

So when something is in a syntactic form of new p it isn't copied. It appears modify, slice, init, tail, take, drop, unstream, and clone are the main thing that fuse well here. This is all closely related to the stream fusion work (google-able paper for deep dives) that underpins vector's design.

EDIT: Based on your comment I'll elaborate. Only things syntactically in the form new p will avoid copying. Since you're probably not writing new yourself then it will only appear as a result of inlined use of function from the vector package. Looking at vector 1, it appears the functions I identified above use new and should thus allow modify to not copy if things are inlined and even then most those only preserve newness, the vector still had to be freshly constructed via something like create, force, modify, or unstream.

For example, if you have the code:

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

Then v will be inlined and the vector is in the form new p (because fromList uses unstream which is new) and therefore modify will not have to copy the array.

On the other hand, consider:

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

Now v is not inlined explicitly - it could also not be inlined because it is from a different module or the expression is shared. As a result there is no code that is syntactically modify f (new p) and the rewrite rule won't fire.

Less contrived, consider:

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

This is a common pattern where a vector is both read and modified - it obviously can't be modified before the read and the rewrite rules either won't fire (because there is no new there) or you'll have to lose sharing of v.

1 See here for the rules "slice/new [Vector]", for example.

这篇关于什么时候修改复制向量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！