Skip to content
  • Simon Peyton Jones's avatar
    Fix a nasty (and long-standing) FloatOut performance bug · 0d291233
    Simon Peyton Jones authored
    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.
    0d291233