Opened 4 years ago

Closed 16 months ago

#4321 closed bug (fixed)

Unexpected stack overflow prevented by superfluous type annotation

Reported by: bjpop Owned by: simonpj
Priority: high Milestone: 7.6.2
Component: Compiler Version: 7.5
Keywords: Cc: daniel.is.fischer@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Difficulty: Unknown
Test Case: T4321 Blocked By:
Blocking: Related Tickets:

Description (last modified by igloo)

GHC versions affected:

  • 6.13.20100915
  • 6.13.20090922
  • 6.12.1
  • 6.10.4

OS versions tested:

  • OS X Snow Leopard
  • Ubuntu Linux 9.10 - Karmic Koala

Description:

The attached program computes Pi by integrating 4/(1+x*x) between 0 and 1.

The important line of code is this one:

h * (sum (map area [1..n]))

If you compile the program as it is, with this command:

ghc --make -O2 Pi.hs

it runs out of stack space when run like so:

./Pi 1000000

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

For GHC versions 6.10.4, 6.12.1 and 6.13.20090922
However, if you add what appears to be a superfluous type annotation to the line of code, like so:

h * ((sum (map area [1..n])) :: Double)

The program runs to completion with no stack overflow:

./Pi 1000000
3.1415926535897643

Indeed it works just fine for even larger inputs.

However version 6.13.20100915 overflows the stack regardless of whether the type annotation is present or not.

I don't think the type annotation should make any difference to the generated code because GHC should infer that the annotated expression is of type Double anyway (if you put an erroneous type in the same place, GHC complains that it should be a Double).

Attachments (1)

Pi.hs (427 bytes) - added by bjpop 4 years ago.
Source code of Haskell program which induces bug

Download all attachments as: .zip

Change History (22)

Changed 4 years ago by bjpop

Source code of Haskell program which induces bug

comment:1 Changed 4 years ago by simonpj

  • Owner set to igloo

Thanks. Turned out that HEAD was a little less keen to inline than 6.12. I've fixed that.

Thu Sep 23 14:00:32 BST 2010  simonpj@microsoft.com
  * Make -funfolding-dict-threshold work properly
  
  and increase its default value. This makes overloaded functions
  a bit keener to inline.  Which fixes Trac #4321

Happily HEAD then behaves the same whether or not there is a pragma.

Ian: could you add this as a test, which will blow up if things go wrong atain? Thanks. The difference in runtime or allocation is fairly stark, so you don't even need to look for stack overflow.

Simon

comment:2 Changed 4 years ago by igloo

  • Resolution set to fixed
  • Status changed from new to closed
  • Test Case set to T4321

Test added.

comment:3 Changed 4 years ago by daniel.is.fischer

  • Cc daniel.is.fischer@… added
  • Owner igloo deleted
  • Resolution fixed deleted
  • Status changed from closed to new

My GHCs from 6.8.3 to HEAD all agree that the last two digits of the result should be swapped.
Could it be an architecture issue or is it possible that the result has been typo'ed?

comment:4 Changed 4 years ago by simonpj

Ian, I guess you added the expected result?

comment:5 Changed 4 years ago by simonpj

  • Owner set to igloo

comment:6 Changed 4 years ago by igloo

Daniel, what platform are you on?

It looks right here:

$ '/home/ian/ghc/7.0-branch/ghc/inplace/bin/ghc-stage2' -fforce-recomp -dcore-lint -dcmm-lint -dno-debug-output -no-user-package-conf -rtsopts  -o T4321 T4321.hs  -O
$ ./T4321 
3.1415926535897643
$ cat T4321.stdout         
3.1415926535897643

(and similarly passes all ways), and is run the "normal" way as part of validate, so I imagine works on the other common platforms too.

comment:7 Changed 4 years ago by daniel.is.fischer

I'm on i686, linux (openSUSE 11.1).
ghc-6.12.3:

