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://github.com/clash-lang/clash-compiler/issues/1691). 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
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
On Thu, 11 Mar 2021, Simon Peyton Jones wrote:
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]
Maybe this is fixed? If you think not, maybe open a ticket?
OK, so initially I tried it on GHC 8.10.3, which is where `elem @[]` is not optimized. I have now tried on GHC 9.0.1, where, just like you see on HEAD, indeed it gets it right. I wonder why that is? What changed between GHC 8.10.3 and 9.0.1? Was the definition of `elem` changed in `base`? Thanks, Gergo
On Fri, 12 Mar 2021, ÉRDI Gergő wrote:
I wonder why that is? What changed between GHC 8.10.3 and 9.0.1? Was the definition of `elem` changed in `base`?
Oh, I've found this commit:
```
commit f10d11fa49fa9a7a506c4fdbdf86521c2a8d3495
Author: Andreas Klebinger
| I wonder why that is? What changed between GHC 8.10.3 and 9.0.1? Was
| the definition of `elem` changed in `base`?
I'm not sure... you could investigate, but I'm inclined just to declare victory!
S
| -----Original Message-----
| From: ÉRDI Gergő
On Fri, 12 Mar 2021, Simon Peyton Jones wrote:
I'm not sure... you could investigate, but I'm inclined just to declare victory!
That's easy for you to say, but here I am stuck with Stack not supporting GHC 9.0... https://github.com/commercialhaskell/stack/issues/5486
Ah, sorry, I thought it was just curiosity about what has changed.
I am not sure whether there will be future 8.10 releases; but you can open a ticket asking Ben to backport the fix (which you have found) to 8.10, if there is to be such a release.
Simon
| -----Original Message-----
| From: ÉRDI Gergő
participants (2)
-
Simon Peyton Jones -
ÉRDI Gergő