Inlining of `any @[]` vs `elem @[]`

[Simon Peyton Jones]

Gergo

With HEAD, and -O, I get the exact same (good code) for these two functions:

	f x = any (x ==) [1, 5, 7::Int]

	g x = elem x [2, 6, 9 :: Int]

namely

f = \ (x_aga :: Int) ->
      case x_aga of { GHC.Types.I# x1_a13b ->
      case x1_a13b of {
        __DEFAULT -> GHC.Types.False;
        1# -> GHC.Types.True;
        5# -> GHC.Types.True;
        7# -> GHC.Types.True
      }
      }

g = \ (x_aQu :: Int) ->
      case x_aQu of { GHC.Types.I# x1_a13b ->
      case x1_a13b of {
        __DEFAULT -> GHC.Types.False;
        2# -> GHC.Types.True;
        6# -> GHC.Types.True;
        9# -> GHC.Types.True
      }
      }

Maybe this is fixed?  If you think not, maybe open a ticket?

Simon

|  -----Original Message-----
|  From: ghc-devs <ghc-devs-bounces at haskell.org> On Behalf Of ÉRDI Gergo
|  Sent: 07 March 2021 02:59
|  To: GHC Devs <ghc-devs at haskell.org>
|  Subject: Inlining of `any @[]` vs `elem @[]`
|  
|  Hi,
|  
|  The inlining behaviour of `any @[]` and `elem @[]` differs in a way
|  that I am not sure is intentional, and it is affecting Clash (see
|  https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgith
|  ub.com%2Fclash-lang%2Fclash-
|  compiler%2Fissues%2F1691&data=04%7C01%7Csimonpj%40microsoft.com%7C
|  e37a9761e8814eada5f208d8e115026d%7C72f988bf86f141af91ab2d7cd011db47%7C
|  1%7C0%7C637506827802688772%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDA
|  iLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=Kik8v
|  KuwNobr9kiQOcIHuKTn%2BbEmQ7oY8tqP9tFjs6M%3D&reserved=0). I would
|  think that if it is a good idea to inline `any` then inlining `elem`
|  would be just as good an idea, or vice versa.
|  
|  However, `any` is defined polymorphically over `Foldable`, via
|  `foldMap` using `foldr`, with all steps between (and `foldr @[]`!)
|  marked as `INLINE`. The result is that if you use `any (x ==) [1, 5,
|  7]` you get the following beautiful Core:
|  
|  ```
|  topEntity
|     = \ (x_agAF :: Int) ->
|         case x_agAF of { GHC.Types.I# y_ahao ->
|         case y_ahao of {
|           __DEFAULT -> GHC.Types.False;
|           1# -> GHC.Types.True;
|           5# -> GHC.Types.True;
|           7# -> GHC.Types.True
|         }
|         }
|  ```
|  
|  As the kids these days would say: *chef's kiss*.
|  
|  
|  `elem`, on the other hand, is a typeclass method of `Foldable`, with a
|  default implementation in terms of `any`, but overridden for lists
|  with the following implementation:
|  
|  ```
|  GHC.List.elem :: (Eq a) => a -> [a] -> Bool
|  GHC.List.elem _ []       = False
|  GHC.List.elem x (y:ys)   = x==y || GHC.List.elem x ys
|  {-# NOINLINE [1] elem #-}
|  {-# RULES
|  "elem/build"    forall x (g :: forall b . Eq a => (a -> b -> b) -> b -
|  > b)
|      . elem x (build g) = g (\ y r -> (x == y) || r) False
|    #-}
|  ```
|  
|  This is marked as non-inlineable until phase 1 (so that `elem/build`
|  has a chance of firing), but it seems that when build fusion doesn't
|  apply (since `[1, 5, 7]` is, of course, not built via `build`), no
|  inlining happens AT ALL, even in later phases, so we end up with this:
|  
|  ```
|  topEntity
|     = \ (x_agAF :: Int) ->
|         GHC.List.elem
|           @ Int
|           GHC.Classes.$fEqInt
|           x_agAF
|           (GHC.Types.:
|              @ Int
|              (GHC.Types.I# 1#)
|              (GHC.Types.:
|                 @ Int
|                 (GHC.Types.I# 5#)
|                 (GHC.Types.: @ Int (GHC.Types.I# 7#) (GHC.Types.[] @
|  Int)))) ```
|  
|  So not only does it trip up Clash, it would also result in less
|  efficient code in software when using "normal" GHC.
|  
|  Is this all intentional? Wouldn't it make more sense to mark
|  `GHC.List.elem` as `INLINE [1]` instead of `NOINLINE [1]`, so that any
|  calls remaining after build fusion would be inlined?
|  
|  Thanks,
|   	Gergo
|  _______________________________________________
|  ghc-devs mailing list
|  ghc-devs at haskell.org
|  https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.
|  haskell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fghc-
|  devs&data=04%7C01%7Csimonpj%40microsoft.com%7Ce37a9761e8814eada5f2
|  08d8e115026d%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637506827802
|  688772%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJ
|  BTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=yMXu0XJQU2GmlDTH9ZaHXhl33
|  ZRBjHMe41rr8lKVxkk%3D&reserved=0