performance - When does `modify` copy the vector?

Question

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?

Answer 1

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.