Opened 9 years ago

Last modified 22 months ago

#3138 new bug

Returning a known constructor: GHC generates terrible code for cmonad

Reported by: simonpj Owned by:
Priority: lowest Milestone:
Component: Compiler Version: 6.10.1
Keywords: Cc: lennart@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Lennart reports that GHC generates very poor code for his cmonad package. If you want to look at a simple example, look at the Inf.hs example included in package cmonad-0.1.1. It's very simple, and ghc generates fantastically bad code for it.

It would be great if you could nail down why it's so amazingly unoptimal. Even with everything inlined and no overloading left, ghc seems to ignore the INLINE directives and use dictionaries left and right. When I looked at it a year ago or so, it was a return of one constructor in a sum. That is, a function always returns the same constructor, so the case analysis of the return value is not needed; it should be returned as an unboxed tuple instead

Another unrelated problem, I think, is that ghc needs to promote in-memory variables to registers when possible. Perhaps the new code generator has such a transformation?

Attachments (1)

Inf.ddump-simpl (33.8 KB) - added by simonpj 9 years ago.
ghc -O Inf.hs -package cmonad-0.1.1.1 -ddump-simpl

Download all attachments as: .zip

Change History (20)

comment:1 Changed 9 years ago by igloo

Milestone: 6.12 branch

comment:2 Changed 9 years ago by simonpj

Cc: lennart@… added

Lennart, I've taken a quick look. As you say, it generates quite a lot of code. I attach the result of -ddump-simpl for Inf.hs compiled with -O.

There is indeed one function that return a simple constructor from a sum type, namely +=_r1mk. Doing the CPR transform for this would indeed be a significant improvement.

But is that it? Can you point to other lost optimisations? For example, while is recursive so we can't inline that.

I'm sure you're right that we should get good code here, but because I don't know the code, it's harder to spot what should be done that isn't getting done. Can you help?

Simon

Changed 9 years ago by simonpj

Attachment: Inf.ddump-simpl added

ghc -O Inf.hs -package cmonad-0.1.1.1 -ddump-simpl

comment:3 Changed 8 years ago by augustss

I expect the code to be the same as the code for

main = do
    rs <- newIORef 0
    ri <- newIORef 0
    writeIORef ri 1

    let loop = do
            i <- readIORef ri
            if i < 1e3 then do
                s <- readIORef s
                writeIORef rs (s + 1/i)
                writeIORef ri (i+1)
                loop
             else
                return ()
    loop

    s <- readIORef rs
    putStrLn $ "Almost infinity is " ++ show s

Because that's what the code does. Getting that far would require specializing the recursive while function (why doesn't ghc specialize recursive functions?).

comment:4 Changed 8 years ago by augustss

A first thing to look at is the fact that there's still dictionaries in the code. There's no unresolved overloading in Inf.hs, so all dictionaries should be gone.

To avoid the disturbing recursive while function, try this code instead:

inf = runE $ do
    s <- auto 0
    i <- auto 0
    i =: 1
    if1 ((i :: E m Double) <= 1e3) $ do
        s += 1/i
        i += 1
    retrn s

comment:5 Changed 8 years ago by simonpj

Indeed GHC isn't a supercompiler and doesn't specialise recursive functions for their call sites. As it happens, Peter Jonsson started yesterday as an intern to try just that! But as of today, no. (Except that, perhaps inconsistently, within a single module, we specialise overloaded functions (including recursive ones) at the types where they are called locally. You can use a SPECIALISE pragma to make that happen for types where there is no local call.)

Even non-recursive functions are inlined only if they look small enough. That can indeed lead to dictionaries being passed instead of code being duplicated.

Meanwhile I'll look at the simpler example -- thanks.

Simon

comment:6 Changed 8 years ago by simonmar

Type of failure: Runtime performance bug

comment:7 Changed 8 years ago by igloo

Milestone: 6.12 branch6.12.3

comment:8 Changed 7 years ago by igloo

Milestone: 6.12.36.14.1
Priority: normallow

comment:9 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:10 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:11 Changed 7 years ago by batterseapower

See also #5075

comment:12 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:13 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: lowlowest

comment:14 Changed 5 years ago by igloo

Milestone: 7.6.17.6.2

comment:15 Changed 3 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:16 Changed 3 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:17 Changed 3 years ago by thoughtpolice

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:18 Changed 2 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:19 Changed 22 months ago by thomie

Milestone: 8.0.1
Note: See TracTickets for help on using tickets.