Hi Haskellers, which compiler settings do I have to pass to ghc-5.02 in order to achieve that the strictness analyzer recognizes strictness of (+) in foldl and computes sum in constant space? Prelude> sum [1..10000000] had the following effect: PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND 23542 herrmann 20 0 250M 130M 97500 R 66.3 52.4 0:21 ghc-5.02 Of course, one could define a strict foldl oneself:
sfoldl f e [] = e sfoldl f e (x:xs) = (sfoldl f $! (f e x)) xs
( > sfoldl (+) 0 [1..10000000] returns 50000005000000 in about a minute interpreted using 18MB of total space.) But with the own definition one has to redefine many of the prelude functions. Thanks in advance -- Christoph Herrmann
"Ch. A. Herrmann" <herrmann@infosun.fmi.uni-passau.de> wrote,
which compiler settings do I have to pass to ghc-5.02 in order to achieve that the strictness analyzer recognizes strictness of (+) in foldl and computes sum in constant space?
Prelude> sum [1..10000000]
had the following effect:
PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND 23542 herrmann 20 0 250M 130M 97500 R 66.3 52.4 0:21 ghc-5.02
Is this what I think it is? Do you benchmark the interpreter? Interpreted code isn't optimised. When I compile main = print $ sum [1..10000000] with -O2, it takes 13s on a 600MHz P3 and runs in 1.5MB of space. Now, you may think that `sum' should have been compiled optimised in the Prelude and you just call this optimised version from the interpreter. However, this reasoning is flawed for a number of reasons (one being that you won't make use of specialised versions of Prelude functions in this way).
Of course, one could define a strict foldl oneself:
sfoldl f e [] = e sfoldl f e (x:xs) = (sfoldl f $! (f e x)) xs
( > sfoldl (+) 0 [1..10000000] returns 50000005000000 in about a minute interpreted using 18MB of total space.)
But with the own definition one has to redefine many of the prelude functions.
GHC's Prelude does not define `sum' in terms of foldl; instead, it uses the definition sum :: (Num a) => [a] -> a sum l = sum' l 0 where sum' [] a = a sum' (x:xs) a = sum' xs (a+x) The Prelude also defines a specialisation of the function for `Integer' (which is what you get in your example) by way of {-# SPECIALISE sum :: [Integer] -> Integer #-} I haven't checked the Core code produced for the above definition, but as I know GHC, I am pretty sure that it compiles the Prelude definition into a nice tight loop making use of all available strictness. Cheers, Manuel
Hi,
Is this what I think it is? Do you benchmark the interpreter? Interpreted code isn't optimised. When I compile
main = print $ sum [1..10000000]
with -O2, it takes 13s on a 600MHz P3 and runs in 1.5MB of space.
Out of curiousity, why doesn't this get compiled down to main = print 50000005000000 ? That is, why doesn't the compiler carry out the calculation and then just embed that in the compiled version? I know that some C compilers do (at least somewhat) similar things when, for example, you say: x = y * 4 it will rewrite this as x = y << 2 and even do more complicated stuff, like if you say x = y * 12 it will give x = 3 * (y << 2) or whatnot. can I expect this from ghc/nhc/etc? - hal
Hal Daume III <hdaume@ISI.EDU> wrote,
Is this what I think it is? Do you benchmark the interpreter? Interpreted code isn't optimised. When I compile
main = print $ sum [1..10000000]
with -O2, it takes 13s on a 600MHz P3 and runs in 1.5MB of space.
Out of curiousity, why doesn't this get compiled down to
main = print 50000005000000
?
That is, why doesn't the compiler carry out the calculation and then just embed that in the compiled version?
Because the compiler can't be sure that the computation terminates. If it doesn't, the compiler would not terminate, which usually makes users quite unhappy ;-)
I know that some C compilers do (at least somewhat) similar things when, for example, you say:
x = y * 4
it will rewrite this as
x = y << 2
and even do more complicated stuff, like if you say
x = y * 12
it will give
x = 3 * (y << 2)
or whatnot.
can I expect this from ghc/nhc/etc?
These kinds of optimisations are different from the use of a Prelude function like `sum', because they don't affect the termination behaviour of the compiler. With -fvia-C GHC will generate C code that is, then, run through the C compiler. If you take this route, then optimisations, such as those you describe, are performed by the C compiler on your Haskell code. The natice code generator probably also performs some of those optimisations, but I am not sure exactly which. Cheers, Manuel
Hi Manuel, >> PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND 23542 >> herrmann 20 0 250M 130M 97500 R 66.3 52.4 0:21 ghc-5.02 Manuel> Is this what I think it is? Do you benchmark the Manuel> interpreter? Interpreted code isn't optimised. not really. I wanted to have a strict foldl (for a different purpose than sum) and could not figure out how to tell the compiler. I tried different things, precompile just one module, compile the entire program, using -fglasgow-exts, but nothing seems to work. Thus, I reduced the problem to sum to make it simpler for you. However, the sum computation based on my sfold definition did not take too long even with the interpreter. Thus, I wondered why the predefined sum computation behaves that bad. Manuel> GHC's Prelude does not define `sum' in terms of foldl; Manuel> instead, it uses the definition ... Where can I find the ghc prelude? Is there also the definition of the mysterious foldl' function which I saw from time to time before it disappeared again? Manuel> I haven't checked the Core code produced for the above Manuel> definition, but as I know GHC, I am pretty sure that it Manuel> compiles the Prelude definition into a nice tight loop Manuel> making use of all available strictness. One would expect that ghci uses a compiled version of sum. Does it or not? Cheers -- Christoph
"Ch. A. Herrmann" wrote:
Hi Haskellers,
which compiler settings do I have to pass to ghc-5.02 in order to achieve that the strictness analyzer recognizes strictness of (+) in foldl and computes sum in constant space?
Prelude> sum [1..10000000]
had the following effect:
PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND 23542 herrmann 20 0 250M 130M 97500 R 66.3 52.4 0:21 ghc-5.02
Of course, one could define a strict foldl oneself:
sfoldl f e [] = e sfoldl f e (x:xs) = (sfoldl f $! (f e x)) xs
There is a foldl' in the Hugs Prelude that does this: foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs There are some functions in the Hugs Prelude that use foldl (or foldl1) and some use foldl'. Maybe someone can explain why certain functions use foldl: reverse, maximum, minimum and readInt, while others use foldl': length, sum and product. I can understand why reverse would use foldl, but why do maximum, minimum and readInt use foldl ? Maybe the function foldl1 was based on foldl' at one time ? Jan
participants (4)
-
Ch. A. Herrmann -
Hal Daume III -
Jan Kort -
Manuel M. T. Chakravarty