dafis@linux-mkk1:~/Haskell/Hacking/liststuff/testsuite/tests/ghc-regress/perf/should_run> ghc -O -fforce-recomp --make T4321
[1 of 1] Compiling Main             ( T4321.hs, T4321.o )
Linking T4321 ...
dafis@linux-mkk1:~/Haskell/Hacking/liststuff/testsuite/tests/ghc-regress/perf/should_run> ./T4321
3.1415926535897634

Today's HEAD:

dafis@linux-mkk1:~/Haskell/Hacking/liststuff/testsuite/tests/ghc-regress/perf/should_run> ~/Haskell/Hacking/liststuff/inplace/bin/ghc-stage2 --version
The Glorious Glasgow Haskell Compilation System, version 7.1.20101019
dafis@linux-mkk1:~/Haskell/Hacking/liststuff/testsuite/tests/ghc-regress/perf/should_run> ~/Haskell/Hacking/liststuff/inplace/bin/ghc-stage2 -O --make T4321
[1 of 1] Compiling Main             ( T4321.hs, T4321.o )
Linking T4321 ...
dafis@linux-mkk1:~/Haskell/Hacking/liststuff/testsuite/tests/ghc-regress/perf/should_run> ./T4321
3.1415926535897634

I get the same result with C, via C, with or without excess-precision...

Platform issue, then. Print it only with 14 places of precision?

comment:8 Changed 4 years ago by igloo

  • Resolution set to fixed
  • Status changed from new to closed

7.0.1 RC 1 works for me on i386, with the -msse2 flag.

comment:9 Changed 4 years ago by daniel.is.fischer

Yup, -msse2 works here too.

comment:10 Changed 3 years ago by daniel.is.fischer

  • Owner igloo deleted
  • Resolution fixed deleted
  • Status changed from closed to new

Urk, doesn't work for optc here:

=====> T4321(optc) 2241 of 2622 [0, 10, 0]
cd ./perf/should_run && '/home/dafis/Haskell/Hacking/newghc/bindisttest/install dir/bin/ghc' -fforce-recomp -dcore-lint -dcmm-lint -dno-debug-output -no-user-package-conf -rtsopts -optl-lz -o T4321 T4321.hs -O -fno-warn-deprecated-flags -fvia-C -O -msse2  >T4321.comp.stderr 2>&1
cd ./perf/should_run && ./T4321    </dev/null >T4321.run.stdout 2>T4321.run.stderr
Actual stdout output differs from expected:
--- ./perf/should_run/T4321.stdout.normalised	2010-10-25 02:41:59.000000000 +0200
+++ ./perf/should_run/T4321.run.stdout.normalised	2010-10-25 02:41:59.000000000 +0200
@@ -1 +1 @@
-3.1415926535897643
+3.1415926535897634
*** unexpected failure for T4321(optc)

(ghc-7.1.20101024)

Perhaps an -optc-msse2 is needed?

comment:11 Changed 3 years ago by simonmar

-msse2 has no effect when using -fvia-C. However, we do use -ffloat-store with the C backend which should mean that you get predictable floating point results, so I'm not sure what's going on here.

comment:12 Changed 3 years ago by daniel.is.fischer

I've no idea. compiling

#include <stdio.h>
#include <stdlib.h>

static double integrate(int n, double h){
    int i;
    double x, sm = 0.0;
    for(i = 1; i <= n; ++i){
        x = h*((double)i-0.5);
        sm += 4.0 / (1.0 + x*x);
    }
    return h*sm;
}

int main(int argc, char *argv[]){
    int num = 1000000;
    if (argc > 1){
        num = atoi(argv[1]);
    }
    printf("%.16f\n",integrate(num,1.0/num));
    return EXIT_SUCCESS;
}

$ gcc -ffloat-store -o vbjpi vbjpi.c
$ ./vbjpi
3.1415926535897634

both, with gcc-4.3.2 and gcc-4.4.1, also with icc -O0. So it seems to be something my C compilers do.

comment:13 Changed 3 years ago by igloo

  • Description modified (diff)

comment:14 Changed 3 years ago by igloo

  • Milestone set to 7.2.1

comment:15 Changed 3 years ago by daniel.is.fischer

  • Resolution set to fixed
  • Status changed from new to closed

