Opened 11 years ago

Closed 11 years ago

Last modified 10 years ago

#2680 closed bug (fixed)

Type-checking performance regression

Reported by: igloo Owned by:
Priority: high Milestone: 6.10.1
Component: Compiler (Type checker) Version: 6.8.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Attached is a module Def1, which defines a load of type synonyms and some values, and a module !ReExport1, which just re-exports Def1.

6.10 is comparable to 6.8 when compiling Def1, but rather than taking a couple of seconds to compile !ReExport1 it takes about 3 minutes.

Def2/ReExport2 are the same, but only contain the type synonyms. The difference in this case is 1 second vs 30 seconds.

GHC 6.8.2:

$ rm *.o; rm *.hi
$ time $GHC -O -fforce-recomp -c Def1.hs
$GHC -O -fforce-recomp -c Def1.hs  36.00s user 0.82s system 100% cpu 36.717 total
$ time $GHC -O -fforce-recomp -c ReExport1.hs
$GHC -O -fforce-recomp -c ReExport1.hs  2.22s user 0.11s system 100% cpu 2.332 total
$ time $GHC -O -fforce-recomp -c Def2.hs
$GHC -O -fforce-recomp -c Def2.hs  7.20s user 0.14s system 99% cpu 7.340 total
$ time $GHC -O -fforce-recomp -c ReExport2.hs
$GHC -O -fforce-recomp -c ReExport2.hs  0.99s user 0.08s system 100% cpu 1.075 total
$ $GHC --version
The Glorious Glasgow Haskell Compilation System, version 6.8.2

6.10 branch:

$ rm *.o; rm *.hi
$ time $GHC -O -fforce-recomp -c Def1.hs
$GHC -O -fforce-recomp -c Def1.hs  35.94s user 0.60s system 100% cpu 36.350 total
$ time $GHC -O -fforce-recomp -c ReExport1.hs
$GHC -O -fforce-recomp -c ReExport1.hs  169.35s user 0.28s system 99% cpu 2:49.67 total
$ time $GHC -O -fforce-recomp -c Def2.hs
$GHC -O -fforce-recomp -c Def2.hs  8.37s user 0.11s system 100% cpu 8.477 total
$ time $GHC -O -fforce-recomp -c ReExport2.hs
$GHC -O -fforce-recomp -c ReExport2.hs  29.11s user 0.10s system 99% cpu 29.258 total
$ $GHC --version                                
The Glorious Glasgow Haskell Compilation System, version 6.10.0.20081009

Attachments (4)

Def1.hs.gz (162.6 KB) - added by igloo 11 years ago.
ReExport1.hs (51 bytes) - added by igloo 11 years ago.
Def2.hs.gz (81.9 KB) - added by igloo 11 years ago.
ReExport2.hs (51 bytes) - added by igloo 11 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 11 years ago by igloo

This is a cutdown version of type-level-0.2.2 from hackage, incidentally.

Changed 11 years ago by igloo

Attachment: Def1.hs.gz added

Changed 11 years ago by igloo

Attachment: ReExport1.hs added

Changed 11 years ago by igloo

Attachment: Def2.hs.gz added

Changed 11 years ago by igloo

Attachment: ReExport2.hs added

comment:2 Changed 11 years ago by simonpj

That's very mysterious -- and highly terrible. When compiling ReExport1.hs I get past tidy-core very fast, and then it gets totally stuck. Do you have a profiled compiler to see what it's up to? My guess is that there's a very non-linear algorithm in the interface file generation.

Simon

comment:3 Changed 11 years ago by duncan

A possibly releated real test case is the Vec library from hackage. We noticed that takes a long time to build which we didn't notice with 6.8.

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Vec

Another one that is much much slowe to compile with 6.10 vs 6.8 is WURFL. However that looks more likely to be a parser issue than typechecking. It's got large amounts of generated code.

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/WURFL

comment:4 Changed 11 years ago by igloo

The problem is in the creation of ent_map in iface/MkIface:mk_usage_info. In this case, all of the mods are the same, so extendModuleEnv_C (++) mv_map mod [occ] builds the list of them quadratically. Using (flip (++)) brings the time down to a couple of seconds. It doesn't look to me like the order of elements should be important here, but can you confirm please?

hunk ./compiler/iface/MkIface.lhs 821
-             Just mod -> extendModuleEnv_C (++) mv_map mod [occ]
+             Just mod -> extendModuleEnv_C (flip (++)) mv_map mod [occ]

comment:5 Changed 11 years ago by igloo

Vec isn't the same problem. There's a twisty maze of fundeps and undecidable instances is on; I'm not sure if the problem is in the code or GHC. If anyone wants to look, the Det' instance starting on line 371 of Data/Vec/LinAlg.hs seems to be the (or at least, a) cause of non-termination.

comment:6 Changed 11 years ago by igloo

WURFL looks like a non-regression to me. I get a stack overflow with 6.8 and 6.10 when compiling with optimisation, and they both compile in ~40 seconds with optimisation off.

The problem is a huge datastructure, which we have other tickets for.

comment:7 in reply to:  4 Changed 11 years ago by simonmar

Replying to igloo:

The problem is in the creation of ent_map in iface/MkIface:mk_usage_info. In this case, all of the mods are the same, so extendModuleEnv_C (++) mv_map mod [occ] builds the list of them quadratically. Using (flip (++)) brings the time down to a couple of seconds. It doesn't look to me like the order of elements should be important here, but can you confirm please?

hunk ./compiler/iface/MkIface.lhs 821
-             Just mod -> extendModuleEnv_C (++) mv_map mod [occ]
+             Just mod -> extendModuleEnv_C (flip (++)) mv_map mod [occ]

Nice catch!

That should be fine, although it's only a few extra characters to write

  extendModuleEnv_C (\xs _ -> occ:xs) mv_map mod [occ]

which is a tad more efficient, and clearer to me.

comment:8 Changed 11 years ago by igloo

Resolution: fixed
Status: newclosed

Fixed in HEAD and 6.10.

comment:9 Changed 10 years ago by simonmar

Type of failure: Compile-time performance bug
Note: See TracTickets for help on using tickets.