Re: Unexpected list non-fusion
On 1/15/12 10:02 AM, Jan-Willem Maessen wrote: On Sat, Jan 14, 2012 at 10:48 PM, wren ng thornton wrote: On 12/12/11 3:37 PM, wren ng thornton wrote: I've noticed that take and filter are good producers (and consumers) for list fusion, but takeWhile, drop, and dropWhile are not. Is there any reason for this discrepancy? If not, would I need to go through the libraries@ process for fixing it, or should I just submit a patch? In working on a patch to fix this I've come upon a question. The fusion rules for take seem a bit odd in that they translate the take into a foldr which produces (Int# -> b), instead of passing the Int# in directly and using foldr to produce the b. Does anyone know why? This is the "turn any list traversal into a foldr using a higher-order fold" trick. I know _what_ it's doing, I'm more curious about why. From looking through the code there didn't appear to be any reason to prefer this higher-order version instead of the straight-forward version. I'm curious if there's some performance quirk that I should beware of... Oh, right. The cons of the list algebra isn't fixed throughout the recursion. Duh. Should've tried to see if it was even possible the easy way. -- Live well, ~wren ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Unexpected list non-fusion
On 12/12/11 3:37 PM, wren ng thornton wrote: I've noticed that take and filter are good producers (and consumers) for list fusion, but takeWhile, drop, and dropWhile are not. Is there any reason for this discrepancy? If not, would I need to go through the libraries@ process for fixing it, or should I just submit a patch? In working on a patch to fix this I've come upon a question. The fusion rules for take seem a bit odd in that they translate the take into a foldr which produces (Int# -> b), instead of passing the Int# in directly and using foldr to produce the b. Does anyone know why? -- Live well, ~wren ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Unexpected list non-fusion
On 12/17/11 6:42 AM, Joachim Breitner wrote: Dear Wren, Am Donnerstag, den 15.12.2011, 17:38 + schrieb Simon Peyton-Jones: | Am Montag, den 12.12.2011, 15:37 -0500 schrieb wren ng thornton: |> I've noticed that take and filter are good producers (and consumers) |> for list fusion, but takeWhile, drop, and dropWhile are not. Is there |> any reason for this discrepancy? |> |> If not, would I need to go through the libraries@ process for fixing |> it, or should I just submit a patch? Please just submit a patch. are you going to tackle this? I was planning to do it over the next couple weeks. Though it you have the time or have other implementations already prepared, you're welcome to it. -- Live well, ~wren ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Unexpected list non-fusion
On 12/15/11 12:38 PM, Simon Peyton-Jones wrote: | Am Montag, den 12.12.2011, 15:37 -0500 schrieb wren ng thornton: |> I've noticed that take and filter are good producers (and consumers) |> for list fusion, but takeWhile, drop, and dropWhile are not. Is there |> any reason for this discrepancy? |> |> If not, would I need to go through the libraries@ process for fixing |> it, or should I just submit a patch? Please just submit a patch. Will do. The latter approach is probably safer. Follow the pattern for (++). That's what I was planning on. Replacing unfused calls by non-fusable implementations seems to be a performance win in the general case. -- Live well, ~wren ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Unexpected list non-fusion
Dear Wren, Am Donnerstag, den 15.12.2011, 17:38 + schrieb Simon Peyton-Jones: > | Am Montag, den 12.12.2011, 15:37 -0500 schrieb wren ng thornton: > | > I've noticed that take and filter are good producers (and consumers) > | > for list fusion, but takeWhile, drop, and dropWhile are not. Is there > | > any reason for this discrepancy? > | > > | > If not, would I need to go through the libraries@ process for fixing > | > it, or should I just submit a patch? > > Please just submit a patch. are you going to tackle this? Greeting, Joachim -- Joachim "nomeata" Breitner m...@joachim-breitner.de | nome...@debian.org | GPG: 0x4743206C xmpp: nome...@joachim-breitner.de | http://www.joachim-breitner.de/ signature.asc Description: This is a digitally signed message part ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Unexpected list non-fusion
| Am Montag, den 12.12.2011, 15:37 -0500 schrieb wren ng thornton:
| > I've noticed that take and filter are good producers (and consumers)
| > for list fusion, but takeWhile, drop, and dropWhile are not. Is there
| > any reason for this discrepancy?
| >
| > If not, would I need to go through the libraries@ process for fixing
| > it, or should I just submit a patch?
Please just submit a patch.
| while preparing my guest lecture¹ about Haskell Performance recently I also
| noticed that takeWhile (and concatMap!) are not setup for list fusion, here
| is what I showed the students; it improved performance considerably in the
| testcase.
|
| takeWhile' :: (a -> Bool) -> [a] -> [a]
| takeWhile' p xs = build $ \c n -> foldr (takeWhileF p c n) n xs {-# INLINE
| takeWhile' #-}
|
| takeWhileF p c n x xs = if p x then x `c` xs else n
|
| Of course, for a proper inclusion one first has to find out if takeWhile' is
| sufficiently fast even when not fused, or whether one has to do the „replace
| first, try to fuse, and then try to replace back by original function if not
| fused“ tick that is used for, e.g., (++).
The latter approach is probably safer. Follow the pattern for (++).
Thanks
Simon
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Unexpected list non-fusion
Hi,
Am Montag, den 12.12.2011, 15:37 -0500 schrieb wren ng thornton:
> I've noticed that take and filter are good producers (and consumers) for
> list fusion, but takeWhile, drop, and dropWhile are not. Is there any
> reason for this discrepancy?
>
> If not, would I need to go through the libraries@ process for fixing it,
> or should I just submit a patch?
while preparing my guest lecture¹ about Haskell Performance recently I
also noticed that takeWhile (and concatMap!) are not setup for list
fusion, here is what I showed the students; it improved performance
considerably in the testcase.
takeWhile' :: (a -> Bool) -> [a] -> [a]
takeWhile' p xs = build $ \c n -> foldr (takeWhileF p c n) n xs
{-# INLINE takeWhile' #-}
takeWhileF p c n x xs = if p x then x `c` xs else n
Of course, for a proper inclusion one first has to find out if
takeWhile' is sufficiently fast even when not fused, or whether one has
to do the „replace first, try to fuse, and then try to replace back by
original function if not fused“ tick that is used for, e.g., (++).
But yes, you are right that all these function ought to be fusable.
Greetings,
Joachim
¹
http://www.joachim-breitner.de/blog/archives/539-Guest-lecture-on-Haskell-performance.html
--
Joachim "nomeata" Breitner
m...@joachim-breitner.de | nome...@debian.org | GPG: 0x4743206C
xmpp: nome...@joachim-breitner.de | http://www.joachim-breitner.de/
signature.asc
Description: This is a digitally signed message part
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Unexpected list non-fusion
I've noticed that take and filter are good producers (and consumers) for list fusion, but takeWhile, drop, and dropWhile are not. Is there any reason for this discrepancy? If not, would I need to go through the libraries@ process for fixing it, or should I just submit a patch? -- Live well, ~wren ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
