Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#10457 closed task (fixed)

Revise/remove custom mapM implementation for lists

Reported by: dolio Owned by:
Priority: normal Milestone: 8.0.1
Component: libraries/base Version: 7.10.1
Keywords: Cc: hvr, ekmett, simonmar
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D1124
Wiki Page:

Description (last modified by bgamari)

Recently, Simon Marlow asked why the list instance for Traversable had a custom mapM implementation that used the Monad operations. Having looked a bit, I don't think there's any good reason. The only fusion that the custom mapM can participate in is due to it being written as foldr, but traverse is, as well. So as long as mapM = traverse is able to inline appropriately, there should be no difference.

Further, this can be changed, in principle, for 7.10.2. It doesn't change any types, only the implementation.

mapM = traverse is the class default definition, so this could possibly be completed by just removing the custom definition.

Link to the libraries thread: https://mail.haskell.org/pipermail/libraries/2015-May/025708.html

Change History (20)

comment:1 Changed 4 years ago by dolio

mapM_ is in a similar situation, despite not being in the Foldable class. It is currently implemented with (>>), but it could be implemented with (<*) or just as mapM_ = traverse_. This is desired as well (see the most recent message in the libraries thread at the time of this comment).

comment:2 Changed 4 years ago by simonmar

Cc: simonmar added

comment:3 Changed 4 years ago by hvr

Differential Rev(s): Phab:D924

here's a first attempt at a patch; please review if that's the change you suggest

comment:4 Changed 4 years ago by ekmett

Looks right to me.

comment:5 Changed 4 years ago by simonpj

Well someone should preferably just check that whatever fusion used to happen still happens, and ideally add a performance test to make sure it stays that way.

That done, go ahead if the Core Libraries Committee is happy. (And Edward is presumably speaking as its chair in comment:4.)

I'm unconvinced it's worth merging to 7.10. After all, it changes nothing except omitting one line of code from a library, right?

Simon

comment:6 Changed 4 years ago by simonmar

Hmmm, so this is only a transparent change for Monads that have <*> = ap. Arguably since it is possible to write legal (though unconventional) Haskell that behaves differently, and it's not a bug fix, it should not go into 7.10.2.

(arguing against my own best interests, because it being in 7.10.2 would be helpful for me, but I've been working around it for a while so I can continue to do so)

comment:7 Changed 4 years ago by dolio

I'm not really attached to this, so if simonmar is okay with postponing to 7.12, it's fine with me.

Anyone who uses Monads with (<*>) /= ap (at least, in ways giving distinct answers) is going to have a bad time, though. The specification of Monad now says they need to be equivalent, and I think that gives library writers license to switch between them without making a major version change. And it's only going to get worse. When ApplicativeDo gets implemented, using that extension will silently switch between these things. For instance, if ApplicativeDo were on in the file with the custom mapM, it would already be the same as traverse, I think.

comment:8 Changed 4 years ago by simonpj

I'm a bit lost. The only change seems to be this:

instance Traversable [] where
instance Traversable [] where
    traverse f = List.foldr cons_f (pure [])
      where cons_f x ys = (:) <$> f x <*> ys

    mapM = Monad.mapM   --   <========= DELETE THIS LINE

That means using the default method, traverse, rather than mapM. Why is that a big deal?

comment:9 Changed 4 years ago by dolio

If I understand correctly, simonmar has a Monad whose Applicative instance does batching of remote calls, because you can do that when you use (<*>) but not (>>=). So:

f <*> x

does one round trip to the server, while:

f >>= \g -> x >>= \y -> return (g y)

does two.

The custom mapM does n trips, where n is the length of the list, while traverse does one, because the latter is implemented using:

cons_f x ys = (:) <$> f x <*> ys

whereas the former is:

cons_f x ys = do { z <- f x ; zs <- ys ; return (z:zs) }
Last edited 4 years ago by dolio (previous) (diff)

comment:10 Changed 4 years ago by simonmar

@simonpj You could in principle write an Applicative or Monad instance that would distinguish between mapM and traverse, although it wouldn't be a good idea. But strictly speaking this is therefore a semantic change.

In my case it makes a (huge) difference to performance, because traverse is parallel for the Haxl monad, where as mapM is serial. There's no difference in semantics, provided you don't dig into the monad implementation and only use the external interface, and provided some other conditions are met.

comment:11 Changed 4 years ago by thoughtpolice

Status: newpatch

comment:12 Changed 4 years ago by thoughtpolice

Milestone: 7.10.27.12.1

From my notes from last week, we're moving this out of 7.10.2, which I forgot about. Punting.

comment:13 Changed 4 years ago by bgamari

Description: modified (diff)
Differential Rev(s): Phab:D924Phab:D1124

Phab:D924 proposed a redefinition of mapM_ in addition to the removal of list's override of mapM. This changed the performance characteristics of user code, as seen in #10711.

I've extracted the removal of the mapM override into Phab:D1124 and forwarded the mapM_ issue to the Core Libraries Committee.

comment:14 Changed 4 years ago by Ben Gamari <ben@…>

In 60297486/ghc:

Drop custom mapM impl for []

See https://mail.haskell.org/pipermail/libraries/2015-May/025708.html
for motivation.

This fixes #10457

Test Plan: Validate

Reviewers: hvr, austin

Subscribers: simonmar, thomie, dolio

Differential Revision: https://phabricator.haskell.org/D1124

GHC Trac Issues: #10457

comment:15 Changed 4 years ago by bgamari

Resolution: fixed
Status: patchclosed

comment:16 Changed 4 years ago by simonpj

Resolution: fixed
Status: closednew

The perf tester says, about nofib allocations:

nofib/allocs/cryptarithm2   + 64.55%
nofib/allocs/k-nucleotide    - 5.03%
nofib/time/fannkuch-redux    - 3.62%

This needs looking into!

Simon

comment:17 Changed 4 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:18 Changed 4 years ago by thomie

Type of failure: None/UnknownRuntime performance bug

nofib/allocs/cryptarithm2 13094088 + 64.55% 21545696 bytes

comment:19 Changed 4 years ago by thomie

Resolution: fixed
Status: newclosed

The performance regression is fixed: https://perf.haskell.org/ghc/#revision/fff02548d237655dea39f108364d7ebe6d0e122d.

nofib/allocs/cryptarithm2 21545696 - 41.58% 12588032 bytes

comment:20 Changed 4 years ago by nomeata

JFTR: This instance of the regression has been fixed, because the State implementation got a sensible Applicative instance. The change in changeset:60297486/ghc still has the ability to regress any user code that has (<*>) = ap. OTOH, there is little we can do about it besides telling people to implement their Applicatives properly.

Note: See TracTickets for help on using tickets.