Seeking comments on proposed fusion rules

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Seeking comments on proposed fusion rules

David Feuer
The rules:

lpaste.net/108508

The boring explanation:

As I mentioned earlier, we currently can't fuse things like

foldr (x : build g)

The foldr can't see the build. Earlier, I considered a simple
cons/build rule that would rewrite

x : build g

to

build (\c n -> x `c` g c n)

I wasn't quite satisfied with this approach, largely because it treats

foldr c n (x1 : x2 : ... : xn : build g)

one way, and

foldr c n ([x1, x2, ..., xn) : build g)

another way. The former expands out the foldr, while the latter (via
various rules involving augment) translates into a foldr over [x1, x2,
..., xn].

I therefore came up with the idea of translating x1:x2:...:xn:build g
into [x1:x2:..:xn]++build g, and then letting the current rules do
their thing. dolio and carter (in #ghc) were concerned about what
would happen if fusion *didn't* occur, in which case the resulting
code appears to be *worse*. So then I wrote some rules to fix that up,
which actually look likely to be good rules in general. They turn

[x1:x2:...:xn] ++ ys

into

x1:x2:...:xn:ys

I ended up having to do more that I had originally expected in my
rules, because they miss a phase they need (it may be possible to fix
that; I'm not sure, because I'm very new to this business); I left
comments showing each step of the translation. One thing of note is
that I ended up using (by hand) the augment/augment rule that is
commented out as probably not being useful.

In my limited testing, the rules seem to do what they're supposed to
(when I can understand the Core), and the profiler is very pleased.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

RE: Seeking comments on proposed fusion rules

Simon Peyton Jones
Turning (:) into (++) feels like the wrong way round to me.

What's wrong with rewriting
        x : build g
into
        build (\cn. x `c` g c n)
as you suggest?

Now, [x1,x2,x3] ++ ys
is just syntactic sugar for
     (x1 : x2 : x2 : []) ++ ys
and I suppose that optimising that into
        x1 : x2 : x3 : ys
is a good thing quite independent of the (x : build g) stuff isn't it?

Simon

| -----Original Message-----
| From: Libraries [mailto:[hidden email]] On Behalf Of David
| Feuer
| Sent: 31 July 2014 19:38
| To: Haskell Libraries
| Subject: Seeking comments on proposed fusion rules
|
| The rules:
|
| lpaste.net/108508
|
| The boring explanation:
|
| As I mentioned earlier, we currently can't fuse things like
|
| foldr (x : build g)
|
| The foldr can't see the build. Earlier, I considered a simple
| cons/build rule that would rewrite
|
| x : build g
|
| to
|
| build (\c n -> x `c` g c n)
|
| I wasn't quite satisfied with this approach, largely because it treats
|
| foldr c n (x1 : x2 : ... : xn : build g)
|
| one way, and
|
| foldr c n ([x1, x2, ..., xn) : build g)
|
| another way. The former expands out the foldr, while the latter (via
| various rules involving augment) translates into a foldr over [x1, x2,
| ..., xn].
|
| I therefore came up with the idea of translating x1:x2:...:xn:build g
| into [x1:x2:..:xn]++build g, and then letting the current rules do
| their thing. dolio and carter (in #ghc) were concerned about what
| would happen if fusion *didn't* occur, in which case the resulting
| code appears to be *worse*. So then I wrote some rules to fix that up,
| which actually look likely to be good rules in general. They turn
|
| [x1:x2:...:xn] ++ ys
|
| into
|
| x1:x2:...:xn:ys
|
| I ended up having to do more that I had originally expected in my
| rules, because they miss a phase they need (it may be possible to fix
| that; I'm not sure, because I'm very new to this business); I left
| comments showing each step of the translation. One thing of note is
| that I ended up using (by hand) the augment/augment rule that is
| commented out as probably not being useful.
|
| In my limited testing, the rules seem to do what they're supposed to
| (when I can understand the Core), and the profiler is very pleased.
| _______________________________________________
| Libraries mailing list
| [hidden email]
| http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Seeking comments on proposed fusion rules

David Feuer
On Thu, Jul 31, 2014 at 3:12 PM, Simon Peyton Jones
<[hidden email]> wrote:
> Turning (:) into (++) feels like the wrong way round to me.
>
> What's wrong with rewriting
>         x : build g
> into
>         build (\cn. x `c` g c n)
> as you suggest?

Turning (:) into (++) *is* the wrong way around, but there is some
method to my madness. If you look in GHC.Base, you'll see the
following comments:

-- The foldr/cons rule looks nice, but it can give disastrously
-- bloated code when commpiling
--      array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
-- i.e. when there are very very long literal lists
-- So I've disabled it for now. We could have special cases
-- for short lists, I suppose.
-- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)

Something similar would happen with the above rule if someone wrote

foldr c n $ this : is : a : very : long : prefix : of : precomputed :
values : the : rest : of : which : are : computed : live : build g

With the current rules, folding over that would actually fold over
that whole thing, with no fusion. With the simple rule above, you
presumably get the "disastrously bloated code" above. If you, today,
rewrote it as

foldr c n $ [this, is, ..., live] ++ build g

then a different set of rules comes into play, producing a fold over
[this, is, ..., live] and fusion on the end.

Although I suppose having two different translations for these two
equivalent things allows the programmer more power, I don't think it's
terribly intuitive. More importantly, anyone who currently does
something like that will end up with the potential bloated code
problem. I think there may even be some such code in arithmoi, but I
could be misremembering. What the more complicated set of rules does
(essentially) is make  foldr c n (this:is:...:live:build g)  act
pretty much the way that foldr c n ([this, is, ..., live] ++ build g)
 does today. As a special sort of case, the foldr/single rule will end
up turning

foldr c n (x : build g)

into

x `c` g c n

which is what currently happens with

foldr c n ([x] : build g)

> Now, [x1,x2,x3] ++ ys
> is just syntactic sugar for
>      (x1 : x2 : x2 : []) ++ ys
> and I suppose that optimising that into
>         x1 : x2 : x3 : ys
> is a good thing quite independent of the (x : build g) stuff isn't it?
>
> Simon

Yes, I think it is.

David
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Seeking comments on proposed fusion rules

David Feuer
> which is what currently happens with
>
> foldr c n ([x] : build g)

Argh. Yes, I meant

foldr c n ([x] ++ build g)

at the end there. And no, I don't actually *know* if the comment about
disastrous code bloat is correct, but I imagine it will be if the
folded function is inlined.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Seeking comments on proposed fusion rules

wren romano
In reply to this post by David Feuer
On Thu, Jul 31, 2014 at 3:33 PM, David Feuer <[hidden email]> wrote:
> -- The foldr/cons rule looks nice, but it can give disastrously
> -- bloated code when commpiling
> --      array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
> -- i.e. when there are very very long literal lists
> -- So I've disabled it for now. We could have special cases
> -- for short lists, I suppose.
> -- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)

