Opened 9 years ago

Closed 4 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 Revisions:

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 9 years ago.

Download all attachments as: .zip

Change History (26)

comment:1 Changed 9 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 9 years ago by simonmar

  • Architecture changed from x86 to Multiple
  • Description modified (diff)
  • Operating System changed from Windows to Multiple
  • severity changed from major to normal
  • Summary changed from ghc internal error to performance 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 9 years ago by simonmar

comment:3 Changed 9 years ago by igloo

  • Milestone set to 6.8

Still a problem in 6.6 and the HEAD.

comment:4 Changed 8 years ago by simonmar

  • Priority changed from normal to high

comment:5 Changed 8 years ago by guest

  • Cc kyrab@… added

comment:6 Changed 8 years ago by guest

comment:7 Changed 8 years ago by simonmar

  • Priority changed from high to normal

comment:8 Changed 8 years ago by simonpj

  • Milestone changed from 6.8 branch to 6.8.3

See also #1875, #1136

comment:9 Changed 8 years ago by igloo

  • Keywords performance added

comment:10 Changed 8 years ago by simonmar

  • Type changed from bug to compile-time performance bug

comment:11 Changed 8 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 7 years ago by simonpj

  • Owner set to igloo
  • Type changed from compile-time performance bug to merge

OK I have fixed the immediate problem.

Thu Mar  6 13:47:34 GMT 2008  [email protected]
  * 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 <[email protected]>
      * 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 7 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 7 years ago by igloo

  • Type changed from merge to compile-time performance bug

comment:15 Changed 7 years ago by igloo

  • Owner igloo deleted

comment:16 Changed 7 years ago by igloo

  • Milestone changed from 6.8.3 to 6.10.1

comment:17 Changed 7 years ago by simonmar

  • Architecture changed from Multiple to Unknown/Multiple

comment:18 Changed 7 years ago by simonmar

  • Operating System changed from Multiple to Unknown/Multiple

comment:19 Changed 7 years ago by igloo

  • Milestone changed from 6.10.1 to 6.10.2

comment:20 Changed 6 years ago by igloo

  • Milestone changed from 6.10.2 to 6.12.1

comment:21 Changed 6 years ago by simonmar

  • Milestone changed from 6.12.1 to 6.14.1
  • Summary changed from performance problem compiling large file to SRTs bigger than they should be?
  • Type changed from compile-time performance bug to run-time performance bug

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

comment:22 Changed 6 years ago by simonmar

  • Type of failure set to Runtime performance bug

comment:23 Changed 5 years ago by simonmar

  • Blocked By 4258 added
  • Milestone changed from 7.0.1 to 7.2.1

comment:24 Changed 4 years ago by simonmar

  • Blocked By 4258 removed
  • Owner set to simonmar
  • Test Case set to 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 4 years ago by simonmar

  • Resolution set to fixed
  • Status changed from new to closed
Note: See TracTickets for help on using tickets.