Type-checking performance regression

[igloo]

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

[igloo]

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

[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

[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

[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]

[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.

[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.

[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.

[igloo]

Fixed in HEAD and 6.10.