Repository navigation
Allocation strategies for vector creation #388
Description
Activity
@Shimuuar I guess from your comment in #301 that, parhaps, you intend to assign
ExactforfromListN? If it's correct, It's quite unsettling...Yes but I don't think this is a problem. It's hint for size of underlying buffer which could be larger than array.
If we add a new field
preAlloc, it's a big breaking change, but I'm afraid of the possibility that changing the semantic behavior like in the OP may break something somewhere unknowably. Also, I'm not sure if it is OK to changeData.Vector.Generic.lengthfrom O(1) to O(N). Currently we haveData.Vector.Fusion.Bundle.length Bundle{ sSize = Exact n } = n
What if someone relies on it?
I can't imagine there are any; I can explain myself that there couldn't be any, but I can't convince myself.Oh no. We have
Generic.length = Bundle.length . Generic.stream
That is, in order to calculate in constant time the length of an actually heap-allocated vector, we rely on the fact that
Exactholds the exact length. We need to implement a big detour in order to make that semantical change.Generic.length = Bundle.length . Generic.stream
You're right. That's bad on one hand but isn't big problem. We just need to make hint more precise. It could be solved by adding one more constructor:
... | Exact Int -- Vector will have exactly this length | Preallocate Int -- Allocate buffer of this size
And is we extend size hints with lower bounds on size bounds it could be written as
Max n n@Shimuuar Correct. I think we agree on the fact that we can't keep the type
Sizeas it is. However, there could be many choices we can make; what you proposed in is surely one thing:data Size = Exact { length :: Int } -- exact size | Preallocate { allocatedMax :: Int } -- Allocate the maximum possible size | Max { max :: Int } -- firstly zero-allocate and do doubling till max | Unknown -- unbounded doubling
I proposed one solution in #301:
data Size = Exact { length :: Int } | Max { preAlloc :: Int, max :: Int } | Unknown { preAlloc :: Int }
We could even try to make everything seem backwards compatible:
data Size = Exact { length :: Int } | DoublingWithMax { preAlloc :: Int, max :: Int } | DoublingUnbounded { preAlloc :: Int } pattern Max n <- DoublingWithMax _ n where Max n = DoublingWithMax 0 n pattern Unknown <- DoublingWithUnbounded _ where Unknown = DoublingWithUnbounded 0 {-# COMPLETE Exact, Max, Unknown #-}
Another reason why I'm proposing solution with minimal bound is the definition of
(+), that is, the interaction with(++). How do we set the size hint offromListN 4 [1,2,3,4] ++ takeWhile (\x -> x*x < 15) (generate 16 id)?Oh, sorry. Bundled pattern synonyms isn't there on GHC 7.10. So we can't make it seem backwards-compatible.
I tried following size hint
data Size = Size { lowerBound :: !Int , upperBound :: !SizeHint }
It seems to work reasonably well. But yes. It's breaking change
- added a commit that references this issue
on Sep 14, 2021 - added a commit that references this issue
on Sep 26, 2021 So after playing a bit with this I converged on following very simple design for vector size hint:
data Size = Size { lowerBound :: !Int , upperBound :: !Int }
For every stream we have estimate for lower and upper bound on vector size. We can use
maxBoundfor vector without such bound. And it's in fact honest bound since it's not possible to create longer vectors anyway.Unstreaming strategy should be simple as well: start from vector with
lowerBoundsize and use doubling until you reachupperBound. I think this should neatly resolve #301 and give much better implementation for size hints.Sounds reasonable to me.
Related to #406, doesn't it break the following?:
drop maxBound $ (`unfoldr` (0::Int)) $ \x -> if x < 0 then Nothing else Just ((), x+1)
We could additionally declare that any vector longer than
maxBound, even if it only appears in the middle of fusions, will make the resulting vector defined and non-divergent but unspecified, though.Also, we will need to have a flag
exactness :: Boolor a constructorExact Intanyway, in order to preserve the swiftness oflength <allocated vec>orlength $ map f <allocated vec>(or doeslowerBound == upperBoundoptimize well with GHC ...? I'm not sure).unforldrproduces stream ofmaxBound+1, right? It wont break if we treat upper boundmaxBoundspecially by assuming that it's some number>=maxBound. In that caseunforldrproduces hintSize 0 maxBoundthen dropping any number of elements should result inSize 0 maxBound.Main problem is streams could be of any size and vectors couldn't be longer then
maxBoundso stream fusion can have intermediate streams that are not representable as vectors and final stream is. Thus stream fusion can turn ⊥ into terminating programs. It does that already by dropping ⊥ elements. So I don't see any problem with adding another and rather obscure way of doing so.And yes we may want to add
Exactconstructor to make optimizer happy. I'm not sure it can optimizelowerBound == upperBoundwell.Uh, I think you ...um... nailed it right. So
IntforupperBoundis an encoding ofMaybe NonMaxBoundInt. I don't see any problem with that.Sorry guys, I had a newborn son just a week after all of you had this discussion last time. Since then the life has been a roller coaster. 😉
Anyways, I think I like this idea of having a region lower+upper bound for the size estimate. It will be quite a bit of work though and it is indeed a breaking change. @Shimuuar I am not sure how far along have you gotten with this, but considering it has been half a year I don't suspect we'll have it done within a month or so, right?
Reason why I am bringing this up is because I'd like to have a release done in two weeks time. See my #357 (comment)
- added a commit that references this issue
on Oct 31, 2024
Currently we have following size hints in bundle:
however buffer allocation for vector has only two strategies: doubling for unknown and exact allocation for both
ExactandMax. I think we should have three: unbounded doubling, doubling with bound for Max, and preallocation for ExactP.S. It was also proposed to add lower bound to discussion