You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
I'd like to clarify the semantics of grow and unsafeGrow, and hopefully update the documentation appropriately. From looking at the code for boxed, unboxed, and storable vectors, it seems that in all cases, grow/unsafeGrow will 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:
Have I misread the code, and in fact that's not the way the current three vector types work?
Do we want to codify this contract in the documentation as a promise for future behavior?
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, grow will 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 grow is 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.
To clarify: currently the interface is grow :: Vector -> Int -> IO Vector but much more sensible would be grow :: 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::vector style) 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 grow returns a new MVector reference: It's because the old reference doesn't contain the updated length!
That's because instead of modeling the start and end indices in MVector as mutable variables, too, they are actually regurlar, unboxed Ints. I suspect the reason for this is that Vector.length and Vector.slice and by extension Vector.tail, etc. should remain pure. Also from the plain perspective of efficiency, unboxed Ints are probably preferrable to mutable references to boxed Ints. 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 shrink operation or negative arguments to grow, 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 from grow and make sure that we don't use the old one any more.
Activity
vincenthz commentedon Jul 31, 2014
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.
cartazio commentedon Jul 31, 2014
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.
snoyberg commentedon Aug 1, 2014
@cartazio If I'm reading you correctly, the correct docs would be:
cartazio commentedon Aug 1, 2014
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.
jstimpfle commentedon Jul 20, 2016
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.dolio commentedon Jul 20, 2016
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.
sgraf812 commentedon Sep 29, 2017
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!In other words, this program prints
That'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.Improve haddock of `grow` functions and clarify their semantics. Fix #36
Improve haddock of `grow` functions and clarify their semantics. Fix #36
lehins commentedon Jan 17, 2021
Anyone involved in this issue cares to review a PR that clarifies those
growsemantics, feel free to comment: #360It only took 6 and a half years to get to and 30 min to implement ð
Improve haddock of `grow` functions and clarify their semantics. Fix #36
Merge pull request #360 from haskell/document-grow-semantics
Improve haddock of `grow` functions and clarify their semantics. Fix #36