Fix a nasty (and long-standing) FloatOut performance bug
authorsimonpj@microsoft.com <unknown>
Mon, 7 Dec 2009 08:32:46 +0000 (08:32 +0000)
committersimonpj@microsoft.com <unknown>
Mon, 7 Dec 2009 08:32:46 +0000 (08:32 +0000)
commit0d291233b14099032c6ffc87f8688abe9bd49f8a
tree23a23eea52dcb8acf4c5bf2c4244699ef767c07a
parent9ffe3c9076a96649eb4aef4795f9a15c8016dc2d
Fix a nasty (and long-standing) FloatOut performance bug

The effect was that, in deeply-nested applications, FloatOut would
take quadratic time.  A good example was compiling
    programs/barton-mangler-bug/Expected.hs
in which FloatOut had a visible pause of a couple of seconds!
Profiling showed that 40% of the entire compile time was being
consumbed by the single function partitionByMajorLevel.

The bug was that the floating bindings (type FloatBinds) was kept
as a list, which was partitioned at each binding site.  In programs
with deeply nested lists, such as
       e1 : e2 : e3 : .... : e5000 : []
this led to quadratic behaviour.

The solution is to use a proper finite-map representation;
see the new definition of FloatBinds near the bottom of FloatOut.
compiler/simplCore/FloatOut.lhs