Opened 18 months ago

Closed 17 months ago

Last modified 17 months ago

#11710 closed bug (fixed)

Fusion of a simple listArray call is very fragile

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

Description

Consider the following (taken from ticket:11707#comment:2),

module Test where                  
import Data.Array

arr, arr2 :: Array Int Int
arr = listArray (0,10) [ 1,1,1,1,1,1,1,1,1,1 ]
arr2 = listArray (0,10) [ 1,1,1,1,1,1,1,1,1,-1 ]

Given that these are a small array, one might suspect it would be worthwhile for GHC to fuse the lists with listArray, giving rise to two nicely unrolled construction procedures.

However, if you look at the Core produced by -O1 this you'll find that this only happens in the case of arr2. arr on the other handle, is mysteriously not fused. The fact that these expressions are so similar and yet produce entirely different code is quite worrying.

Change History (9)

comment:1 Changed 18 months ago by bgamari

And here's a quick quiz for those playing along at home:

How much unrolling would you expect to happen in this case?

arr :: Array Int Int
arr = listArray (0,10) [ 1,1,1,-1,1,1,1,1,1,1 ]

Answer: The first four elements will be unrolled; the remaining will be constructed by recursive pattern matching against a CAF [Int]

comment:2 Changed 18 months ago by bgamari

For the record, the case in comment:1 results in this Core,

Test2.arr10 = GHC.Types.I# 1
Test2.arr11 = GHC.Types.I# (-1)

Test2.arr1 =
  \ (@ s) (s1# :: GHC.Prim.State# s) ->
    case GHC.Prim.newArray# @Int @s 11 (GHC.Arr.arrEleBottom @Int) s1#
    of _ { (# ipv, ipv1 #) ->
    case GHC.Prim.writeArray# @s @Int ipv1 0 Test2.arr10 ipv
    of s4# { __DEFAULT ->
    case GHC.Prim.writeArray# @s @Int ipv1 1 Test2.arr10 s4#
    of s4#1 { __DEFAULT ->
    case GHC.Prim.writeArray# @s @Int ipv1 2 Test2.arr10 s4#1
    of s4#2 { __DEFAULT ->
    case GHC.Prim.writeArray# @s @Int ipv1 3 Test2.arr11 s4#2
    of s4#3 { __DEFAULT ->
    letrec {
      go :: [Int] -> GHC.Prim.Int# -> GHC.Prim.State# s -> GHC.Prim.State# s
      go =
        \ (ds :: [Int]) (eta :: GHC.Prim.Int#) (eta1 :: GHC.Prim.State# s) ->
          case ds of _ {
            [] -> eta1;
            : y ys ->
              case GHC.Prim.writeArray# @s @Int ipv1 eta y eta1
              of s4#4 { __DEFAULT ->
              case eta of wild1 {
                __DEFAULT -> go ys (GHC.Prim.+# wild1 1) s4#4;
                10 -> s4#4
              }
              }
          }; } in
    case go Test2.arr4 4 s4#3 of wild4 { __DEFAULT ->
    case GHC.Prim.unsafeFreezeArray# @s @Int ipv1 wild4
    of _ { (# ipv2, ipv3 #) ->
    (# ipv2, GHC.Arr.Array @Int @Int Test2.arr3 Test2.arr2 11 ipv3 #)

comment:3 Changed 18 months ago by bgamari

The reason for this inconsistency appears to be the dynamic prefix log in dsExplicitList. Let's look at the desugared output that gave rise to comment:2,

arr =
  listArray
    GHC.Arr.$fIxInt
    (I# 0, I# 10)
    (GHC.Base.build
       (\ (@ a) (c [OS=OneShot] :: Int -> a -> a) (n [OS=OneShot] :: a) ->
          c (I# 1)
            (c (I# 1)
               (c (I# 1)
                  (c (negate GHC.Num.$fNumInt (I# 1))
                     (foldr c n [I# 1, I# 1, I# 1, I# 1, I# 1, I#])
    )))))

We see that the desugarer took everything up to and including the -1 element as the dynamic prefix.

The dynamic prefix is defined in dsExplicitList as,

is_static :: CoreExpr -> Bool
is_static e = all is_static_var (varSetElems (exprFreeVars e))

is_static_var :: Var -> Bool
is_static_var v
  | isId v = isExternalName (idName v)  -- Top-level things are given external names
  | otherwise = False                   -- Type variables

(dynamic_prefix, static_suffix) = spanTail is_static xs'

That is, anything expression having a free variable with an external name (e.g. negate in the current example) is considered to be non-static, even if it will eventually be resolved to something static during simplification.

If we consider that foldr/build is an optimization, the above behavior seems reasonable, preserving potential optimization opportunities by liberally applying build desugaring. This does, however, lead to slightly longer compilation times even in the case where fusion didn't fire as we need to rewrite build to a plain list during simplification.

Last edited 18 months ago by bgamari (previous) (diff)

comment:4 Changed 18 months ago by simonpj

Yes, see Note [Desugaring explicit lists] in DsExpr, about the "static tail" of a list.

For listArray (1,100) [1,2 we get

  let {
    $dIx_aHr :: Ix Integer
    [LclId, Str=DmdType]
    $dIx_aHr = GHC.Arr.$fIxInteger } in
  let {
    $dNum_aSd :: Num Integer
    [LclId, Str=DmdType]
    $dNum_aSd = GHC.Num.$fNumInteger } in
  let {
    $dNum_aSh :: Num Integer
    [LclId, Str=DmdType]
    $dNum_aSh = $dNum_aSd } in
  let {
    $dNum_aSj :: Num Integer
    [LclId, Str=DmdType]
    $dNum_aSj = $dNum_aSh } in
  let {
    $dNum_aSf :: Num Integer
    [LclId, Str=DmdType]
    $dNum_aSf = $dNum_aSd } in
  letrec {
    alex_table_aSk :: Array Integer Integer
    [LclId, Str=DmdType]
    alex_table_aSk =
      listArray
        @ Integer
        @ Integer
        $dIx_aHr
        (0, 100)
        (GHC.Types.:
           @ Integer
           1
           (GHC.Types.: @ Integer 2 (GHC.Types.[] @ Integer))); }

(The dead Num dictionaries happen because the desugarer short-circuits the calls to fromInteger @ Integer.)

Notice that the list has no free vars, so via the "static tail" trick in DsExpr we generate an explicit list. But for listArray (0,100) [-1,2] we get

  let {
    $dIx_aHs :: Ix Integer
    [LclId, Str=DmdType]
    $dIx_aHs = GHC.Arr.$fIxInteger } in
  let {
    $dNum_aSe :: Num Integer
    [LclId, Str=DmdType]
    $dNum_aSe = GHC.Num.$fNumInteger } in
  let {
    $dNum_aSi :: Num Integer
    [LclId, Str=DmdType]
    $dNum_aSi = $dNum_aSe } in
  let {
    $dNum_aSm :: Num Integer
    [LclId, Str=DmdType]
    $dNum_aSm = $dNum_aSi } in
  let {
    $dNum_aSk :: Num Integer
    [LclId, Str=DmdType]
    $dNum_aSk = $dNum_aSi } in
  let {
    $dNum_aSg :: Num Integer
    [LclId, Str=DmdType]
    $dNum_aSg = $dNum_aSe } in
  letrec {
    alex_table_aSn :: Array Integer Integer
    [LclId, Str=DmdType]
    alex_table_aSn =
      listArray
        @ Integer
        @ Integer
        $dIx_aHs
        (0, 100)
        (GHC.Base.build
           @ Integer
           (\ (@ a_d22o)
              (c_d22p :: Integer -> a_d22o -> a_d22o)
              (n_d22q :: a_d22o) ->
              c_d22p
                (negate @ Integer $dNum_aSi 1)
                (GHC.Base.foldr
                   @ Integer
                   @ a_d22o
                   c_d22p
                   n_d22q
                   (GHC.Types.: @ Integer 2 (GHC.Types.[] @ Integer))))); } in

Now the calls to negate have a dictionary $dNum_asi which isn't top-level, so the "static tail" stuff fails and we generate a build.

This is obviously far too fragile. I think we should just drop the "static tail" idea entirely.

It's never bad to generate the build form, except for generating bloated code; see #11707.

comment:5 Changed 18 months ago by simonpj

Then we can also get rid of -fsimple-list-literals.

comment:6 Changed 17 months ago by bgamari

Differential Rev(s): Phab:D2023
Milestone: 8.0.1
Status: newpatch

The fix from #11707, Phab:D2007, has been merged.

Phab:D2023 removes the static tail business, as suggested by Simon in comment:4.

comment:7 Changed 17 months ago by Ben Gamari <ben@…>

In 0db05941/ghc:

DsExpr: Rip out static/dynamic check in list desugaring

Previously we would try to break explicit lists into a dynamic prefix
and static tail and desugar the former into a `build` expression.
Unfortunately, this heuristic resulted in surprising behavior
(see #11710) and wasn't pulling its weight. Here we drop it (along with
the `-fsimple-list-literals` flag), leaving only the list length
heuristic to determine whether `build` or cons list desugaring should be
used.

Test Plan: Validate

Reviewers: simonpj, austin

Reviewed By: simonpj

Subscribers: thomie

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

GHC Trac Issues: #11710

comment:8 Changed 17 months ago by bgamari

Status: patchmerge

comment:9 Changed 17 months ago by bgamari

Resolution: fixed
Status: mergeclosed
Last edited 17 months ago by bgamari (previous) (diff)
Note: See TracTickets for help on using tickets.