Repository navigation
Semantics of grow/unsafeGrow #36
Description
Activity
I think this is correct. Having looked at the storable and unboxed vectors couple of weeks ago, this is what I read too. If the documentation is improved as a result, it's probably a good idea to explicitly document that the old vector is copied to the new vector, and this is not a 'realloc' type operation. I think I'm not the only one to think grow = realloc.
I think the intended semantics are that it may do a realloc, but not guaranteed to, and all the current implementations do the simpler copying semantics because for on heap allocations the cost should be roughly the same.
@cartazio If I'm reading you correctly, the correct docs would be:
Even though right now,
growwill always leave the original mutable vector intact and unmodified, this is behavior that may change in the future, and should not be relied upon. If you need such functionality, you should instead create a new vector and then copy the data from the old vector to the new one.i'm not sure if thats quite true. I'll try to take a look with a few folks at hac_bos this weekend. I believe the motivation for the *grow operations lies in Stream fusion in the case when the stream has unknown size, and any choice in semantics should reflect that.
Another perspective: the name
growis misleading. Mutable vectors are implemented using a bare MutableArray instead of a mutable reference thereof. So they couldn't grow in-place in case realloc needed to move.https://hackage.haskell.org/package/vector-0.11.0.0/docs/src/Data-Vector-Mutable.html#MVector
To clarify: currently the interface is
grow :: Vector -> Int -> IO Vectorbut much more sensible would begrow :: Vector -> Int -> IO ()(types simplified).There are probably good reasons (which I don't understand) for not using a mutable reference. But since in-place grow can't be supported that way, another suggestion would be to just remove the interface altogether and make another data type (C++
std::vectorstyle) which can support growing.I don't really know the original intention of grow.
However, there is a notion of growing that does not mutate the original vector, but also does not mean that the new vector can be used without affecting the old one (perhaps only in the 'unsafe' case).
It is the opposite of slicing. When you slice a mutable vector, you just adjust the bounds, but keep the same underlying array, so writes to one can affect (pieces of) the other. In principle, a vector type could over-allocate the underlying mutable array, and allow growing by just adjusting the bounds. Nothing we have does this, but it could be done, and it has the signature of grow.
Edit: I just realized the below assumes an implementation which
reallocs in-place.I'm quite late to the game, but there is at least one other reason why
growreturns a newMVectorreference: It's because the old reference doesn't contain the updated length!#!/usr/bin/env stack -- stack --resolver lts-9.6 script --package vector import Data.Vector.Mutable (IOVector) import qualified Data.Vector.Mutable as Vector main = do v1 <- Vector.new 1 print (Vector.length v1) v2 <- Vector.grow v1 1 print (Vector.length v1) print (Vector.length v2)
In other words, this program prints
$ stack grow.hs 1 1 2That's because instead of modeling the start and end indices in
MVectoras mutable variables, too, they are actually regurlar, unboxedInts. I suspect the reason for this is thatVector.lengthandVector.sliceand by extensionVector.tail, etc. should remain pure. Also from the plain perspective of efficiency, unboxedInts are probably preferrable to mutable references to boxedInts. So, if there were mutable struct fields (there was some HIW talk about that), we should seriously consider using them here.There's another perspective to this: We can't allow a
shrinkoperation or negative arguments togrow, as that would invalidate all old references which still store the old length.TLDR; Even if the implementation used
realloc, we still need to return a new reference fromgrowand make sure that we don't use the old one any more.- added a commit that references this issue
on Jan 20, 2021
I'd like to clarify the semantics of
growandunsafeGrow, and hopefully update the documentation appropriately. From looking at the code for boxed, unboxed, and storable vectors, it seems that in all cases,grow/unsafeGrowwill create a new mutable vector and leave the original mutable vector unchanged. The upshot would be that it would be valid to modify the original vector without affecting the new vector, and vice-versa. Two questions: