Opened 10 years ago

Last modified 10 months ago

#1168 new bug

Optimisation sometimes decreases sharing in IO code

Reported by: simonmar Owned by:
Priority: normal Milestone:
Component: Compiler Version: 6.6
Keywords: Cc: adam@…, klao@…, maoe
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case: nofib/spectral/calendar
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

The simplifier is losing sharing in spectral/calendar, probably because we're being a bit fast-and-loose with eta-expanding State# lambdas. A quick look at the Core shows that calFor year is not shared across multiple executions.

Attachments (1)

Main.hs (1.9 KB) - added by dspies 3 years ago.
Example Instance; Solution to https://open.kattis.com/problems/cargame

Download all attachments as: .zip

Change History (27)

comment:1 Changed 10 years ago by simonmar

Milestone: 6.6.2_|_

I don't think we're going to fix this any time soon. The simplifier is eta-expanding State# lambdas on purpose, because it's often critical for good performance of IO code, but it does risk re-computation in some cases, and this is one of those cases. Leaving the bug open because it is a real bug, someday we might implement something a bit more refined (e.g. arity analysis).

comment:2 Changed 10 years ago by simonmar

See also #1957.

comment:3 Changed 10 years ago by simonmar

Summary: nofib/spectral/calendar is mis-optimisedOptimisation sometimes decreases sharing in IO code

Changing the subject to indicate the real cause of the problem.

comment:4 Changed 9 years ago by ChrisKuklewicz

This just came up on the mailing list again. The program was slow unless (-fno-state-hack) was used.

Is it possible to have GHC emit a warning (as part of -Wall) to let the use know that GHC is applying a potentially risky simplification?

comment:5 Changed 9 years ago by simonmar

A warning would be good, but I see two potential problems:

  • there would be a lot of false positives
  • the warning has to be generated by the simplifier, and source-location information has been stripped off by this point, so we don't have a good way to report the location of the warning.

comment:7 Changed 9 years ago by simonpj

Cc: adam@… added

Adding Adam Jenkins to the cc list. At the end of the above thread he writes (reasonably enough):

Thank you for the explanation. Inlining does explain the behavior I was seeing, and -fno-state-hack does make the program behave the way I'd expect.

I would like to humbly submit that perhaps this optimization should be off by default. It seems to me that any compiler optimization which can potentially increase your program's runtime by an order of complexity is dangerous. Also, while the Haskell Report doesn't seem to specify anything about lazy evaluation behavior, it seems to me that in order to program in Haskell, assuming that a computation assigned to a variable won't be recomputed multiple times is almost as necessary an assumption as assuming that the compiler will optimize away tail recursion. For instance GHC FAQ entry 7.2 implicitly assumes this is true:

http://haskell.org/haskellwiki/GHC:FAQ#Does_GHC_do_common_subexpression_elimination.3F

In my real program where I ran into this problem it took me quite a while to figure out why my program's performance wasn't making any sense, and why seemingly irrelevant changes to my code made the performance problem go away.

comment:8 Changed 9 years ago by simonpj

I agree that the current behaviour sometimes bites badly, as it did for you here. Trouble is, removing the hack has (or used to have) a significant negative effect on performance of lots of programs.

Still, I think that there are various other possibilities to try. For example, compiling the I/O libraries (only) with the state-hack on, and with it off by default elsewhere, might gather most of the benefits without the costs. Or restricting it to top level functions. Or something like that.

It needs someone who's willing to do some measurements and try variations.

comment:9 Changed 9 years ago by simonpj

See also #2284

comment:10 Changed 9 years ago by guest

comment:11 Changed 9 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:12 Changed 9 years ago by simonmar

Operating System: UnknownUnknown/Multiple

comment:13 Changed 4 years ago by morabbin

Type of failure: None/Unknown

Seems to like nothing has changed here; #2284 is claimed as a dup of this ticket (#1168) in its comments, but not marked as such.

Doesn't seem like a bug though; more like a feature request.

comment:14 Changed 4 years ago by simonpj

See also #7561 for another example.

comment:15 Changed 3 years ago by simonpj

See #9349 for another example.

comment:16 Changed 3 years ago by klao

Cc: klao@… added

Changed 3 years ago by dspies

Attachment: Main.hs added

Example Instance; Solution to https://open.kattis.com/problems/cargame

comment:17 Changed 3 years ago by simonpj

David, it's be very helpful if you could

  • Specify the exact steps to reproduce the performance changes you see, with and without -fno-state-hack.
  • Say which version of GHC you are using

Thanks

Simon

comment:18 Changed 2 years ago by nomeata

See #10102 for another example (but nothing excitingly new there).

comment:19 Changed 22 months ago by thomie

See #10825 for another example.

comment:20 Changed 18 months ago by nomeata

See #11365 for another example, it seems.

comment:21 Changed 17 months ago by thomie

Type of failure: None/UnknownRuntime performance bug

comment:22 Changed 16 months ago by simonpj

See #11677 for another example

comment:23 Changed 15 months ago by simonpj

See #11795 for another example.

comment:24 Changed 15 months ago by simonpj

See #11271 for another example.

comment:25 Changed 15 months ago by simonpj

See #10401 too

comment:26 Changed 10 months ago by maoe

Cc: maoe added
Note: See TracTickets for help on using tickets.