RE: -allow-extension-for-bottom
Ah I see. You get earlier results, but the overall computation is unchanged. Hmm. I can't say I'm persuaded. The transformation is unsound in general and, because it makes programs lazier, it'll slow programs down a bit; in exchange there's the possibility of earlier output (which may or may not be visible in the ultimate result). I think you are better off writing the program you want, rather than relying on the compiler to find it for you! Simon | -----Original Message----- | From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users- | bounces@haskell.org] On Behalf Of Serge D. Mechveliani | Sent: 11 October 2004 13:32 | To: Simon Peyton-Jones | Cc: glasgow-haskell-users@haskell.org | Subject: Re: -allow-extension-for-bottom | | First, thanks to the people who correct me about `equivalence', | (I skip the name because the letter was addressed privately). | | Because we do not mean to compile each program to the equivalent | one of | error "bottom" | | | On Mon, Oct 11, 2004 at 12:44:49PM +0100, Simon Peyton-Jones wrote: | > Can you give a small program that runs 1000x faster in one form compared | > with the other? | > | > Currently, if foo is strict, GHC transforms (2) into (1), not the other | > way round. In general, transforming (1) into (2) looks hard, because it | > means finding the common portions of two expressions. | | Anywhay, this looks like an appropriate business for a clever | compliler (under some option). | | > But I'd be | > interested to see cases where you get a lot of performance from such a | > transformations. | > | > Simon | > | | | I my recent practical example, the program with the factored `if' | prints out in 1 second a very useful information on the first | `steps' of a certain proof (the last steps take long), | while the unfactored version holds the whole result until 30 seconds. | But this is on the toy example. In practice, this may be, say, | 100 hours, because the prover is allowed and expected to think long. | The simplified version of the program is | | main = hSetBuffering stdout NoBuffering >> putStr (out "\n") | | out :: String -> String | | out = let valueTakingLong = last [1 .. (10^7)] > 0 | in | if valueTakingLong then ('a' :) . ('b' :) | else ('a' :) . ('b' :) | | The author intended 'a' to appear immediately. | But it appears only after a long time. | | This is hard to control such things in practice, | one has to take effort to write the factored program. | And usually, this is immaterial whether in (if p x) | (p x) may yield bottom. | | I suspect that | (1) the example can be changed so that the full evaluation time | difference will be 1000 times | (somewhat apply `head' to the above `if' expression ...) | | (2) this concerns not only the `if' factoring, this effects the | `bottom' treating in general. | | What do you think of this? | | ----------------- | Serge Mechveliani | mechvel@botik.ru | | | | > | -----Original Message----- | > | From: glasgow-haskell-users-bounces@haskell.org | > [mailto:glasgow-haskell-users- | > | bounces@haskell.org] On Behalf Of Serge D. Mechveliani | > | Sent: 11 October 2004 12:22 | > | To: haskell@haskell.org | > | Cc: glasgow-haskell-users@haskell.org | > | Subject: -allow-extension-for-bottom | > | | > | Dear Haskell implementors, | > | | > | Consider the compilation flag -allow-extension-for-bottom | > | | > | which changes the language meaning so that allows to ignore | > | the bottom value. For example, the programs | > | | > | (1) (\ x -> (if p x then foo (g x) else foo (h x)) ) | > | and | > | (2) (\ x -> foo ((if p x then g x else h x)) ) | > | | > | become equivalent, and many program transformations become | > | possible. | > | I suspect that after compiling and running of a program under | > | -allow-extension-for-bottom the user will discover many helpful | > | information about the original program. | > | For example, under -allow-extension-for-bottom it may run 1000 | > | times faster, and then, the user finds out what to change to have | > | a 1000 times speed-up for the original program for the standard | > | Haskell. | > | | > | Thus, in my particular practical example, it is evident to me that | > | it is better to specify (2). But many similar effects are hard to | > | find out without compiling under -allow-extension-for-bottom. | > | | > | Maybe, the compiler could issue the warnings like, say, | > | | > | "Consider factoring `if' in ... This may improve ... " | > | ? | > | | > | Copy, please, the answer to mechvel@botik.ru, | > | | > | ----------------- | > | Serge Mechveliani | > | mechvel@botik.ru | > | | > | | > | | > | | > | _______________________________________________ | > | Glasgow-haskell-users mailing list | > | Glasgow-haskell-users@haskell.org | > | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users | > | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
On Mon, Oct 11, 2004 at 04:35:30PM +0100, Simon Peyton-Jones wrote:
Ah I see. You get earlier results, but the overall computation is unchanged.
Hmm. I can't say I'm persuaded. The transformation is unsound in general and, because it makes programs lazier, it'll slow programs down a bit; in exchange there's the possibility of earlier output (which may or may not be visible in the ultimate result).
I think you are better off writing the program you want, rather than relying on the compiler to find it for you!
I am sorry, there was a typo. The `else' branch should contain 'c' instead of 'b': main = hSetBuffering stdout NoBuffering >> putStr (out "\n") out :: String -> String out = let valueTakingLong = last [1 .. (10^8)] > 0 in if valueTakingLong then ('a' :) . ('b' :) else ('a' :) . ('c' :) (as you note, it has some sense even with the typo). Also here is an example of 1000 times speed up by factoring `if': main = putStr (f:"\n") f :: Char f = let valueTakingLong = last [1 .. (10^8)] > 0 in head (if valueTakingLong then 'a': "b" else 'a': "c") -- head ('a': (if valueTakingLong then "b" else "c")) Factoring `if' means un-commenting the last line. And further, such factoring leads to the complile-time transformation f --> 'a'. These two examples are very artificial. Why does not the programmer define directly f = 'a' ? The real program is like this: prove :: Goal -> ProofResult prove g = let res' = prove (deriveFrom g) :: ProofResult trace' = pTrace res' -- recurse, obtain res' and add something to -- some fields of res' in case (foo g, foo' g) of (A, _) -> res' {... = ..., pTrace = ('a' :) . ('b' :) . trace' } :: ProofResult (_, B) -> res' {... = ..., pTrace = ('a' :) . ('c' :) . trace' } _ -> ... And pTrace prints out not `lazily': one needs to wait 1 hour instead of immediately observing the first members of the final pTrace. The effect is the same as of 1000 times slow down. Because in many cases it is sufficient to observe the first steps and to find out what to improve. The intention was: "compute it as in the factored `case' form". And now I need to rewrite it in such a form. It takes effort to find out how to write this in a natural way, while the initial program did not require any effort to write. Generally, what I fear of is a hidden slow down. In the above case it was easy to detect the effect, because it shouted on the print-out. But it may occur that many other fragments contain the slow downs of 10-20 times caused by the reasons like unfactored `if', and they are hard to discover, because they do not shout on the print-out. Though, I have not any convincing example, so far. ----------------- Serge Mechveliani mechvel@botik.ru
participants (2)
-
Serge D. Mechveliani -
Simon Peyton-Jones