Opened 11 years ago

Closed 5 years ago

#783 closed bug (fixed)

SRTs bigger than they should be?

Reported by: guest Owned by: simonmar
Priority: normal Milestone: 7.4.1
Component: Compiler Version: 6.4.2
Keywords: performance Cc: kyrab@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case: T783
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by simonmar)

Windows XP, GHC 6.4.2 binary package.

Will attach the relevant module.

...
Compiling Dist             ( ./Dist.hs, ./Dist.o )
ghc: internal error: update_fwd: unknown/strange object  0
    Please report this as a compiler bug.  See:
    http://www.haskell.org/ghc/reportabug

Attachments (1)

Dist.hs (133.6 KB) - added by simonmar 11 years ago.

Download all attachments as: .zip

Change History (26)

comment:1 Changed 11 years ago by drtom@…

As well as triggering the internal error, I found it necessary to increase the heap size, and it took *AGES*. So, I guess it's two bugs - the internal error and the performance bug.

cheers, Tom

comment:2 Changed 11 years ago by simonmar

Architecture: x86Multiple
Description: modified (diff)
Operating System: WindowsMultiple
severity: majornormal
Summary: ghc internal errorperformance problem compiling large file

I'm 99% certain the crash has been fixed; see #787. However I tried the attached file, and it loaded without error on my 6.4.2 installation here.

Changing the title to reflect the performance problem, this is definitely an issue.

Changed 11 years ago by simonmar

Attachment: Dist.hs added

comment:3 Changed 10 years ago by igloo

Milestone: 6.8

Still a problem in 6.6 and the HEAD.

comment:4 Changed 10 years ago by simonmar

Priority: normalhigh

comment:5 Changed 10 years ago by guest

Cc: kyrab@… added

comment:6 Changed 10 years ago by guest

comment:7 Changed 9 years ago by simonmar

Priority: highnormal

comment:8 Changed 9 years ago by simonpj

Milestone: 6.8 branch6.8.3

See also #1875, #1136

comment:9 Changed 9 years ago by igloo

Keywords: performance added

comment:10 Changed 9 years ago by simonmar

Type: bugcompile-time performance bug

comment:11 Changed 9 years ago by igloo

With a slightly simpler variant of this:

module Foo where

foo :: Double -> Int
foo x | x == 1 = 1
foo x | x == 2 = 2
...
foo x | x == 500 = 500

compiling with

ghc -c large.hs -fforce-recomp +RTS -p -h

one problem is that we get something like

lit1 = ...
lit2 = ...
...

foo = case ... of
          False ->
              case ... of
                  False -> ...
                  True -> lit2
          True -> lit1

Each of the case expressions has an SRT for its alternatives. The outer one has all 500 lit's, the one inside 499, and so on, so we have quadratic space usage. The SRTs are SRTEntries cafs, where cafs is an IdSet (which is ultimately a UniqFM), so no sharing is possible.

In this particular case using -O "fixes" it as == etc get specialised and the lits disappear, but (a) this won't be the case in general and (b) I don't think you should need to use -O to get reasonable compiler space usage.

comment:12 Changed 9 years ago by simonpj

Owner: set to igloo
Type: compile-time performance bugmerge

OK I have fixed the immediate problem.

Thu Mar  6 13:47:34 GMT 2008  simonpj@microsoft.com
  * Fix Trac #783: improve short-cutting literals in the type checker

Ian can you merge, and (somehow) add a test case to the test suite?

I'm not sure how to fully solve the quadratic behaviour in general. The reason that the lits were appearing in the SRT is because the dictionary for Num Float has a CAF in it. So, as Ian says, there really are N sub-SRTs for the various stages of evaluation. However things are now less bad than before:

  • Ian has made the SRTs use bitmaps:
    Wed Feb 27 06:45:05 PST 2008  Ian Lynagh <igloo@earth.li>
      * Add and use seqBitmap when constructing SRTs
    
  • The above patch from me makes the literal problem go away for Float and Double (common cases)

However, as Simon M says, I'm not sure why the N sub-SRTS don't all share a single table, and that should really kill off the quadratic behaviour in this case. That is the remaining bit that would be worth investigating. Maybe leave the ticket open for that.

Simon

comment:13 Changed 9 years ago by igloo

I've merged the patch.

Also, just to clarify, the patch Add and use seqBitmap when constructing SRTs is actually in a later stage of the compiler (although I did find that problem while looking at this bug). Going directly to a bitmap, rather than first making the SRTEntries, might be a way to fix this bug.

comment:14 Changed 9 years ago by igloo

Type: mergecompile-time performance bug

comment:15 Changed 9 years ago by igloo

Owner: igloo deleted

comment:16 Changed 9 years ago by igloo

Milestone: 6.8.36.10.1

comment:17 Changed 8 years ago by simonmar

Architecture: MultipleUnknown/Multiple

comment:18 Changed 8 years ago by simonmar

Operating System: MultipleUnknown/Multiple

comment:19 Changed 8 years ago by igloo

Milestone: 6.10.16.10.2

comment:20 Changed 8 years ago by igloo

Milestone: 6.10.26.12.1

comment:21 Changed 7 years ago by simonmar

Milestone: 6.12.16.14.1
Summary: performance problem compiling large fileSRTs bigger than they should be?
Type: compile-time performance bugrun-time performance bug

We should look at the SRTs in this example with the new code generator.

comment:22 Changed 7 years ago by simonmar

Type of failure: Runtime performance bug

comment:23 Changed 6 years ago by simonmar

Blocked By: 4258 added
Milestone: 7.0.17.2.1

comment:24 Changed 5 years ago by simonmar

Blocked By: 4258 removed
Owner: set to simonmar
Test Case: T783

This ticket was still open because we wanted to check that there was no bad SRT behaviour. I've checked various versions of the example code and I can't find any bad behaviour, so I'm adding the program as a test case and closing the ticket. If the bad case pops up again with the new code generator, the test will fail.

comment:25 Changed 5 years ago by simonmar

Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.