Opened 2 years ago

Closed 2 years ago

Last modified 2 years ago

#5997 closed bug (duplicate)

GHC fails to make function tail recursive

Reported by: Khudyakov Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.4.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Difficulty: Unknown
Test Case: simplCore/should_run/T5997 Blocked By:
Blocking: Related Tickets:

Description

Sometimes GHC does not compile function as tail recursive despite it looks like tail recursive. Here is simplified example.

{-# LANGUAGE BangPatterns #-}

incompleteBetaWorker :: Double -> Double
incompleteBetaWorker _ = loop 1 1 1 1
  where
    -- Constants
    eps = 1e-15
    -- Loop
    loop :: Double -> Int -> Double -> Double -> Double
    loop !psq !ns !term !betain
      | done      = betain'
      | otherwise = loop psq' (ns - 1) term' betain'
      where
        -- New values
        term'   = term
        betain' = betain
        psq'    = if ns < 0 then psq + 1 else psq
        -- This condition cause stack overflow
        done = db <= eps && db <= eps*betain' where db = abs term'
        -- With this it loops endlessly
        -- done = db <= eps * betain' where db = abs term'

main :: IO ()
main = print $ incompleteBetaWorker 0

If second equation for done is used function is tail recursive and works in constant space. if first one (uncommented) is used it isn't. From looking at the it looks loop is converted to several corecursive functions.

Such loops appear frequently in numerical code and it's important to ensure that worker function is tail recursive since getting answer may require a lot of iteration.

I've tested it with GHC 7.2.2 and 7.4.1. Both are affected. Example was compiled with -O2.

Change History (3)

comment:1 Changed 2 years ago by simonpj

  • Difficulty set to Unknown
  • Resolution set to duplicate
  • Status changed from new to closed

Thanks. Turns out to be a dup of #5920. But I'll add this as a second test case.

comment:2 Changed 2 years ago by simonpj@…

commit b8ff4448d899f783fc112f3774aab626979a4f22

Author: Simon Peyton Jones <simonpj@microsoft.com>
Date:   Fri Apr 13 17:38:32 2012 +0100

    Fix worker/wrapper for CPR functions
    
    A long-standing and egregious bug in the worker/wrapper code meant
    that some functions with the CPR property weren't getting a CPR
    w/w. And that had the effect of making a tail-recursive function not
    tail recursive.  As well as increasing allocation.
    
    Fixes Trac #5920, and #5997.
    
    Nofib results (highlights):
    
            Program           Size    Allocs   Runtime   Elapsed  TotalMem
    --------------------------------------------------------------------------------
             boyer2          -0.1%    -15.3%      0.01      0.01     +0.0%
            mandel2          -0.0%     -8.1%      0.01      0.01     +0.0%
               para          -0.1%    -11.8%     -7.9%     -7.8%     +0.0%
    --------------------------------------------------------------------------------
                Min          -0.1%    -15.3%     -7.9%     -7.8%    -33.3%
                Max          +0.0%     +0.2%     +6.3%     +6.3%     +3.7%
     Geometric Mean          -0.0%     -0.4%     +0.1%     +0.1%     -0.5%
    
    Looks like a clear win.  And I have not even recompiled the libraries, so
    it'll probably be a bit better in the ed.

 compiler/stranal/DmdAnal.lhs |   13 ++++++-------
 compiler/stranal/WwLib.lhs   |   25 ++++++++++++++++---------
 2 files changed, 22 insertions(+), 16 deletions(-)

comment:3 Changed 2 years ago by simonpj

  • Test Case set to simplCore/should_run/T5997
Note: See TracTickets for help on using tickets.