Q: Forcing repeated evaluation
Hello, I have another question regarding the optimisation of Haskell code: I have a relatively inexpensive function generating a long list, imagine something like (I simplified a lot): l = [ i*i*i | i <- [0..n] ] -- for very large n This long list is consumed several times in the program: x1 = f1 l x2 = f2 x1 l x3 = f3 x2 l I found that the list l is calculated just once and that the computational time is dominated by the allocations and garbage collection. I want to try to force l to be generated on-the-fly every time it is needed, to see if it improves performance. What is a good way to do it? Would something like unsafePerformIO $ return l do the job? Isn'it there any flag for the compiler (ghc) to suggest this optimisation? Thank you for your feedback. Jan -- ------------------------------------------------------------------------- Jan Kybic <kybic@ieee.org> Odyssee, INRIA, Sophia-Antipolis, France or <Jan.Kybic@sophia.inria.fr>,tel. work +33 492 38 7589, fax 7845 http://www-sop.inria.fr/odyssee/team/Jan.Kybic/index.en.html
tor 2002-09-12 klockan 11.27 skrev Jan Kybic:
Hello, I have another question regarding the optimisation of Haskell code: I have a relatively inexpensive function generating a long list, imagine something like (I simplified a lot):
l = [ i*i*i | i <- [0..n] ] -- for very large n
This long list is consumed several times in the program:
x1 = f1 l x2 = f2 x1 l x3 = f3 x2 l
I found that the list l is calculated just once and that the computational time is dominated by the allocations and garbage collection. I want to try to force l to be generated on-the-fly every time it is needed, to see if it improves performance. What is a good way to do it? Would something like
unsafePerformIO $ return l
do the job? Isn'it there any flag for the compiler (ghc) to suggest this optimisation? Thank you for your feedback.
The easiest way is to make it a function l _ = [ i*i*i | i <- [0..n] ] -- for very large n x1 = f1 (l ()) x2 = f2 x1 (l ()) x3 = f3 x2 (l ()) () can be any value really. Regards, Martin -- Martin Norbäck d95mback@dtek.chalmers.se Kapplandsgatan 40 +46 (0)708 26 33 60 S-414 78 GÖTEBORG http://www.dtek.chalmers.se/~d95mback/ SWEDEN OpenPGP ID: 3FA8580B
On Thursday 12 September 2002 10:43 am, Martin Norbäck wrote:
tor 2002-09-12 klockan 11.27 skrev Jan Kybic:
Hello, I have another question regarding the optimisation of Haskell code: I have a relatively inexpensive function generating a long list, imagine something like (I simplified a lot):
l = [ i*i*i | i <- [0..n] ] -- for very large n
This long list is consumed several times in the program:
x1 = f1 l x2 = f2 x1 l x3 = f3 x2 l
I found that the list l is calculated just once and that the computational time is dominated by the allocations and garbage collection. I want to try to force l to be generated on-the-fly every time it is needed, to see if it improves performance. What is a good way to do it? Would something like
unsafePerformIO $ return l
do the job? Isn'it there any flag for the compiler (ghc) to suggest this optimisation? Thank you for your feedback.
The easiest way is to make it a function
l _ = [ i*i*i | i <- [0..n] ] -- for very large n
x1 = f1 (l ()) x2 = f2 x1 (l ()) x3 = f3 x2 (l ())
I asked a similar question a while ago, and (I think) there was general agreement that this was not a reliable solution because the expression (l ()) is still a CAF and there's nothing to stop a Haskell implementation "optimising" occurrences of this expression to a single shared heap object (and creating a space leak potentially). I think whether or not this works reliably depends on compiler implementation and/or chosen optimisation level. I understand that Clean addresses this problem by defining the language semantics in terms of graph re-writing rather than lambda calculus. So, I guess Clean outlaws transformations which change the sharing of graphs. It seems a pity something similar can't be done for Haskell. For GHC I was told the -fno-full-laziness flag (or something like that) will stop the sharing, but the GHC doc's make no mention of this flag as far as I can see :-( Regards -- Adrian Hey
collection. I want to try to force l to be generated on-the-fly every time it is needed, to see if it improves performance. What is a good way to do it? Would something like
... The easiest way is to make it a function
l _ = [ i*i*i | i <- [0..n] ] -- for very large n
I asked a similar question a while ago, and (I think) there was general agreement that this was not a reliable solution because the expression
I found a solution which works in some cases. For example: reeval f x = do xref <- newIORef x x' <- readIORef xref return (f x') Then the IO action "reeval f x" should reevalue f each time it is invoked. Is this safe? Will this work in all cases? Thanks for any comments. -- ------------------------------------------------------------------------- Jan Kybic <kybic@ieee.org> Odyssee, INRIA, Sophia-Antipolis, France or <Jan.Kybic@sophia.inria.fr>,tel. work +33 492 38 7589, fax 7845 http://www-sop.inria.fr/odyssee/team/Jan.Kybic/index.en.html
On 17 Sep 2002, Jan Kybic wrote:
collection. I want to try to force l to be generated on-the-fly every time it is needed, to see if it improves performance. What is a good way to do it? Would something like
... The easiest way is to make it a function
l _ = [ i*i*i | i <- [0..n] ] -- for very large n
I asked a similar question a while ago, and (I think) there was general agreement that this was not a reliable solution because the expression
Note that (assuming that I'm not missing something) you can prevent the moving of expressions involving l in a very ugly way by noting that these `dummy argument functions' are polymorphic so that you could write x1 = f1 (l 1) x2 = f2 x1 (l 2) x3 = f3 x2 (l 3) (ie using a different argument for each one) since I'm pretty sure none of the Haskell compilers attempt to replace an lhs by an rhs before attempting lambda lifting. The nasty thing about this is of course that the onus is now on you to ensure you don't repeat an argument; you don't get any help from the type system. ___cheers,_dave_________________________________________________________ www.cs.bris.ac.uk/~tweed/ | `It's no good going home to practise email:tweed@cs.bris.ac.uk | a Special Outdoor Song which Has To Be work tel:(0117) 954-5250 | Sung In The Snow' -- Winnie the Pooh
Jan Kybic wrote:
Hello, I have another question regarding the optimisation of Haskell code: I have a relatively inexpensive function generating a long list, imagine something like (I simplified a lot):
l = [ i*i*i | i <- [0..n] ] -- for very large n
This long list is consumed several times in the program:
x1 = f1 l x2 = f2 x1 l x3 = f3 x2 l
I found that the list l is calculated just once and that the computational time is dominated by the allocations and garbage collection. I want to try to force l to be generated on-the-fly every time it is needed, to see if it improves performance. What is a good way to do it? Would something like
unsafePerformIO $ return l
do the job? Isn'it there any flag for the compiler (ghc) to suggest this optimisation? Thank you for your feedback.
Jan
A simple solution is to "decaf" the offending definition. Give l an argument of trivial type: replace l both in its definition and at all point of use by the application l ().
participants (5)
-
Adrian Hey -
Colin Runciman -
D. Tweed -
Jan Kybic -
Martin Norbäck