Inlining of `any @[]` vs `elem @[]`
Simon Peyton Jones
simonpj at microsoft.com
Thu Mar 11 17:54:44 UTC 2021
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: ghcdevs <ghcdevsbounces at haskell.org> On Behalf Of ÉRDI Gergo
 Sent: 07 March 2021 02:59
 To: GHC Devs <ghcdevs 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%2Fclashlang%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 noninlineable 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
 _______________________________________________
 ghcdevs mailing list
 ghcdevs at haskell.org
 https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.
 haskell.org%2Fcgibin%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
More information about the ghcdevs
mailing list