Repository navigation
Implementing a value-strict Vector #380
Description
Activity
No
elemseqis barely used. You'll have to force element to WHNF inVector/MVectorinstance.P.S.
StorableandPrimdefinitions are also not quite correct. Storing value in array will evaluate it to NF, whileseqevaluates to WHNF. This is more serious forStorablewhere value could mirror some C struct and have lazy fields and that difference would matter.OK, thanks for the hint. I went through the instance methods and it seems that
MVector'sbasicUnsafeReplicateandbasicUnsafeWriteare the only ones that take in an element to be added to an array, so I just added bangs to those. Is that right? That is still quite simple, I'm happy I didn't have to duplicate the entire top-level API and add bangs everywhere.@infinity0 I remember there is
basicSet?@infinity0
By settingbasicSet (StrictVector v) !x = basicSet v xwe can let GHC believe that the caller of
setmay evaluatexto WHNF no matter whethervis inhabited or empty; that can lead to a better optimization.I can see what you mean, but what real use-case would that help? IMO it is sufficient that a "strict container" ensures the values inside it are forced; this is sufficient to prevent space-leaks. The additional behaviour you're describing doesn't really do anything to prevent space leaks: either
xis lost, thus GCd, orxwill later be placed inside a different strict container which would force it then, orxwill later be placed inside a different lazy container in which case not forcing it is fine.
BTW version with bang is slightly more strict. It will evaluate
xin every case, while default will only force it for nonempty vectorsReacted by Genki Sato@infinity0 More I think about it, more difficult it is to settle my standpoint. However I share what I naïvely thought until now. Not redefining
basicSetdoes not hurt the vector's correctness. We may even say it is more correct to leave it default. However it can dig a pithole in front of a user in case of the lack of good documentation, and it can lead to a space leak.import Data.Vector.Strict.Mutable as VStrM import Data.Vector.Strict as VStr example :: Int -> ST s (VStr.Vector (VStrM.Vector s Int)) example n = do vec <- VStr.replicateM 100000 (VStrM.new n) !_ <- VStr.foldM (\i v -> VStrM.set v (2*i) >> return (i+1)) (0::Int) vec return vecObviously the function leaks space where
n==0, since it creates a 100000-fold nested thunk(...((0+1)+1)...+1). Even in the casen /= 0, GHC cannot reduce its loop variableifromInt(which is heap-allocated) toInt#(which is on the stack or the register) because GHC, correctly, doesn't deduce that the loop function is strict ini.
However the user may assume thatVSM.setis strict in its second argument, either becauseVStrM.MVectoris advertised as strict, or becauseData.Vector.Unboxed.Mutable.setis so in all the official implementations.I wrote this up until here and I noticed
Data.Vector.Storable.Mutable.setis not strict in the second argument. The lesson is that the users of a strict container cannot assume the functions manipulating them are strict just because the containers are strict, maybe? I don't even know if it's good to retract my argument here...The lesson is that the users of a strict container cannot assume the functions manipulating them are strict just because the containers are strict, maybe?
Right, I think this lack-of-guarantee is acceptable, because it also applies to the alternate strategy of defining !-annotations on the container data type. (Which I prefer; but I cannot do for Vector because of the reasons I gave in the OP.) In that case, the whole point is to free the developer from worrying about putting !-annotations on functions (or
seqs everywhere), and in this case if a function does not actually put the element into the container, then the element is not forced.In other words, the example you gave, would also exhibit the same non-forcing behaviour for the other containers I added to strict-containers that use !-annotations on data types. (e.g.
Strict.Map)So if the user needs to force it outside of the container (any strict container), they themselves should be performing the forcing.
The lesson is that the users of a strict container cannot assume the functions manipulating them are strict just because the containers are strict, maybe?
This is also impossible to achieve in practise - since anyone can write their own function that "operates" on a strict container, that doesn't put an element argument into the container. For example, variations on
contains. It's not really feasible to require everyone in the world to enforce this guarantee, so I don't think users can reasonably expect it to be true.Thank you for your good explanation. Now I understand you and agree with you.
since anyone can write their own function that "operates" on a strict container, that doesn't put an element argument into the container. For example, variations on
contains. It's not really feasible to require everyone in the world to enforce this guaranteeThis is completely correct. However this means we can't ever fill up the said pitfall, and that it's BIG. We need a good textbook about this, maybe...😆
OOI, how does it differ from https://hackage.haskell.org/package/strict-containers? Oh, you actually wrote that one: https://github.com/haskellari/strict-containers/blob/master/strict-containers/patches/Vector.patch
Great job, thank you @infinity0!
@Mikolaj that package written by me is basically the result of the above discussion, and there is no difference.
This issue could be closed, or it could be left open if the maintainers would like to merge my strict vector into this package eventually.
Reacted by Mikolaj KonarskiThat would be very welcome. I'm now struggling with a conflict between vector (from which I need Storable vectors) and strict-containers (from which I need the strict boxed Vector).
BTW, I've found
Data.Strict.Vector.Autogen.Mutable, which solved my conflict and the leak I was having is gone. :)
Hi, I am trying to implement a variant of
Data.Vectorthat is automatically strict in its values.Since the underlying structure is a primitive
Array#I cannot add!strictness annotations to the data constructors, which would otherwise have been the most efficient way to do this. So I am forced to force every element as it is added to the vector.It seems that
Generic.Vectoroffers a methodelemseqfor this purpose - forVector.Storablethis isseqwhilst for the normal lazyVectorthis does not evaluate the first subject. So it would seem that to implement a value-strictVectorclone, I could simply copyData.Vectorwith one single addition of definitionelemseq _ = seq, is that correct? Sorry if this is blindingly obvious but it's not explicitly mentioned in the docs (I suggest to add this & can file a PR to this effect.)