Prevent optimization from tempering with unsafePerformIO
Hello, I am writing a compiler from the functional logic language Curry to Haskell. As the result is a real extension of Haskell, there has to be SOME side effect involved. Unfortunately, this seems to prevent me from using any of ghc's optimizations on the resulting code. I have tried for some time to invoke the no-inline pragmata, but they seem to have no effect at all. Recently at ICFP, Neil Mitchell told me that there definitely is a way to avoid this problem. But does anybody know how? Thanks for your help! Bernd Brassel
bbr:
Hello,
I am writing a compiler from the functional logic language Curry to Haskell. As the result is a real extension of Haskell, there has to be SOME side effect involved. Unfortunately, this seems to prevent me from using any of ghc's optimizations on the resulting code. I have tried for some time to invoke the no-inline pragmata, but they seem to have no effect at all. Recently at ICFP, Neil Mitchell told me that there definitely is a way to avoid this problem. But does anybody know how?
Thanks for your help! Bernd Brassel
Can you give a specific example of what you have tried to do, and how it failed? Thanks, Don
Hi Neil, hi Don! Nice meeting you at ICFP by the way.
Can you give a specific example of what you have tried to do, and how it failed?
I have attached a short synopsis of what our Curry to Haskell conceptually does. I could explain what all the parts mean and why they are defined this way, if it is important. On first glance it looks as if we were doing unsafe things in the very worst way. But the invariants within the generated code clean up things again. E.g., the result of main does not at all depend on whether or not the program is evaluated eagerly or lazily. I hope it is okay that I did not add any no-inline pragmata or something like that. Unfortunately, I forgot all the things we have tried more than a year ago to make optimization work. But this is the way it should work: $ ghc --make -O0 -o curry-no-opt curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-no-opt ... $ curry-no-opt 3 possibilities: [True,True,False] 2 possibilities: [True,False] and this is what happens after optimization: $ rm curry.hi curry.o $ ghc --make -O2 -o curry-opt curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-opt ... $ curry-opt 3 possibilities: [True,False] 2 possibilities: [True,False] As the code is now that is no surprise. But how can I prevent this from happening by adding pragmata? Thanks a lot for your time! Bernd
Hi, I think it's the let floating (out) together with common subexpression elimination:
ghc --make -O2 -no-recomp -fno-cse -o curry-no-cse curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-no-cse ... ghc --make -O2 -no-recomp -fno-full-laziness -o curry-no-fll curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-no-fll ... ghc --make -O2 -no-recomp -fno-full-laziness -fno-cse -o curry-no-cse-no-fll curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-no-cse-no-fll ... ./curry-no-cse 3 possibilities: [True,False] 2 possibilities: [True,False] ./curry-no-fll 3 possibilities: [True,False] 2 possibilities: [True,False] ./curry-no-cse-no-fll 3 possibilities: [True,True,False] 2 possibilities: [True,False]
Regards, David ps.: Maybe it is interesting to look at HasFuse [1] (somewhat outdated), but it exactly forbids both transformations [1] http://www.ki.informatik.uni-frankfurt.de/research/diamond/hasfuse/ Bernd Brassel wrote:
Hi Neil, hi Don!
Nice meeting you at ICFP by the way.
Can you give a specific example of what you have tried to do, and how it failed?
I have attached a short synopsis of what our Curry to Haskell conceptually does. I could explain what all the parts mean and why they are defined this way, if it is important. On first glance it looks as if we were doing unsafe things in the very worst way. But the invariants within the generated code clean up things again. E.g., the result of main does not at all depend on whether or not the program is evaluated eagerly or lazily.
I hope it is okay that I did not add any no-inline pragmata or something like that. Unfortunately, I forgot all the things we have tried more than a year ago to make optimization work.
But this is the way it should work:
$ ghc --make -O0 -o curry-no-opt curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-no-opt ... $ curry-no-opt 3 possibilities: [True,True,False] 2 possibilities: [True,False]
and this is what happens after optimization:
$ rm curry.hi curry.o $ ghc --make -O2 -o curry-opt curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-opt ... $ curry-opt 3 possibilities: [True,False] 2 possibilities: [True,False]
As the code is now that is no surprise. But how can I prevent this from happening by adding pragmata?
Thanks a lot for your time!
Bernd
------------------------------------------------------------------------
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
On Tue, Oct 16, 2007 at 04:06:26PM +0200, Bernd Brassel wrote:
Hi Neil, hi Don!
Nice meeting you at ICFP by the way.
Can you give a specific example of what you have tried to do, and how it failed?
I have attached a short synopsis of what our Curry to Haskell conceptually does. I could explain what all the parts mean and why they are defined this way, if it is important. On first glance it looks as if we were doing unsafe things in the very worst way. But the invariants within the generated code clean up things again. E.g., the result of main does not at all depend on whether or not the program is evaluated eagerly or lazily.
I hope it is okay that I did not add any no-inline pragmata or something like that. Unfortunately, I forgot all the things we have tried more than a year ago to make optimization work.
Might I suggest, that the problem is your use of unsafePerformIO? If you use unsafePerformIO in accordance with the rules listed in the specification (which happens to be the FFI addendum), -O options will have no effect. (Not that what you are trying to do is achievable with correct use of unsafePerformIO; why do you want to do this unsafely, instead of just using 'length'? unsafePerformIO is a very slow function, remember) Stefan
Hi Stefan! Thanks for your answer. Stefan O'Rear wrote:
Might I suggest, that the problem is your use of unsafePerformIO?
Yes you might. And you are surely right. But not using it in this way is not an alternative.
why do you want to do this unsafely, instead of just using 'length'? unsafePerformIO is a very slow function, remember)
The big picture is that we generate programs like this example in order to compile the functional logic language Curry down to Haskell. Basically, there are two ways to do this: a) write an interpreter for Curry in Haskell, e.g., by employing non-determinism monads b) extend Haskell by employing side effects Alternative a) is not really an issue for us. Doing it this way, all Curry programs will suffer in performance in such a magnitude that - in comparison - unsafePerformIO is super-fast. In addition, we already have interpreters for Curry which I do not assume a Haskell interpreter to outperform without 5 years worth of tuning. Alternative b) is the choice, because doing it this way, all deterministic, i.e., purely functional parts of Curry programs would take advantage of Haskell being a functional language. If then the logic parts are not so fast, e.g., because unsafePerformIO is slow, this does not matter so much. In comparison to other approaches (like Alternative a) and many other implementations of Curry) our slogan is: "make functions fast and logic possible". Fast functions will outweigh the slowdown for logics. But to get "functions fast" employing optimization sounds like a good idea to me. But even without any optimization, our system can compare well to most other implementations for many applications. Thanks for your input! Bernd
On 10/17/07, Bernd Brassel
why do you want to do this unsafely, instead of just using 'length'? unsafePerformIO is a very slow function, remember)
The big picture is that we generate programs like this example in order to compile the functional logic language Curry down to Haskell. Basically, there are two ways to do this:
a) write an interpreter for Curry in Haskell, e.g., by employing non-determinism monads b) extend Haskell by employing side effects
Alternative a) is not really an issue for us. Doing it this way, all Curry programs will suffer in performance in such a magnitude that - in comparison - unsafePerformIO is super-fast. In addition, we already have interpreters for Curry which I do not assume a Haskell interpreter to outperform without 5 years worth of tuning.
Alternative b) is the choice, because doing it this way, all deterministic, i.e., purely functional parts of Curry programs would take advantage of Haskell being a functional language. If then the logic parts are not so fast, e.g., because unsafePerformIO is slow, this does not matter so much. In comparison to other approaches (like Alternative a) and many other implementations of Curry) our slogan is: "make functions fast and logic possible". Fast functions will outweigh the slowdown for logics. But to get "functions fast" employing optimization sounds like a good idea to me. But even without any optimization, our system can compare well to most other implementations for many applications.
May I suggest a third route that has the advantages of both your approaches. The backside is of course that it takes a bit of work. My suggestion is to do an effect analysis of your curry programs to identify the purely functional parts and compile them directly to pure Haskell. The rest of the programs can run in a monad. This approach should be more robust than relying on unsafePerformIO. It is also very much in the spirit of your slogan. Just my 2 cents, /Josef
May I suggest a third route that has the advantages of both your approaches. The backside is of course that it takes a bit of work. My suggestion is to do an effect analysis of your curry programs to identify the purely functional parts and compile them directly to pure Haskell. The rest of the programs can run in a monad. This approach should be more robust than relying on unsafePerformIO. It is also very much in the spirit of your slogan.
Thank you for the suggestion. We were thinking along the lines of identifying "the purely functional parts and compile them directly to pure Haskell" as a possibility of optimization (with some code duplication). But if the "rest of the programs can run in a monad" the question is: How much of the example program I submitted would you classify as "purely functional"? Actually, most of it is purely functional apart from the (?) - operator. But I do not see a way to make use of this. If, however, the whole program is classified as "non-functional" then this is definitely not in the spirit of the slogan. One effect we like very much about our implementation is that all expressions which do not depend on non-deterministic values are shared across the whole search. Note, that this dependence is a dynamic property. If the code of programs like the example was monadic, I do not see how not to loose this property. Thanks again! Bernd
May I suggest a third route that has the advantages of both your approaches. The backside is of course that it takes a bit of work. My suggestion is to do an effect analysis of your curry programs to identify the purely functional parts and compile them directly to pure Haskell. The rest of the programs can run in a monad. This approach should be more robust than relying on unsafePerformIO. It is also very much in the spirit of your slogan.
Thank you for the suggestion. We were thinking along the lines of identifying "the purely functional parts and compile them directly to pure Haskell" as a possibility of optimization (with some code duplication). But if the "rest of the programs can run in a monad" the question is: How much of the example program I submitted would you classify as "purely functional"? Actually, most of it is purely functional apart from the (?) - operator. But I do not see a way to make use of this. If, however, the whole program is classified as "non-functional" then this is definitely not in the spirit of the slogan. One effect we like very much about our implementation is that all expressions which do not depend on non-deterministic values are shared across the whole search. I suspect that any reasonably precise analysis will classify all the
Hi again,
On 10/17/07, Bernd Brassel
Note, that this dependence is a dynamic property. If the code of programs like the example was monadic, I do not see how not to loose this property.
I'm not quite sure what you mean when you say that dependence is dynamic.
Simon Peyton Jones said:
Adding these artificial dependencies may amount to exactly the kind of effect analysis that Josef suggests.
Yes such a determinism analysis is a good idea to optimize functional logic programs and we have already done work in that direction. But I would not like to turn those programs into a monad which we cannot prove to be deterministic. Your hint of "adding artificial dependencies" sounds more promising.
Don't take my suggestion of using monads too literally if you don't like monads. Indeed Simon's dependency injection can be formulated as a monad but you don't need to use monads if you don't want to. My point was that your programs will be divided into a pure part and an effectful part. Monads are just one way of capturing the effectfulness. Cheers, Josef
Hi David, thank you! This is really useful information!
I think it's the let floating (out) together with common subexpression elimination:
ghc --make -O2 -no-recomp -fno-cse -o curry-no-cse curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-no-cse ... ghc --make -O2 -no-recomp -fno-full-laziness -o curry-no-fll curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-no-fll ... ghc --make -O2 -no-recomp -fno-full-laziness -fno-cse -o curry-no-cse-no-fll curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-no-cse-no-fll ... ./curry-no-cse 3 possibilities: [True,False] 2 possibilities: [True,False] ./curry-no-fll 3 possibilities: [True,False] 2 possibilities: [True,False] ./curry-no-cse-no-fll 3 possibilities: [True,True,False] 2 possibilities: [True,False]
I will try this on large scale Curry programs. I hope the remaining optimizations will still do some good. Do you think that there is a way to be more selective? I mean to select those parts of the program which can and which cannot be optimized?
ps.: Maybe it is interesting to look at HasFuse [1] (somewhat outdated), but it exactly forbids both transformations
[1] http://www.ki.informatik.uni-frankfurt.de/research/diamond/hasfuse/
Yes, that looks interesting, too. Are there plans to update it with the ghc? Thanks for your hints! Bernd
Hi Bernd, Bernd Brassel wrote:
Hi David,
thank you! This is really useful information!
I think it's the let floating (out) together with common subexpression elimination:
ghc --make -O2 -no-recomp -fno-cse -o curry-no-cse curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-no-cse ... ghc --make -O2 -no-recomp -fno-full-laziness -o curry-no-fll curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-no-fll ... ghc --make -O2 -no-recomp -fno-full-laziness -fno-cse -o curry-no-cse-no-fll curry.hs [1 of 1] Compiling Main ( curry.hs, curry.o ) Linking curry-no-cse-no-fll ... ./curry-no-cse 3 possibilities: [True,False] 2 possibilities: [True,False] ./curry-no-fll 3 possibilities: [True,False] 2 possibilities: [True,False] ./curry-no-cse-no-fll 3 possibilities: [True,True,False] 2 possibilities: [True,False]
I will try this on large scale Curry programs. I hope the remaining optimizations will still do some good. Do you think that there is a way to be more selective? I mean to select those parts of the program which can and which cannot be optimized?
I think this would require an analysis of the code during compilation (to split into "pure" parts and "impure" parts), but we did not investigate this.
ps.: Maybe it is interesting to look at HasFuse [1] (somewhat outdated), but it exactly forbids both transformations
[1] http://www.ki.informatik.uni-frankfurt.de/research/diamond/hasfuse/
Yes, that looks interesting, too. Are there plans to update it with the ghc?
Honestly, we did nothing since 2004 on the code, but maybe we could port the changes to the current source of ghc. I remember that in an early version of ghc (I think < 5) there was an option -O file which gave the user control over the optimizations with a script, this would probably a nice feature to have again... Regards, David
Thanks for your hints! Bernd _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
I think you'll find it useful to be explicit about what you are relying on. For example I think that if your program contains two calls unsafePerformIO e1 unsafePerformIO e2 then * You don't care about the *order* in which these are performed * You do care that they are both performed separately, even if e1=e2. That is, you do not want CSE (common sub-expression) * I'm not sure whether you care if they are not performed at all. E.g. if you have let x = unsafePerformIO e in True then GHC will discard the binding for x. You can control this by adding data dependencies, so that the body of the 'let' depends on 'x'. * I'm not sure if you care whether they are performed once or many times. E.g. f = \x. x + unsafePerformIO (h z) If the (h z) doesn't mention 'x', GHC will transform this to v = unsafePerformIO (h z) f = \x. x+v So now the effect happens once only, rather than once per call of f. Again you can control this by adding an articifical dependency on x. Adding these artificial dependencies may amount to exactly the kind of effect analysis that Joesef suggests. Simon | -----Original Message----- | From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users-bounces@haskell.org] On | Behalf Of Bernd Brassel | Sent: 17 October 2007 09:02 | To: glasgow-haskell-users@haskell.org | Subject: Prevent optimization from tempering with unsafePerformIO | | Hi David, | | thank you! This is really useful information! | | > I think it's the let floating (out) together with common subexpression | > elimination: | > | > > ghc --make -O2 -no-recomp -fno-cse -o curry-no-cse curry.hs | > [1 of 1] Compiling Main ( curry.hs, curry.o ) | > Linking curry-no-cse ... | > > ghc --make -O2 -no-recomp -fno-full-laziness -o curry-no-fll curry.hs | > [1 of 1] Compiling Main ( curry.hs, curry.o ) | > Linking curry-no-fll ... | > > ghc --make -O2 -no-recomp -fno-full-laziness -fno-cse -o | > curry-no-cse-no-fll curry.hs | > [1 of 1] Compiling Main ( curry.hs, curry.o ) | > Linking curry-no-cse-no-fll ... | > > ./curry-no-cse | > 3 possibilities: [True,False] | > 2 possibilities: [True,False] | > > ./curry-no-fll | > 3 possibilities: [True,False] | > 2 possibilities: [True,False] | > > ./curry-no-cse-no-fll | > 3 possibilities: [True,True,False] | > 2 possibilities: [True,False] | | I will try this on large scale Curry programs. I hope the remaining | optimizations will still do some good. Do you think that there is a way | to be more selective? I mean to select those parts of the program which | can and which cannot be optimized? | | > ps.: Maybe it is interesting to look at HasFuse [1] (somewhat outdated), | > but it exactly forbids both transformations | > | > [1] http://www.ki.informatik.uni-frankfurt.de/research/diamond/hasfuse/ | | Yes, that looks interesting, too. Are there plans to update it with the | ghc? | | Thanks for your hints! | Bernd | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
I think you'll find it useful to be explicit about what you are relying on.
Yes, good point.
For example I think that if your program contains two calls unsafePerformIO e1 unsafePerformIO e2 then * You don't care about the *order* in which these are performed
Right, the order is not important.
* You do care that they are both performed separately, even if e1=e2. That is, you do not want CSE (common sub-expression)
Right.
* I'm not sure whether you care if they are not performed at all. E.g. if you have let x = unsafePerformIO e in True
I do not care whether or not the action is performed. Even more so, if the whole evaluation strategy is not lazy but speculatively eager or something the like, this does not change the semantics of our programs.
* I'm not sure if you care whether they are performed once or many times. E.g. f = \x. x + unsafePerformIO (h z) If the (h z) doesn't mention 'x', GHC will transform this to v = unsafePerformIO (h z) f = \x. x+v So now the effect happens once only, rather than once per call of f. Again you can control this by adding an articifical dependency on x.
This is a very good example. The effect has to happen once per call to f. So what do you mean by "adding an artificial dependency"? Would for this example something like the following be enough? f = \x. x + myEffect x myEffect _ = unsafePerformIO (h z)
Adding these artificial dependencies may amount to exactly the kind of effect analysis that Joesef suggests.
Yes such a determinism analysis is a good idea to optimize functional logic programs and we have already done work in that direction. But I would not like to turn those programs into a monad which we cannot prove to be deterministic. Your hint of "adding artificial dependencies" sounds more promising. The hints and suggestions I got in this thread are already very helpful, thanks for that! Bernd
Bernd Brassel wrote:
* I'm not sure if you care whether they are performed once or many times. E.g. f = \x. x + unsafePerformIO (h z) If the (h z) doesn't mention 'x', GHC will transform this to v = unsafePerformIO (h z) f = \x. x+v So now the effect happens once only, rather than once per call of f. Again you can control this by adding an articifical dependency on x.
This is a very good example. The effect has to happen once per call to f.
So what do you mean by "adding an artificial dependency"? Would for this example something like the following be enough?
f = \x. x + myEffect x
myEffect _ = unsafePerformIO (h z)
Adding these artificial dependencies may amount to exactly the kind of effect analysis that Joesef suggests.
Yes such a determinism analysis is a good idea to optimize functional logic programs and we have already done work in that direction. But I would not like to turn those programs into a monad which we cannot prove to be deterministic. Your hint of "adding artificial dependencies" sounds more promising.
perhaps unsafePerformIODependingOn :: dep -> IO a -> a {-# NOINLINE unsafePerformIODependingOn #-} --is that pragma enough to avoid strictness/unused-ness analysis? --use 'lazy'? compile the module this is defined in with -O0? --I don't think seq'ing dep is desired. unsafePerformIODependingOn dep a = unsafePerformIO a f = \x. x + unsafePerformIODependingOn (x) (h z) --use a tuple if there are multiple variables you depend on also, do you care if the same `unsafePerformIO` is repeatedly performed more than once for no reason? Isaac
participants (7)
-
Bernd Brassel -
David Sabel -
Don Stewart -
Isaac Dupree -
Josef Svenningsson -
Simon Peyton-Jones -
Stefan O'Rear