#10711: Defining mapM_ in terms of traverse_ causes substantial blow-up in ByteCodeAsm -------------------------------------+------------------------------------- Reporter: bgamari | Owner: bgamari Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: ghcirun004 Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by akio): I think the quadratic behavior comes from the fact that the `>>=` linearly traverses its LHS. Let's define the size of an `Assembler` value with: {{{#!hs size :: Assembler a -> Integer size (Pure _) = 1 size (Thing i k) = 1 + size (k i) }}} `m >>= f` performs `O(size(m))` operations because `>>=` is recursive on its LHS. Most of the cost is hidden inside a lambda, but you will have to pay it eventually, namely when `run` is finally applied. Now we can analyze the cost of other operations: * `m >> n` needs `O(size(m))` operations, because it's `m >>= \_ -> n`. * `f <$> m` needs `O(size(m))` operations, because it's `m >>= return . f`. * `m <*> n` needs `O(size(m) + size(n))` operations, because it's `m >>= \v -> n >>= \w -> return v w`. * `m *> n` needs `O(size(m) + size(n))` operations, because it's `const <$> m <*> n`. If you use `mapM_` with a `N`-element list of 2-sized `Assembler`s, each application of `>>` costs `O(1)`, so the total cost is `O(N)`. If you use `mapA_` instead, the LHS of an application of `*>` is `O(1)` large but the RHS is `O(N)` large on average. This means it needs `O(N)` operations on average, so the total cost is `O(N*N)`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10711#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler