Allocation strategies for vector creation

[Shimuuar]

Currently we have following size hints in bundle:

data Size = Exact Int          -- ^ Exact size
          | Max   Int          -- ^ Upper bound on the size
          | Unknown            -- ^ Unknown size

however buffer allocation for vector has only two strategies: doubling for unknown and exact allocation for both Exact and Max. I think we should have three: unbounded doubling, doubling with bound for Max, and preallocation for Exact

P.S. It was also proposed to add lower bound to discussion

[gksato]

@Shimuuar I guess from your comment in #301 that, parhaps, you intend to assign Exact for fromListN ? If it's correct, It's quite unsettling...

[Shimuuar]

Yes but I don't think this is a problem. It's hint for size of underlying buffer which could be larger than array.

[gksato]

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 change Data.Vector.Generic.length from O(1) to O(N). Currently we have

Data.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.

[gksato]

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 Exact holds the exact length. We need to implement a big detour in order to make that semantical change.

[Shimuuar]

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

[gksato]

@Shimuuar Correct. I think we agree on the fact that we can't keep the type Size as 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 of fromListN 4 [1,2,3,4] ++ takeWhile (\x -> x*x < 15) (generate 16 id) ?

[gksato]

Oh, sorry. Bundled pattern synonyms isn't there on GHC 7.10. So we can't make it seem backwards-compatible.

[Shimuuar]

I tried following size hint

data Size = Size
  { lowerBound :: !Int
  , upperBound :: !SizeHint
  }

It seems to work reasonably well. But yes. It's breaking change

[Shimuuar]

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 maxBound for 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 lowerBound size and use doubling until you reach upperBound. I think this should neatly resolve #301 and give much better implementation for size hints.

@lehins @Bodigrim @gksato What's your opinion?

[Bodigrim]

Sounds reasonable to me.

[gksato]

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 :: Bool or a constructor Exact Int anyway, in order to preserve the swiftness of length <allocated vec> or length $ map f <allocated vec> (or does lowerBound == upperBound optimize well with GHC ...? I'm not sure).

[Shimuuar]

unforldr produces stream of maxBound+1, right? It wont break if we treat upper bound maxBound specially by assuming that it's some number >=maxBound. In that case unforldr produces hint Size 0 maxBound then dropping any number of elements should result in Size 0 maxBound.

Main problem is streams could be of any size and vectors couldn't be longer then maxBound so 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 Exact constructor to make optimizer happy. I'm not sure it can optimize lowerBound == upperBound well.

[gksato]

Uh, I think you ...um... nailed it right. So Int for upperBound is an encoding of Maybe NonMaxBoundInt. I don't see any problem with that.

[lehins]

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)