Casting + eta reduction
Consider newtype Foo = Foo Int lift :: (Int -> a) -> Foo -> a lift f (Foo x) = f x Now, I'd expect this to compile with -O2 down to something like lift f = f `cast` (Foo -> a) but it doesn't. It seems that GeneralizedNewtypeDeriving assumes that these two things *are* equivalent, and it just directly casts the class dictionary. The implication would be that that GeneralizedNewtypeDeriving gives more efficient instances than you could *possibly* get if you wrote them by hand, which is very sad. Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
On Thu, Jul 08, 2010 at 09:30:23PM -0500, Louis Wasserman wrote:
Consider
newtype Foo = Foo Int
lift :: (Int -> a) -> Foo -> a lift f (Foo x) = f x
Now, I'd expect this to compile with -O2 down to something like
lift f = f `cast` (Foo -> a)
but it doesn't.
It seems that GeneralizedNewtypeDeriving assumes that these two things *are* equivalent, and it just directly casts the class dictionary. The implication would be that that GeneralizedNewtypeDeriving gives more efficient instances than you could *possibly* get if you wrote them by hand, which is very sad.
It's true. For more, see this thread: http://www.mail-archive.com/haskell-cafe@haskell.org/msg72300.html Of course that thread is more about how sometimes GND gives you *wrong* code. That's currently being worked on and will hopefully be fixed at some point. But as you point out, it's also worth thinking about the flip side: how to optimize away non-type-class-related functions like your example. -Brent
It compiles to lift f d = f (d `cast` blah) which seems fine to me. Are you unhappy with that? Simon From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users-bounces@haskell.org] On Behalf Of Louis Wasserman Sent: 09 July 2010 03:30 To: glasgow-haskell-users@haskell.org Subject: Casting + eta reduction Consider newtype Foo = Foo Int lift :: (Int -> a) -> Foo -> a lift f (Foo x) = f x Now, I'd expect this to compile with -O2 down to something like lift f = f `cast` (Foo -> a) but it doesn't. It seems that GeneralizedNewtypeDeriving assumes that these two things *are* equivalent, and it just directly casts the class dictionary. The implication would be that that GeneralizedNewtypeDeriving gives more efficient instances than you could *possibly* get if you wrote them by hand, which is very sad. Louis Wasserman wasserman.louis@gmail.com<mailto:wasserman.louis@gmail.com> http://profiles.google.com/wasserman.louis
Mmmm, let's give a slightly different example: foo :: Foo -> Int foo (Foo a) = a + 1 bar :: Int -> Int bar = foo . Foo and I'd expect bar to be replaced with (foo `cast` (Int -> Int)) and inlined, eliminating an allocation. In general, we'd get the equivalent of the no-allocation versions of GeneralizedNewtypeDeriving instances, so long as we could write them out for ourselves. Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis On Tue, Jul 13, 2010 at 9:09 AM, Simon Peyton-Jones <simonpj@microsoft.com>wrote:
It compiles to
lift f d = f (d `cast` blah)
which seems fine to me. Are you unhappy with that?
Simon
*From:* glasgow-haskell-users-bounces@haskell.org [mailto: glasgow-haskell-users-bounces@haskell.org] *On Behalf Of *Louis Wasserman *Sent:* 09 July 2010 03:30 *To:* glasgow-haskell-users@haskell.org *Subject:* Casting + eta reduction
Consider
newtype Foo = Foo Int
lift :: (Int -> a) -> Foo -> a
lift f (Foo x) = f x
Now, I'd expect this to compile with -O2 down to something like
lift f = f `cast` (Foo -> a)
but it doesn't.
It seems that GeneralizedNewtypeDeriving assumes that these two things *are* equivalent, and it just directly casts the class dictionary. The implication would be that that GeneralizedNewtypeDeriving gives more efficient instances than you could *possibly* get if you wrote them by hand, which is very sad.
Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
Or a different way: I want -fdo-lambda-eta-expansion (which, if I understand correctly, actually triggers eta *reduction*) to eliminate argument casts, as well. My motivation: I'm working on a generalized trie library, and due to http://hackage.haskell.org/trac/ghc/ticket/4185, I can't use GeneralizedNewtypeDeriving to minimize the overhead of a stack of about 20 newtypes, each with their own class instance, even if I wasn't trying to use Template Haskell, which currently has no syntax for doing GeneralizedNewtypeDeriving on multi-parameter type classes (it only derives single-argument type classes.) As it stands, I have a lot of methods that compile to foo f = bar (\ x -> f (x `cast` a)) and they stack 20 deep, which means I have to do 20 allocations (\ x -> f (x `cast` a)) for even the most simple methods. What I'd like to see is this getting reduced to foo = bar `cast` (...) which would reduce my overhead significantly. Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis On Tue, Jul 13, 2010 at 10:06 AM, Louis Wasserman <wasserman.louis@gmail.com
wrote:
Mmmm, let's give a slightly different example:
foo :: Foo -> Int foo (Foo a) = a + 1
bar :: Int -> Int bar = foo . Foo
and I'd expect bar to be replaced with (foo `cast` (Int -> Int)) and inlined, eliminating an allocation. In general, we'd get the equivalent of the no-allocation versions of GeneralizedNewtypeDeriving instances, so long as we could write them out for ourselves.
Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
On Tue, Jul 13, 2010 at 9:09 AM, Simon Peyton-Jones <simonpj@microsoft.com
wrote:
It compiles to
lift f d = f (d `cast` blah)
which seems fine to me. Are you unhappy with that?
Simon
*From:* glasgow-haskell-users-bounces@haskell.org [mailto: glasgow-haskell-users-bounces@haskell.org] *On Behalf Of *Louis Wasserman *Sent:* 09 July 2010 03:30 *To:* glasgow-haskell-users@haskell.org *Subject:* Casting + eta reduction
Consider
newtype Foo = Foo Int
lift :: (Int -> a) -> Foo -> a
lift f (Foo x) = f x
Now, I'd expect this to compile with -O2 down to something like
lift f = f `cast` (Foo -> a)
but it doesn't.
It seems that GeneralizedNewtypeDeriving assumes that these two things *are* equivalent, and it just directly casts the class dictionary. The implication would be that that GeneralizedNewtypeDeriving gives more efficient instances than you could *possibly* get if you wrote them by hand, which is very sad.
Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
now I understand. I've created a Trac ticket. Shouldn't be hard. http://hackage.haskell.org/trac/ghc/ticket/4201 Thanks Simon From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users-bounces@haskell.org] On Behalf Of Louis Wasserman Sent: 13 July 2010 17:46 To: Simon Peyton-Jones Cc: glasgow-haskell-users@haskell.org Subject: Re: Casting + eta reduction Or a different way: I want -fdo-lambda-eta-expansion (which, if I understand correctly, actually triggers eta *reduction*) to eliminate argument casts, as well. My motivation: I'm working on a generalized trie library, and due to http://hackage.haskell.org/trac/ghc/ticket/4185, I can't use GeneralizedNewtypeDeriving to minimize the overhead of a stack of about 20 newtypes, each with their own class instance, even if I wasn't trying to use Template Haskell, which currently has no syntax for doing GeneralizedNewtypeDeriving on multi-parameter type classes (it only derives single-argument type classes.) As it stands, I have a lot of methods that compile to foo f = bar (\ x -> f (x `cast` a)) and they stack 20 deep, which means I have to do 20 allocations (\ x -> f (x `cast` a)) for even the most simple methods. What I'd like to see is this getting reduced to foo = bar `cast` (...) which would reduce my overhead significantly. Louis Wasserman wasserman.louis@gmail.com<mailto:wasserman.louis@gmail.com> http://profiles.google.com/wasserman.louis On Tue, Jul 13, 2010 at 10:06 AM, Louis Wasserman <wasserman.louis@gmail.com<mailto:wasserman.louis@gmail.com>> wrote: Mmmm, let's give a slightly different example: foo :: Foo -> Int foo (Foo a) = a + 1 bar :: Int -> Int bar = foo . Foo and I'd expect bar to be replaced with (foo `cast` (Int -> Int)) and inlined, eliminating an allocation. In general, we'd get the equivalent of the no-allocation versions of GeneralizedNewtypeDeriving instances, so long as we could write them out for ourselves. Louis Wasserman wasserman.louis@gmail.com<mailto:wasserman.louis@gmail.com> http://profiles.google.com/wasserman.louis On Tue, Jul 13, 2010 at 9:09 AM, Simon Peyton-Jones <simonpj@microsoft.com<mailto:simonpj@microsoft.com>> wrote: It compiles to lift f d = f (d `cast` blah) which seems fine to me. Are you unhappy with that? Simon From: glasgow-haskell-users-bounces@haskell.org<mailto:glasgow-haskell-users-bounces@haskell.org> [mailto:glasgow-haskell-users-bounces@haskell.org<mailto:glasgow-haskell-users-bounces@haskell.org>] On Behalf Of Louis Wasserman Sent: 09 July 2010 03:30 To: glasgow-haskell-users@haskell.org<mailto:glasgow-haskell-users@haskell.org> Subject: Casting + eta reduction Consider newtype Foo = Foo Int lift :: (Int -> a) -> Foo -> a lift f (Foo x) = f x Now, I'd expect this to compile with -O2 down to something like lift f = f `cast` (Foo -> a) but it doesn't. It seems that GeneralizedNewtypeDeriving assumes that these two things *are* equivalent, and it just directly casts the class dictionary. The implication would be that that GeneralizedNewtypeDeriving gives more efficient instances than you could *possibly* get if you wrote them by hand, which is very sad. Louis Wasserman wasserman.louis@gmail.com<mailto:wasserman.louis@gmail.com> http://profiles.google.com/wasserman.louis
participants (3)
-
Brent Yorgey -
Louis Wasserman -
Simon Peyton-Jones