Closing this, via-C is going/gone. Although I still get ...34 on my 32-bit box with gcc-4.5.0 (openSuSE 11.3) and ghc-7.0.4 when compiling via C. Very odd.

comment:16 Changed 2 years ago by michalt

  • Resolution fixed deleted
  • Status changed from closed to new

Unfortunately the current HEAD fails T4321 for me due to stack overflow. It
seems that the problem is similar -- sum doesn't get inlined by current
HEAD whereas GHC 7.4 does inline it.

Maybe I'm missing something, but it seems to me that an easy fix would be to
slightly modify the definition of sum:

sum     l       = sum' l 0
  where
    sum' []     a = a
    sum' (x:xs) a = sum' xs (a+x)

by making sum' strict in the second argument or by defining it as
foldl' (+) 0. Is there any reason not to do that?

comment:17 Changed 2 years ago by igloo

  • Difficulty set to Unknown
  • Milestone changed from 7.4.1 to 7.6.1
  • Priority changed from normal to high
  • Version changed from 6.13 to 7.5

comment:18 Changed 2 years ago by simonpj

I got part way throught fixing this before getting distracted. My partial patch is below.

But this still doesn't quite fix
it becase the (new) trivial wrappers aren't inlined until after specialisation
so the opportunity is missed. The solution is to be a bit more eager about inlining in "gentle" mode (perhaps by inlining all INLINE things), but that takes more time than I have today, so I'm capturing the state of play here.

diff --git a/Data/List.hs b/Data/List.hs
index 9f5001f..8cecf78 100644
--- a/Data/List.hs
+++ b/Data/List.hs
@@ -1027,10 +1027,6 @@ foldl1' _ []             =  errorEmptyList "foldl1'"
 -- -----------------------------------------------------------------------------
 -- List sum and product
 
-{-# SPECIALISE sum     :: [Int] -> Int #-}
-{-# SPECIALISE sum     :: [Integer] -> Integer #-}
-{-# SPECIALISE product :: [Int] -> Int #-}
-{-# SPECIALISE product :: [Integer] -> Integer #-}
 -- | The 'sum' function computes the sum of a finite list of numbers.
 sum                     :: (Num a) => [a] -> a
 -- | The 'product' function computes the product of a finite list of numbers.
@@ -1039,14 +1035,27 @@ product                 :: (Num a) => [a] -> a
 sum                     =  foldl (+) 0
 product                 =  foldl (*) 1
 #else
-sum     l       = sum' l 0
-  where
-    sum' []     a = a
-    sum' (x:xs) a = sum' xs (a+x)
-product l       = prod l 1
-  where
-    prod []     a = a
-    prod (x:xs) a = prod xs (a*x)
+{-# INLINE sum #-}
+sum l = sum' l 0
+
+sum' :: (Num a) => [a] -> a -> a
+-- We want to make specialised copies of sum in calling modules
+{-# INLINABLE sum' #-}
+{-# SPECIALISE sum' :: [Int] -> Int -> Int #-}
+{-# SPECIALISE sum' :: [Integer] -> Integer -> Integer #-}
+sum' []     a = a
+sum' (x:xs) a = sum' xs (a+x)
+
+-- product is just like sum
+{-# INLINE product #-}
+product l = product' l 1
+
+product' :: (Num a) => [a] -> a -> a
+{-# INLINABLE product' #-}
+{-# SPECIALISE product' :: [Int] -> Int -> Int #-}
+{-# SPECIALISE product' :: [Integer] -> Integer -> Integer #-}
+product' []     a = a
+product' (x:xs) a = product' xs (a*x)
 #endif

comment:19 Changed 20 months ago by igloo

  • Milestone changed from 7.6.1 to 7.6.2

comment:20 Changed 17 months ago by igloo

  • Owner set to simonpj

comment:21 Changed 16 months ago by simonpj

  • Resolution set to fixed
  • Status changed from new to closed

In the end, the patch to #7507 fixed this too.

Simon

Note: See TracTickets for help on using tickets.