Opened 10 years ago

Last modified 6 weeks ago

#2731 new bug

Avoid unnecessary evaluation when unpacking constructors

Reported by: simonpj Owned by:
Priority: lowest Milestone:
Component: Compiler Version: 8.5
Keywords: CodeGen Cc:
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

Consider

data T a = MkT !a

foo :: T (a,b) -> a
foo (MkT (x,y)) = x

GHC will extract the first component of the MkT, evaluate it, and then extract the first component of the pair. The evaluation step isn't needed, since the component is known to be already-evaluated. UNPACK directives won't work here, because the component is polymorphic.

In the email thread, Tyson posted an example where this extra eval made a significant difference to his inner loop: http://www.haskell.org/pipermail/glasgow-haskell-users/2008-October/015796.html

Simon

Change History (18)

comment:1 Changed 9 years ago by simonmar

Type of failure: Runtime performance bug

comment:2 Changed 8 years ago by igloo

Milestone: 6.12 branch6.12.3

comment:3 Changed 8 years ago by igloo

Milestone: 6.12.36.14.1
Priority: normallow

comment:4 Changed 8 years ago by igloo

Milestone: 7.0.17.0.2

comment:5 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:6 Changed 7 years ago by igloo

Milestone: 7.2.17.4.1

comment:7 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: lowlowest

comment:8 Changed 6 years ago by igloo

Milestone: 7.6.17.6.2

comment:9 Changed 5 years ago by jstolarek

Cc: jan.stolarek@… added

comment:10 Changed 4 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:11 Changed 4 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:12 Changed 4 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:13 Changed 3 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:14 Changed 3 years ago by jstolarek

Cc: jan.stolarek@… removed

comment:15 Changed 2 years ago by thomie

Milestone: 8.0.1

comment:16 Changed 16 months ago by simonpj

Keywords: CodeGen added

comment:17 Changed 6 weeks ago by AndreasK

Version: 6.8.38.5

If anyone wonders this is still the case in GHC-8.4 / HEAD.

Changing the type of T to data T = MkT !(Bool,Bool) also doesn't change anything.

Cmm Code.

     {offset
       c1pY:
           if ((Sp + -8) < SpLim) (likely: False) goto c1q2; else goto c1q3;
       c1q2:
           R2 = R2;
           R1 = foo_closure;
           call (stg_gc_fun)(R2, R1) args: 8, res: 0, upd: 8;
       c1q3:
           I64[Sp - 8] = c1pV;
           R1 = R2;
           Sp = Sp - 8;
           if (R1 & 7 != 0) goto c1pV; else goto c1pW;
       c1pW:
           call (I64[R1])(R1) returns to c1pV, args: 8, res: 8, upd: 8;
       c1pV:
           I64[Sp] = c1q1;
           R1 = P64[R1 + 7];
           if (R1 & 7 != 0) goto c1q1; else goto c1q5;
       c1q5:
           call (I64[R1])(R1) returns to c1q1, args: 8, res: 8, upd: 8;
       c1q1:
           R1 = P64[R1 + 7] & (-8);
           Sp = Sp + 8;
           call (I64[R1])(R1) args: 8, res: 0, upd: 8;
     }

To solve this we would need to track the evaluation requirements of binders in STG. Something it seems we currently don't do.

comment:18 Changed 6 weeks ago by simonpj

To solve this we would need to track the evaluation requirements of binders in STG.

Correct -- and it really would not be hard to do. A relatively straightforward task for someone interested in GHC's back end. I'd be happy to advise.

Note: See TracTickets for help on using tickets.