[Haskell-cafe] Puzzled about inlining and specialise inline under ghc -O2
Dear Haskell-Cafe,
I'm computing a histogram of a bunch of symbols with up to 8 bits of
information each, stored in a unboxed vector of Word8. The histogram is
represented as an unboxed vector of Int with size 2^bits. I compute the
histogram by folding an increment function.
The problem: depending on what types and what annotations I give to the
increment and histogram function (see below), the GC gets through a
different amount of memory. I'm using GHC 7.0.3 and -O2. I'd like to
better understand how and why the optimisation does/doesn't kick in.
Here are the functions with the most generic types I can think of:
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Unboxed.Mutable as UMV
import Control.Monad.Primitive (PrimMonad, PrimState)
increment :: (PrimMonad m, UMV.Unbox a, Num a, Integral b) =
UMV.MVector (PrimState m) a - b - m (UMV.MVector (PrimState m) a)
increment v x = do
n - UMV.read v (fromIntegral x)
UMV.write v (fromIntegral x) (n+1)
return v
histogram :: (Integral a, UMV.Unbox a) = Int - UV.Vector a -
UV.Vector Int
histogram bitsPerSym v = runST $ do
a - UMV.replicate (2^bitsPerSym) (0::Int)
a' - UV.foldM' increment a v
UV.unsafeFreeze a'
Running my test load, I get: total alloc = 33,206,568 bytes
Looking at the core, ghc is not specialising the functions, even if I
tell it to inline them. So let's brutally change the types to be as
specific as I need for my application:
increment :: UMV.MVector s Int - Word8 - ST s (UMV.MVector s Int)
histogram :: Int - UV.Vector Word8 - UV.Vector Int
result: total alloc = 19,581,152 bytes
and if I put INLINE pragmas for both functions: 16,952,512 bytes
I should be able to achieve the same effect with SPECIALISE INLINE
pragmas, right? Let's try that:
{-# SPECIALISE INLINE increment :: UMV.MVector s Int - Word8 - ST s
(UMV.MVector s Int) #-}
{-# SPECIALISE INLINE histogram :: Int - UV.Vector Word8 - UV.Vector
Int #-}
result: 33,139,856 bytes
(GHC can't figure out application of the first rule, giving:
Warning: RULE left-hand side too complicated to desugar)
So unfortunately my most generic form won't work here, I need to
specialise increment to be in ST (which sucks, because I want it to work
for both IO and ST):
increment :: (UMV.Unbox a, Num a, Integral b) =
UMV.MVector s a - b - ST s (UMV.MVector s a)
{-# SPECIALISE INLINE increment :: UMV.MVector s Int - Word8 - ST s
(UMV.MVector s Int) #-}
result: 17,016,192 bytes
This is very close to the most specific function instantiations and
INLINE, but:
- I've lost being generic between ST and IO
- it's still a little bigger than the specific instances + INLINE
So my questions are: what is going on? Can I have genericity between ST
and IO while keeping the low GC usage? How come SPECIALISE INLINE does
not give the same result as specific instances + INLINE?
Obviously, for this example, I don't really *need* increment to work
inside IO, since I'm using runST... but I want to understand what
is going on. Profiling Haskell performance and memory usage has always
been difficult for me.
Much thanks in advance,
Rafal Kolanski.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Puzzled
Ouch, now I really feel stupid, because I *knew* about the stricter
foldl' version.
But great to know about the new strictness on vars! I really should get
GHC 6.8 RC1 for Windows...
I just got puzzled why mysum worked better than sum for some reason...
mysym looks like an identical unfolded version of sum to me, yet it
behaved differently. mysum, also being non-strict, did *not* stack
overflow. Maybe because it is a simpler / more unfolded version, so it
needs to keep less euh unevaluated thunks (how are these called?) on
the stack? So I would also have gotten a stack overflow with mysum, it
just needed more iterations?
Many thanks,
Peter
Bertram Felgenhauer wrote:
Peter Verswyvelen wrote:
The following code, when compiled with GHC 6.6.1 --make -O gives a stack
overflow when I enter 100 as a command line argument:
(please don't look at the efficiency of the code, it can of course be
improved a lot both in time performance and numeric precision...)
import System
leibnizPI :: Integer - Double
leibnizPI n = sum (map leibnizTerm [0..n]) where
leibnizTerm n = let i = fromIntegral n
in 4 * (((-1) ** i) / (2*i+1))
main = do
args - getArgs
let n = read (head args)
print (leibnizPI n)
However, if I replace
main = print (leibnizPI 100)
is does not stack overflow.
Now, if I leave the original main, but replace sum in leibnizPI by
mysum xs = aux 0 xs
where
aux s (x:xs) = aux (s+x) xs
aux s [] = s
Then I don't get a stack overflow.
However, I do get a stack overflow when I compile it without -O, in all
cases.
This puzzles me. I don't see any non-tail calls in my code...
I guess it has to do with strictness?
http://www.haskell.org/haskellwiki/Performance/Strictness
Yes.
The problem is that without optimizations, both sum and mysum
build a large unevaluated expression of the form
((..((0+x1)+x2)+...)+xn)
The stack overflow happens when this expression gets evaluated. At that
point, the outermost (+) demands the result of the (+) on the next level,
and so on.
To prevent this you need a stricter version of sum. You can build one
with foldl':
import Data.List
sum' :: Num a = [a] - a
sum' = foldl' (+) 0
Arguably this is the correct definition of sum. The problem you
had is fairly common.
Why isn't it possible to annotate strictness on the type signature in
Haskell as in Clean? Is this on the TODO list?
Strictness is independent from the type in Haskell (but see the fourth
solution presented below). You can explicitely make one value at least
as strict as another using seq:
mysum' xs = aux 0 xs
where
aux s (x:xs) = let s' = s+x in s' `seq` aux s' xs
aux s [] = s
In ghc, you can mark arguments as strict
mysum'' xs = aux 0 xs
where
aux !s (x:xs) = aux (s+x) xs
aux !s [] = s
This is a language extension, you need -fbang-patterns
to allow it, or with a recent ghc (6.7, 6.9 or a 6.8 rc)
a {-# LANGUAGE BangPatterns #-} pragma, or -XBangPatterns.
A fourth possibility, which is Haskell 98 again, is to declare an
auxiliary data type with a strict field:
data Strict a = Strict !a
mysum''' xs = aux (Strict 0) xs
where
aux (Strict s) (x:xs) = aux (Strict (s+x)) xs
aux (Strict s) [] = s
Hope that helps,
Bertram
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Puzzled
2007/10/6, Peter Verswyvelen [EMAIL PROTECTED]: But great to know about the new strictness on vars! I really should get GHC 6.8 RC1 for Windows... Just in case you misunderstood : this functionality was already there in GHC 6.4, it's just the new syntax to active it that is available only in recent versions of GHC : this new syntax will hopefully be adopted by others Haskell compilers and thus become a compiler-agnostic way of specifying extensions to Haskell98 (so that others compiler than GHC can tell you why they won't compile this wonderful code that use all the latest extensions that have been included into your release candidate of GHC, much better than the old way where they just told you the syntax was wrong, isn't it ?). -- Jedaï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Puzzled
On 10/6/07, Bertram Felgenhauer [EMAIL PROTECTED] wrote:
This is a language extension, you need -fbang-patterns
to allow it, or with a recent ghc (6.7, 6.9 or a 6.8 rc)
a {-# LANGUAGE BangPatterns #-} pragma, or -XBangPatterns.
LANGUAGE pragmas (including BangPatterns) work just fine in 6.6, by the way.
Stuart
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Puzzled
Just to be clear, I doubt the difference had anything to do with
tail-recursion per se. My guess is that with the mysum version, ghc was
able to do some strictness analysis/optimization that it wasn't able to do
(for whatever reason) with the first version. The best solution (as others
have pointed out) is to create a strict version of sum with foldl'.
On 10/6/07, Peter Verswyvelen [EMAIL PROTECTED] wrote:
Ouch, now I really feel stupid, because I *knew* about the stricter
foldl' version.
But great to know about the new strictness on vars! I really should get
GHC 6.8 RC1 for Windows...
I just got puzzled why mysum worked better than sum for some reason...
mysym looks like an identical unfolded version of sum to me, yet it behaved
differently. mysum, also being non-strict, did *not* stack overflow. Maybe
because it is a simpler / more unfolded version, so it needs to keep less
euh unevaluated thunks (how are these called?) on the stack? So I would
also have gotten a stack overflow with mysum, it just needed more
iterations?
Many thanks,
Peter
Bertram Felgenhauer wrote:
Peter Verswyvelen wrote:
The following code, when compiled with GHC 6.6.1 --make -O gives a stack
overflow when I enter 100 as a command line argument:
(please don't look at the efficiency of the code, it can of course be
improved a lot both in time performance and numeric precision...)
import System
leibnizPI :: Integer - Double
leibnizPI n = sum (map leibnizTerm [0..n]) where
leibnizTerm n = let i = fromIntegral n
in 4 * (((-1) ** i) / (2*i+1))
main = do
args - getArgs
let n = read (head args)
print (leibnizPI n)
However, if I replace
main = print (leibnizPI 100)
is does not stack overflow.
Now, if I leave the original main, but replace sum in leibnizPI by
mysum xs = aux 0 xs
where
aux s (x:xs) = aux (s+x) xs
aux s [] = s
Then I don't get a stack overflow.
However, I do get a stack overflow when I compile it without -O, in all
cases.
This puzzles me. I don't see any non-tail calls in my code...
I guess it has to do with strictness?
http://www.haskell.org/haskellwiki/Performance/Strictness
Yes.
The problem is that without optimizations, both sum and mysum
build a large unevaluated expression of the form
((..((0+x1)+x2)+...)+xn)
The stack overflow happens when this expression gets evaluated. At that
point, the outermost (+) demands the result of the (+) on the next level,
and so on.
To prevent this you need a stricter version of sum. You can build one
with foldl':
import Data.List
sum' :: Num a = [a] - a
sum' = foldl' (+) 0
Arguably this is the correct definition of sum. The problem you
had is fairly common.
Why isn't it possible to annotate strictness on the type signature in
Haskell as in Clean? Is this on the TODO list?
Strictness is independent from the type in Haskell (but see the fourth
solution presented below). You can explicitely make one value at least
as strict as another using seq:
mysum' xs = aux 0 xs
where
aux s (x:xs) = let s' = s+x in s' `seq` aux s' xs
aux s [] = s
In ghc, you can mark arguments as strict
mysum'' xs = aux 0 xs
where
aux !s (x:xs) = aux (s+x) xs
aux !s [] = s
This is a language extension, you need -fbang-patterns
to allow it, or with a recent ghc (6.7, 6.9 or a 6.8 rc)
a {-# LANGUAGE BangPatterns #-} pragma, or -XBangPatterns.
A fourth possibility, which is Haskell 98 again, is to declare an
auxiliary data type with a strict field:
data Strict a = Strict !a
mysum''' xs = aux (Strict 0) xs
where
aux (Strict s) (x:xs) = aux (Strict (s+x)) xs
aux (Strict s) [] = s
Hope that helps,
Bertram
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Puzzled
The following code, when compiled with GHC 6.6.1 --make -O gives a stack overflow when I enter 100 as a command line argument: (please don't look at the efficiency of the code, it can of course be improved a lot both in time performance and numeric precision...) import System leibnizPI :: Integer - Double leibnizPI n = sum (map leibnizTerm [0..n]) where leibnizTerm n = let i = fromIntegral n in 4 * (((-1) ** i) / (2*i+1)) main = do args - getArgs let n = read (head args) print (leibnizPI n) However, if I replace main = print (leibnizPI 100) is does not stack overflow. Now, if I leave the original main, but replace sum in leibnizPI by mysum xs = aux 0 xs where aux s (x:xs) = aux (s+x) xs aux s [] = s then I don't get a stack overflow. However, I do get a stack overflow when I compile it without -O, in all cases. This puzzles me. I don't see any non-tail calls in my code... I guess it has to do with strictness? http://www.haskell.org/haskellwiki/Performance/Strictness Why isn't it possible to annotate strictness on the type signature in Haskell as in Clean? Is this on the TODO list? Many thanks, Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Puzzled
Peter Verswyvelen wrote:
The following code, when compiled with GHC 6.6.1 --make -O gives a stack
overflow when I enter 100 as a command line argument:
(please don't look at the efficiency of the code, it can of course be
improved a lot both in time performance and numeric precision...)
import System
leibnizPI :: Integer - Double
leibnizPI n = sum (map leibnizTerm [0..n]) where
leibnizTerm n = let i = fromIntegral n
in 4 * (((-1) ** i) / (2*i+1))
main = do
args - getArgs
let n = read (head args)
print (leibnizPI n)
However, if I replace
main = print (leibnizPI 100)
is does not stack overflow.
Now, if I leave the original main, but replace sum in leibnizPI by
mysum xs = aux 0 xs
where
aux s (x:xs) = aux (s+x) xs
aux s [] = s
Then I don't get a stack overflow.
However, I do get a stack overflow when I compile it without -O, in all
cases.
This puzzles me. I don't see any non-tail calls in my code...
I guess it has to do with strictness?
http://www.haskell.org/haskellwiki/Performance/Strictness
Yes.
The problem is that without optimizations, both sum and mysum
build a large unevaluated expression of the form
((..((0+x1)+x2)+...)+xn)
The stack overflow happens when this expression gets evaluated. At that
point, the outermost (+) demands the result of the (+) on the next level,
and so on.
To prevent this you need a stricter version of sum. You can build one
with foldl':
import Data.List
sum' :: Num a = [a] - a
sum' = foldl' (+) 0
Arguably this is the correct definition of sum. The problem you
had is fairly common.
Why isn't it possible to annotate strictness on the type signature in
Haskell as in Clean? Is this on the TODO list?
Strictness is independent from the type in Haskell (but see the fourth
solution presented below). You can explicitely make one value at least
as strict as another using seq:
mysum' xs = aux 0 xs
where
aux s (x:xs) = let s' = s+x in s' `seq` aux s' xs
aux s [] = s
In ghc, you can mark arguments as strict
mysum'' xs = aux 0 xs
where
aux !s (x:xs) = aux (s+x) xs
aux !s [] = s
This is a language extension, you need -fbang-patterns
to allow it, or with a recent ghc (6.7, 6.9 or a 6.8 rc)
a {-# LANGUAGE BangPatterns #-} pragma, or -XBangPatterns.
A fourth possibility, which is Haskell 98 again, is to declare an
auxiliary data type with a strict field:
data Strict a = Strict !a
mysum''' xs = aux (Strict 0) xs
where
aux (Strict s) (x:xs) = aux (Strict (s+x)) xs
aux (Strict s) [] = s
Hope that helps,
Bertram
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Puzzled by error with forall quantifier.
Can anyone explain the following error message from Hug98 (with extensions enabled)? I have class Space t class Space t = HasY v t where assignY :: v - t - t getY :: t - v varY :: forall w . Space w = v - (t-t) - (w-w) I get an error on the last definition quantifier does not mention type variable v (and if I quantify v, then it complains that t is not quantified). The idea I'm trying to express is that for any instance of HasY v t there should be a function varY with type v - (t-t) - (w-w) for some type w of class Space. Any help much appreciated. Is there any kind of tutorial introduction to forall out there? Cheers, Theo Norvell ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Puzzled by error with forall quantifier.
hello, just skip the forall. free type variables are implicitly forall-quantified. the forall keyword is used for functions that need to take polymorphic functions as arguments, but that's advanced stuff. so in short, this should work: class Space t class Space t = HasY v t where assignY :: v - t - t getY :: t - v varY :: Space w = v - (t-t) - (w-w) the next problem you are likely to run into is ambiguities, and you might want to take a look at functional dependencies. hope this helps iavor Theodore S. Norvell wrote: Can anyone explain the following error message from Hug98 (with extensions enabled)? I have class Space t class Space t = HasY v t where assignY :: v - t - t getY :: t - v varY :: forall w . Space w = v - (t-t) - (w-w) I get an error on the last definition quantifier does not mention type variable v (and if I quantify v, then it complains that t is not quantified). The idea I'm trying to express is that for any instance of HasY v t there should be a function varY with type v - (t-t) - (w-w) for some type w of class Space. Any help much appreciated. Is there any kind of tutorial introduction to forall out there? Cheers, Theo Norvell ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe -- == | Iavor S. Diatchki, Ph.D. student | | Department of Computer Science and Engineering | | School of OGI at OHSU | | http://www.cse.ogi.edu/~diatchki | == ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Puzzled by error with forall quantifier.
Iavor S. Diatchki wrote: just skip the forall. free type variables are implicitly forall-quantified. Of course! Thanks. The problem is that I actually wanted exists. However as the type that exists is functionally dependent on other the parameters to the class I think I can deal with it using functional dependencies, as you suggest. Sorry for the elementary question. Cheers, Theo Norvell ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
