Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Mirror of ghc repository. DO NOT SUBMIT PULL REQUESTS HERE. Patches are best submitted to GHC's Phabricator (https://phabricator.haskell.org/), bugs and feature-requests are best filed to GHC's Trac (https://ghc.haskell.org/trac/ghc), or sent to the mailing list (ghc-devs@haskell.org)
Haskell C Makefile Perl6 Perl Logos Other
branch: master

Fix a huge space leak in the mighty Simplifier

This long-standing, terrible, adn somewhat subtle bug was exposed
by Trac #10370, thanks to Reid Barton's brilliant test case (comment:3).

The effect is large on the Trac #10370 test.
Here is what the profile report says:

Before:
 total time  =       24.35 secs   (24353 ticks @ 1000 us, 1 processor)
 total alloc = 11,864,360,816 bytes  (excludes profiling overheads)

After:
 total time  =       21.16 secs   (21160 ticks @ 1000 us, 1 processor)
 total alloc = 7,947,141,136 bytes  (excludes profiling overheads)

The /combined/ effect of the tidyOccName fix, plus this one, is dramtic
for Trac #10370.  Here is what +RTS -s says:

Before:
  15,490,210,952 bytes allocated in the heap
   1,783,919,456 bytes maximum residency (20 sample(s))

  MUT     time   30.117s  ( 31.383s elapsed)
  GC      time   90.103s  ( 90.107s elapsed)
  Total   time  120.843s  (122.065s elapsed)

After:
   7,928,671,936 bytes allocated in the heap
      52,914,832 bytes maximum residency (25 sample(s))

  MUT     time   13.912s  ( 15.110s elapsed)
  GC      time    6.809s  (  6.808s elapsed)
  Total   time   20.789s  ( 21.954s elapsed)

- Heap allocation halved
- Residency cut by a factor of more than 30.
- ELapsed time cut by a factor of 6

Not bad!

The details
~~~~~~~~~~~
The culprit was SimplEnv.mkCoreSubst, which used mapVarEnv to do some
impedence-matching from the substitituion used by the simplifier to
the one used by CoreSubst.  But the impedence-mactching was recursive!

  mk_subst tv_env cv_env id_env
    = CoreSubst.mkSubst in_scope tv_env cv_env (mapVarEnv fiddle id_env)

  fiddle (DoneEx e)          = e
  fiddle (DoneId v)          = Var v
  fiddle (ContEx tv cv id e) = CoreSubst.substExpr (mk_subst tv cv id) e

Inside fiddle, in the ContEx case, we may do another whole level of
fiddle.  And so on.  Moreover, UniqFM (which is built on Data.IntMap) is
strict, so the fiddling is done eagerly.  I didn't wok through all the
details but the result is a gargatuan blow-up of entirely unnecessary work.

Laziness would make this go away, I think, but I don't want to mess
with IntMap.  And in any case, the impedence matching is a royal pain.

In the end I simply ceased trying to use CoreSubst.substExpr in the
simplifier, and instead just use simplExpr.  That does mean bit of
duplication; e.g.  new code for simplRules.  But it's not a big deal
and it's far more direct and easy to reason about.

A bit of knock-on refactoring:

 * Data type ArgSummary moves to CoreUnfold.

 * interestingArg moves from CoreUnfold to SimplUtils, and gets a
   SimplEnv argument which can be used when we encounter a variable.

 * simplLamBndrs, addBndrRules move from SimplEnv to Simplify
   (because they now calls simplUnfolding, simplRules resp)

 * SimplUtils.substExpr, substUnfolding, mkCoreSubst die completely

 * In Simplify some several functions that were previously pure
   substitution-based functions are now monadic:
     - addBndrRules, simplRule
     - addCoerce, add_coerce in simplCast

 * In case 2c of Simplify.rebuildCase, there was a pretty disgusting
   expression-substitution taking place for 'rhs'; and we really don't
   want to make that monadic becuase 'rhs' can be big.
   Solution: reduce the arity of the rules for seq.
   See Note [User-defined RULES for seq] in MkId.
latest commit 45d9a15c4b
@simonpj simonpj authored
Failed to load latest commit information.
bindisttest Follow-up to 32f41c7
compiler Fix a huge space leak in the mighty Simplifier
distrib configure : LLVM and LD detections improvements (#10234).
docs Backpack docs: Clarifications from today's Skype call.
driver Shorten long lines in DynFlags, add details to ghci usage guide.
ghc ghci: Allow :back and :forward to take counts
includes Add a TODO FIXME w.r.t. D894
libffi-tarballs @ b6658e5 Update libffi-tarballs submodule to libffi 3.1 (re #8701)
libffi libffi: backport noexecstack fix for x86/win32.S
libraries Fix error messages from open(Binary)TempFileWithDefaultPermissions
mk Make template-haskell build with GHC 7.6, fixes bootstrap build.
nofib @ 85d10a4 update submodule
rts rts: add "-no-rtsopts-suggestions" option
rules Drop old integer-gmp-0.5 from GHC source tree
testsuite Fix a huge space leak in the mighty Simplifier
utils Refactor tuple constraints
.arcconfig Fix .arcconfig
.arclint Cabal submodule update: hole support and tests.
.gitignore Ignore temporary ./configure files.
.gitmodules Delete old-{time,locale} and haskell{98,2010}
.mailmap Add remaining <unknown>s and comments to .mailmap
.travis.yml travis: Get libstdc++ from a more sensible location
ANNOUNCE Globally replace "hackage.haskell.org" with "ghc.haskell.org"
HACKING.md Update `sync-all` and others files w.r.t. merged testsuite (re #8545)
INSTALL.md docs: add INSTALL.md to root dir (#9926)
LICENSE Reorganisation of the source tree
MAKEHELP.md docs: Flatten MAKEHELP/SUBMAKEHELP
Makefile build: fix 'make help'
README.md Explain how to clone GitHub forks. Ticket #8379.
Vagrantfile vagrant: move files around
aclocal.m4 arm: Force non-executable stack (part 2)
boot Replace all #!/usr/bin/perl with #!/usr/bin/env perl
config.guess Update config.{guess,sub} to GNU automake 1.14.1
config.sub Update config.{guess,sub} to GNU automake 1.14.1
configure.ac configure : LLVM and LD detections improvements (#10234).
ghc.mk Support stage 1 Template Haskell (non-quasi) quotes, fixes #10382.
install-sh Update aux files `config.{guess,sub}` and `install-sh`
packages Declare official GitHub home of libraries/parallel
settings.in LlvmCodeGen cross-compiling fixes (#9895)
sync-all Cleanup and better documentation of sync-all script
tarballs Add tarball syncing to darcs-all
validate testdriver: delete unused ways

README.md

The Glasgow Haskell Compiler

Build Status

This is the source tree for GHC, a compiler and interactive environment for the Haskell functional programming language.

For more information, visit GHC's web site.

Information for developers of GHC can be found on the GHC Trac.

Getting the Source

There are two ways to get a source tree:

  1. Download source tarballs

    Download the GHC source distribution:

      ghc-<version>-src.tar.bz2
    

    which contains GHC itself and the "boot" libraries.

  2. Check out the source code from git

    The official mirror for GHC on GitHub is located at https://github.com/ghc/ghc.

      $ git clone git://github.com/ghc/ghc.git
      $ cd ghc
      $ ./sync-all get
    

    If you want to clone your own fork instead, add an argument to sync-all to tell it where it can find the other repositories it needs.

      $ git clone <your preferred github.com GHC fork URL> ghc
      $ cd ghc
      $ ./sync-all -r git://github.com/ghc get
    

    DO NOT submit pull request directly to the github repo. See the GHC developer team's working conventions re contributing patches.

Building & Installing

For full information on building GHC, see the GHC Building Guide. Here follows a summary - if you get into trouble, the Building Guide has all the answers.

Before building GHC you may need to install some other tools and libraries. See, Setting up your system for building GHC.

NB. In particular, you need GHC installed in order to build GHC, because the compiler is itself written in Haskell. You also need Happy, Alex, and Cabal. For instructions on how to port GHC to a new platform, see the GHC Building Guide.

For building library documentation, you'll need Haddock. To build the compiler documentation, you need a good DocBook XML toolchain and dblatex.

Quick start: the following gives you a default build:

$ perl boot
$ ./configure
$ make         # can also say 'make -jX' for X number of jobs
$ make install

(NB: Do you have multiple cores? Be sure to tell that to make! This can save you hours of build time depending on your system configuration, and is almost always a win regardless of how many cores you have. As a simple rule, you should have about N+1 jobs, where N is the amount of cores you have.)

The perl boot step is only necessary if this is a tree checked out from git. For source distributions downloaded from GHC's web site, this step has already been performed.

These steps give you the default build, which includes everything optimised and built in various ways (eg. profiling libs are built). It can take a long time. To customise the build, see the file HACKING.

Once you have a build you need to keep it going. You need to keep all repos in sync with the sync-all script. To get the latest changes:

$ ./sync-all pull
$ ./sync-all get

Filing bugs and feature requests

If you've encountered what you believe is a bug in GHC, or you'd like to propose a feature request, please let us know! Submit a ticket in our bug tracker and we'll be sure to look into it. Remember: Filing a bug is the best way to make sure your issue isn't lost over time, so please feel free.

If you're an active user of GHC, you may also be interested in joining the glasgow-haskell-users mailing list, where developers and GHC users discuss various topics and hang out.

Hacking & Developing GHC

Once you've filed a bug, maybe you'd like to fix it yourself? That would be great, and we'd surely love your company! If you're looking to hack on GHC, check out the guidelines in the HACKING.md file in this directory - they'll get you up to speed quickly.

Contributors & Acknowledgements

GHC in its current form wouldn't exist without the hard work of its many contributors. Over time, it has grown to include the efforts and research of many institutions, highly talented people, and groups from around the world. We'd like to thank them all, and invite you to join!

Something went wrong with that request. Please try again.