Opened 8 years ago

Closed 3 years ago

#5835 closed feature request (fixed)

Make better use of known dictionaries

Reported by: rl Owned by: danharaj
Priority: normal Milestone:
Component: Compiler Version: 7.5
Keywords: Cc: nfrisby
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D2714
Wiki Page:

Description (last modified by bgamari)

Example:

{-# LANGUAGE GADTs #-}
module T5835 where

data T a where
  T :: Eq a => a -> T a

foo :: a -> T a -> Bool
{-# INLINE foo #-}
foo x = \(T y) -> x == y

appl :: (a -> b) -> a -> b
{-# NOINLINE appl #-}
appl f x = f x

bar :: T Int -> Bool
bar t = appl (foo 42) t

GHC generates this for bar:

bar2 :: Int
bar2 = I# 42

bar1 :: T Int -> Bool
bar1 =
  \ (ds_dhk :: T Int) ->
    case ds_dhk of _ { T $dEq_agz y_aa4 ->
    == @ Int $dEq_agz bar2 y_aa4
    }

bar :: T Int -> Bool
bar = \ (t_aga :: T Int) -> appl @ (T Int) @ Bool bar1 t_aga

Note how it want to get the Eq dictionary for Int from T. But we know the Eq Int instance without inspecting T and bar could be significantly simplified if we used that.

Change History (13)

comment:1 Changed 8 years ago by igloo

difficulty: Unknown
Milestone: 7.6.1

comment:2 Changed 7 years ago by igloo

Milestone: 7.6.17.6.2

comment:3 Changed 5 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:4 Changed 5 years ago by thomie

Description: modified (diff)
Type of failure: None/UnknownRuntime performance bug

Core unchanged in HEAD vs 7.5. To reproduce, use this command:

ghc -O2 -ddump-simpl -dsuppress-module-prefixes -dsuppress-idinfo T5835.hs

comment:5 Changed 5 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:6 Changed 4 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:7 Changed 4 years ago by bgamari

Description: modified (diff)
Milestone: 8.0.18.2.1

Looks like this won't make it for 8.0.

comment:8 Changed 3 years ago by bgamari

Milestone: 8.2.1

De-milestoning due to lack of progress. If you, the motivated reader, would like to see this happen please do pick it up!

comment:9 Changed 3 years ago by nfrisby

Cc: nfrisby added

comment:10 Changed 3 years ago by danharaj

Owner: set to danharaj

comment:11 Changed 3 years ago by danharaj

Differential Rev(s): Phab:D2714

My patch for #12791 also resolves this issue.

comment:12 Changed 3 years ago by Matthew Pickering <matthewtpickering@…>

In 748b7974/ghc:

Use top-level instances to solve superclasses where possible

This patch introduces a new flag `-fsolve-constant-dicts` which makes the
constraint solver solve super class constraints with available dictionaries if
possible. The flag is enabled by `-O1`.

The motivation of this patch is that the compiler can produce more efficient
code if the constraint solver used top-level instance declarations to solve
constraints that are currently solved givens and their superclasses. In
particular, as it currently stands, the compiler imposes a performance penalty
on the common use-case where superclasses are bundled together for user
convenience. The performance penalty applies to constraint synonyms as
well. This example illustrates the issue:

```
{-# LANGUAGE ConstraintKinds, MultiParamTypeClasses, FlexibleContexts #-}
module B where

class M a b where m :: a -> b

type C a b = (Num a, M a b)

f :: C Int b => b -> Int -> Int
f _ x = x + 1
```

Output without the patch, notice that we get the instance for `Num Int` by
using the class selector `p1`.

```
f :: forall b_arz. C Int b_arz => b_arz -> Int -> Int
f =
  \ (@ b_a1EB) ($d(%,%)_a1EC :: C Int b_a1EB) _ (eta1_B1 :: Int) ->
    + @ Int
      (GHC.Classes.$p1(%,%) @ (Num Int) @ (M Int b_a1EB) $d(%,%)_a1EC)
      eta1_B1
      B.f1
```

Output with the patch, nicely optimised code!

```
f :: forall b. C Int b => b -> Int -> Int
f =
  \ (@ b) _ _ (x_azg :: Int) ->
    case x_azg of { GHC.Types.I# x1_a1DP ->
    GHC.Types.I# (GHC.Prim.+# x1_a1DP 1#)
    }
```

Reviewers: simonpj, bgamari, austin

Reviewed By: simonpj

Subscribers: mpickering, rwbarton, thomie

Differential Revision: https://phabricator.haskell.org/D2714

GHC Trac Issues: #12791, #5835

comment:13 Changed 3 years ago by mpickering

Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.