What is the effect of mapping with a newtype constructor

user_2289983 0
Viewed 146

In Chapter 8 of thinking with types I learned that the fmap Sum part of

fastSum :: [Int] -> Int
fastSum = getSum . mconcat . fmap Sum

has a O(n) runtime cost, whereas using coerce instead avoids that overhead.

I know newtypes have no representation overhead, but what I do not understand is what is the runtime effect of mapping a newtype constructor over a list. I thought this would only have a compile-time overhead, and it should be just O(1), since the compiler only needs to know the type of the fmap SomeNewtypeCtr expression.

newtype haskell
1 Answers

It's hard to understand what Haskell exactly does in such cases, because of optimization. Haskell only mandates what is the result, not how it is obtained.

Some possibilities:

  • fmap Sum performs a list scan, and copies each cell and each element;
  • fmap Sum performs a list scan, and copies each cell but not the elements (the new cells point to the old elements);
  • fmap Sum does not scan the list at all and is automatically optimized to a no-op.

I tried godbolt.org to inspect the generated Core and assembly. Note that it still uses an old GHC 8.6.2. Still, I turned optimization on (-O2) and compiled

foo :: [Int] -> [Sum Int]
foo = fmap Sum

and obtained

foo = Example.foo1 `cast` (.....)
Example.foo1 = \ (v_a1iF :: [Int]) -> v_a1iF

Hence foo becomes the identity function, suitably coerced, producing the assembly

   movq %r14,%rbx
   andq $-8,%rbx
   jmp *(%rbx)

which should be, roughly speaking, the equivalent of an immediate return in the GHC runtime system.

Concluding: Data.Coerce.coerce is very nice since it ensures a no-op, but even plain Haskell, after optimization, can be surprisingly efficient.

user_32349590
Related