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
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-pe... -- Joachim "nomeata" Breitner mail@joachim-breitner.de | nomeata@debian.org | GPG: 0x4743206C xmpp: nomeata@joachim-breitner.de | http://www.joachim-breitner.de/
| 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
Dear Wren, Am Donnerstag, den 15.12.2011, 17:38 +0000 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 mail@joachim-breitner.de | nomeata@debian.org | GPG: 0x4743206C xmpp: nomeata@joachim-breitner.de | http://www.joachim-breitner.de/
On 12/17/11 6:42 AM, Joachim Breitner wrote:
Dear Wren,
Am Donnerstag, den 15.12.2011, 17:38 +0000 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
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
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
participants (3)
-
Joachim Breitner -
Simon Peyton-Jones -
wren ng thornton