Authored by bgamari on May 29 2015, 2:57 AM.
hvr retitled this revision from to Drop custom mapM impl for  & set mapM_ = traverse_.
hvr added reviewers: austin, simonmar.
hvr updated the Trac tickets for this revision.
hvr added a reviewer: ekmett.
Need a nofib run to test perf.
Yes, it'd be nice to at least get some ballpark allocation numbers for this.
Running with option 1 (traverse) does 100% more allocation than option 2 (mapM).
One interesting point is that switching out length for a hand-rolled recursive implementation puts them on par with one another. So the mapM version must be fusing with length somehow, perhaps? Marking both functions NOINLINE has little effect on test1 and makes test2 much worse than noinlined test1, although 2 does less copying than 1 in that case (instead of more when inlining is enabled).
Not sure about the exact mechanism here yet.
Now I'm not sure if my test case is demonstrating the same thing, because moving the mapM/traverse call out to a separate, noinline function in cryptarithm2 has no effect on the results.
Okay. After further investigation, I have some results to report.
My first clue was that when changing the code to use traverse, there is a call to map in the core, which of course isn't there in the mapM code. This was likely causing an extra intermediate list over the mapM version.
So, I hand-rolled an implementation of DigitState, implementing all the classes myself, and marking everything INLINE, performance is then identical between traverse and mapM, and it is better than using transformers.
With that in mind, I popped over to transformers, and looked at StateT. Marking fmap INLINE there had no effect. But, it looked suspicious to me that the Applicative definition just had (<*>) = ap. So, I hand-wrote an implementation and marked it INLINE. This was better than mapM. So, instead I just changed it back to (<*>) = ap and marked it INLINE. This then makes traverse identical in performance to mapM.
So, the discrepancy in performance in this benchmark is due to the StateT instance for Applicative. There is nothing fundamentally slower about traverse here.
Ok, so this makes sense. If <*> = ap, then traverse is the same as mapM, and will have the same performance provided <*> is inlined. If <*> is not inlined, then there might be an extra performance penalty compared with mapM.
I suspect your hand-written and inlined <*> with traverse beat mapM because >>= is not inlined.
This could end up pessimising existing code, but in a recoverable way. We should check whether it happens for IO.
Actually, now that I think about it, I think the allocation difference was that I implemented (<*>) for strict StateT instead of lazy. But it doesn't matter, because just inlining (<*>) = ap achieves parity.
IO seems to display no difference between traverse and mapM.
I think we're good to go here then. Just one thing that puzzles me: <*> = ap should be inlined automatically. Perhaps without the INLINE on <*> = ap we get ap inlined instead, and then <*> does not get inlined at call sites because it is too big. But that still wouldn't explain the difference, because we would only get an extra call, not extra allocation. Strange.
The only thing that makes sense to me is that it doesn't make the decision on whether to inline (<*>) until ap is inlined, at which point it's too large. I'm not sure I knew it worked that way.
The extra allocation is caused by missed fusion. Without inlining, there is a map (:) call that disappears when we inline (<*>) because they fuse together.
Alright, sounds OK to me.
bgamari added a reviewer: bgamari.
make test TEST="ghcirun004 T1969 T5642"
Two are stat failures due to allocations, one appears to time out.
I'm looking deeper into these regressions. It seems that T1969 fails even without this patch so we can safely ignore it.
With doesn't touch mapM at all. Compiling without --interactive produces an executable that works as one would expect.
and there it hangs... This would suggest that this testcase just happens to (luckily) tickle a use of mapM in the compiler. I'm going to recompile ghc with profiling and see if -xc doesn't suggest where this might be.
Unfortunately at the moment I still haven't the slightest idea which monad this is being applied to, so it's unclear how (*>) and (>>) differ.
Intriguingly, reverting just this piece of the patch allows ghcirun004 to be loaded and run. Removing the INLINE has no effect.
Indeed the mapM_ instance in question appears to live in ByteCodeAsm in assembleBCO. Reverting it to use the previous definition of mapM_ results in normal load times for ghcirun004. The monad here is Assembler, defined in the same module.
Indeed defining (*>) = (>>) in the Applicative Assembler instance brings things back to sanity.
Hmm, isn't Phabricator supposed to pull in dependencies of a Diff when validating it? This validates on my machine with D1097 yet somehow the Harbormaster still fails.
bgamari edited reviewers, added: hvr; removed: bgamari.
I'm going to abandon this to preserve it for posterity and merge the removal of the mapM override from  in D1124.