Yes, the foldr/cons rule is a bad idea. However, the cons/build rule
should be fine.

Both rules have the goal of reducing foldr/cons/build. The problem
shows up when we don't have that full pattern. The failure mode of
foldr/cons is ridiculously bloated code when the list doesn't end in a
build. I can't really think of a failure mode for cons/build.

When there's no foldr to cancel with, the build will be inlined; thus,
the original (x : build g) which became build(\c n -> c x (g c n))
will then become (x : g (:) []) in the end. If we did not have the
cons/build rule, then inlining of build would transform the original
(x : build g) into (x : g (:) []) directly. So having the rule, or
not, doesn't change the end result. In both cases we might complain
that g(:)[] is too slow, but then in both cases we'd expect there to
be a g-specific rule for rewriting g(:)[] into some g'.

The other possibility for a failure mode would be when there *is* a
foldr to cancel with but the cons function is really large— since the
cons/build rule duplicates the use of the cons function. That is, we
may worry about code like (foldr c0 n0 (x1:x2....:xN : build g)) where
N is large. However, note that after applying cons/build repeatedly
and then applying foldr/build, we end up with the code ((\c n -> c x1
(c x2 (... (c xN (g c n))...))) c0 n0) —that is, the rules produce a
beta-redex, they do not perform the substitution themselves. Since
beta-reduction is not performed by rewrite rules, the beta-reducer
already has to handle the issue of duplication.

--
Live well,
~wren
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Seeking comments on proposed fusion rules

David Feuer

So you're saying you don't think the apparent cons-duplication resulting from cons/build is really a problem? If so, that's a relief, because I didn't have much luck getting my more complex scheme to work properly.

On Aug 14, 2014 11:28 PM, "wren romano" <[hidden email]> wrote:
On Thu, Jul 31, 2014 at 3:33 PM, David Feuer <[hidden email]> wrote:
> -- The foldr/cons rule looks nice, but it can give disastrously
> -- bloated code when commpiling
> --      array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
> -- i.e. when there are very very long literal lists
> -- So I've disabled it for now. We could have special cases
> -- for short lists, I suppose.
> -- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)

Yes, the foldr/cons rule is a bad idea. However, the cons/build rule
should be fine.

Both rules have the goal of reducing foldr/cons/build. The problem
shows up when we don't have that full pattern. The failure mode of
foldr/cons is ridiculously bloated code when the list doesn't end in a
build. I can't really think of a failure mode for cons/build.

When there's no foldr to cancel with, the build will be inlined; thus,
the original (x : build g) which became build(\c n -> c x (g c n))
will then become (x : g (:) []) in the end. If we did not have the
cons/build rule, then inlining of build would transform the original
(x : build g) into (x : g (:) []) directly. So having the rule, or
not, doesn't change the end result. In both cases we might complain
that g(:)[] is too slow, but then in both cases we'd expect there to
be a g-specific rule for rewriting g(:)[] into some g'.

The other possibility for a failure mode would be when there *is* a
foldr to cancel with but the cons function is really large— since the
cons/build rule duplicates the use of the cons function. That is, we
may worry about code like (foldr c0 n0 (x1:x2....:xN : build g)) where
N is large. However, note that after applying cons/build repeatedly
and then applying foldr/build, we end up with the code ((\c n -> c x1
(c x2 (... (c xN (g c n))...))) c0 n0) —that is, the rules produce a
beta-redex, they do not perform the substitution themselves. Since
beta-reduction is not performed by rewrite rules, the beta-reducer
already has to handle the issue of duplication.

--
Live well,
~wren

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries