CODEWITHSUNDEEP
performancehaskell
gspr
gspr

Reputation: 11227

Why are the functions making Vector an instance of Functor, Monad, Applicative, Alternative, Foldable and Traversable slow?

The changelog for version 0.8 of vector lists the following change with a warning:

Functor, Monad, Applicative, Alternative, Foldable and Traversable instances for boxed vectors (WARNING: they tend to be slow and are only provided for completeness).

Could someone explain why this is the case? Is it just the normal cost of typeclass specialization, or something more interesting?

Update: Looking at some particular instances, one sees for example:

instance Foldable.Foldable Vector where
  {-# INLINE foldr #-}
  foldr = foldr

and similarly for the other folds. Does this mean that folding is slow for Vectors in general? If not, what makes a non-specialized fold slow enough to warrant a warning?

Upvotes: 17

Views: 554

Answers (2)

Edward Kmett
Edward Kmett

Reputation: 29962

I submitted the original set of these instances to Roman a year and a half ago and have maintained vector-instances since then. (I had to remove these instances from vector-instances once they migrated into vector, and now maintain it solely for the really exotic stuff). His concern was that if folks used these instances polymorphically then the RULES that make Vectors fuse away can't fire unless the polymorphic function gets inlined and monomorphized.

They exist because not every bit of code on the planet is Vector-specific and even then it is nice to sometimes use the common names.

Slow here is relative. The worst case is they perform like anybody else's folds, binds, etc. but Roman takes every single boxed value as a personal insult. :)

Upvotes: 15

jaspervdj
jaspervdj

Reputation: 883

I've just had a quick look at the source code and the implementations don't look excessively slow. I'd argue the authors added this warning because when you're writing a program in the Vector monad, you're working from such a high-level point of view that it's easy to forget that every >>= is, in fact, a concatMap, which tends to be inherently slow.

Another thing: Vector is particularly fast for unboxed types. So a user might be attracted to use the monad notation (for convenience), while he should actually be using an unboxed type (for speed).

Upvotes: 8

Related Questions