Skip to content
  • Simon Peyton Jones's avatar
    Fix an asymptotic bug in the occurrence analyser · 517d03e4
    Simon Peyton Jones authored
    Trac #12425 and #12234 showed up a major and long-standing
    bug in the occurrence analyser, whereby it could generate
    explonentially large program!
    
    There's a lot of commentary on #12425; and it's all described
    in Note [Loop breakers, node scoring, and stability]
    
    I did quite a lot of refactoring to make the code comprehensibe
    again (its structure had bit-rotted rather), so the patch
    looks bigger than it really is.
    
    Hurrah!
    
    I did a nofib run to check that I hadn't inadertently ruined
    anything:
    
    --------------------------------------------------------------------------------
            Program           Size    Allocs   Runtime   Elapsed  TotalMem
    --------------------------------------------------------------------------------
              fluid          -0.3%     -1.5%      0.01      0.01     +0.0%
             parser          -0.9%     +0.6%      0.04      0.04     +0.0%
             prolog          -0.1%     +1.2%      0.00      0.00     +0.0%
    
    --------------------------------------------------------------------------------
                Min          -0.9%     -1.5%     -8.6%     -8.7%     +0.0%
                Max          +0.1%     +1.2%     +7.7%     +7.8%     +2.4%
     Geometric Mean          -0.2%     -0.0%     -0.2%     -0.3%     +0.0%
    
    I checked what happened in 'prolog'.  It seems that we have a
    recursive data structure something like this
    
       f :: [blah]
       f x = build (\cn.  ...g...  )
    
       g :: [blah2]
       g y = ....(foldr k z (f y))....
    
    If we inline 'f' into 'g' we get better fusion than the other
    way round, but we don't have any way to spot that at the moment.
    (I wonder if we could do worker/wrapper for functions returning
    a 'build'?)  It was happening before by a fluke.
    
    Anyway I decided to accept this; it's relatively rare I think.
    517d03e4