foldr under the hood
neilmitchell.blogspot.com/2019/04/foldr-under...Posted May 1, 2019, 9:58 AM UTC
9816
neilmitchell.blogspot.com
Great post! Two clarifications/elaborations come to mind. If you're optimizing some hot loops, these points might be relevant. HTH.
The static argument transformation can be a huge win because it ultimately enables specialization (by first enabling inlining). But, SAT may also have a downside: the go function is heap allocated at each call site. Sometimes the inlining doesn't help, or specialization doesn't fire, or etc and the SAT incurs more allocation, which can be relatively expensive. More relevant info here: https://gitlab.haskell.org/ghc/ghc/wikis/late-lam-lift (Nice work, Sebastian! Excited for paper.)
Last I checked, ("big") list literals are not unfolded. foldr (+) 0 [1,2,3] is not deforested to 1+2+3+0.
2
What makes list literals big?
3
I haven't bothered to check. It might very well be that all list literals are "big".
1
Interesting about SAT. I believe the last benchmarks I saw had it at 20-30%, so very valuable there - but that was quite a while ago.
Yes, big literals are not deforested. When I talk about [1,2,3] I'm talking about what happens at runtime. Which bit made it sound otherwise?
2
Which bit made it sound otherwise?
Skimming your post again, I'm not seeing an indication one way or the other. I think it was the use of literals in your examples juxtaposed with the discussion of compiler transformations, inlining, and rewrite rules that initially caught my eye.
1
Good post. Is there a performance difference between
foldr :: forall f a b. Foldable f => (a -> b -> b) -> (b -> f a -> b)
foldr cons nil as = appEndo (foldMap (Endo #. cons) as) nil
foldr :: forall f a b. Foldable f => (a -> b -> b) -> (b -> f a -> b)
foldr cons nil as = coerce (foldMap @f @(Endo b) @a) cons as nil
1
Nope - at -O1 they both give identical code.
2
great news thanks for checking Neil, it could be written foldr = flip . foldMap @_ @(via Endo) then
1
Horrible on mobile...
-3
Looks pretty nice on my iPhone... but could definitely be better. When I last updated my blog style you couldn't yet visit websites from phones...
4
Strange, I can't zoom and I'd have to swipe constantly because the lines are long.
3
it's not too bad, could be better but not horrible
0
Yes. I can't zoom and it shows only one third of the text on the screen. Horrible.
3
Looks fine on my phone, can scroll around and zoom as I please. I suggest you browse websites with anything other than a blackberry
-1
I have a regular android phone.
1
Really great explanation.