RE: how much can %alloc in profiling be trusted

10 Jul 2003

      Hi Simon, All,

By SCC'ing the code myself, it seems that most of the allocation is
coming from the SCCs dot4 and size'2 in the following:

cosine :: Vector -> Vector -> Double
cosine v1 v2 = 
  case dot v1 v2 0 of
    n | n <= 0    -> 0
      | otherwise -> n / (size v1 * size v2)
  where 
    dot [] _  n = {-# SCC "dot1" #-} n
    dot _  [] n = {-# SCC "dot2" #-} n
    dot xl@((x,xv):xs) yl@((y,yv):ys) n =
      case x `compare` y of
        EQ -> {-# SCC "dot3" #-} (dot xs ys $! (xv * yv + n))
        LT -> {-# SCC "dot4" #-} (dot xs yl n)
        GT -> {-# SCC "dot5" #-} (dot xl ys n)
    size l = sqrt $! size' l 0
    size' [] n = {-# SCC "size'1" #-} n
    size' ((_,x):xs) n = {-# SCC "size'2" #-} (size' xs $! (n + x*x))

The only reason dot4 dominates rather than dot5 is that it's called
about 30 times more frequently (by chance).  Looking at the simpl-core
from -ddump-simpl, and not knowing too much about how to read it, it
vaguely looks to me light GHC has un-tail-recursified the dot function:

(in definition of Main.$wdot)

  case GHC.Prim.<# x# y# of wild5 {
    GHC.Base.True ->
      __scc {dot4 Main}
      case Main.$wdot a3 wild1 ww of ww1 { __DEFAULT ->
        GHC.Float.D# ww1
    };

Now I know the semantics of core is a bit different than Haskell, but
this seems to no longer be tail recursive (it needs to rebox the Double#
after the recursive call).  Am I reading this correctly?

 - Hal

--
 Hal Daume III                                   | hdaume@isi.edu
 "Arrest this man, he talks in maths."           | www.isi.edu/~hdaume
...
-----Original Message-----
From: Simon Peyton-Jones 
Sent: Thursday, July 10, 2003 2:38 AM
To: Hal Daume; glasgow-haskell-users@haskell.org
Subject: RE: how much can %alloc in profiling be trusted
It should be accurate.  Hard to say more without 
investigating your program in detail.
Try -ddump-simpl (with your profiling flags) to see how your 
function looks just before code generation.
Simoin
| -----Original Message-----
| From: glasgow-haskell-users-admin@haskell.org 
[mailto:glasgow-haskell-users-admin@haskell.org]
| On Behalf Of Hal Daume
| Sent: 09 July 2003 23:17
| To: glasgow-haskell-users@haskell.org
| Subject: how much can %alloc in profiling be trusted
| 
| In my program, I get the following time/allocation information for a
| call to my cosine function:
| 
|                              individual      inherited
| COST CENTRE   no. entries  %time  %alloc  %time  %alloc
| cosine               2721  43.1   74.3    43.1   74.3
| 
| this is a shocking amount of allocation, considering the 
definition of
| the function:
| 
| cosine :: Vector -> Vector -> Double
| cosine v1 v2 =
|   case dot v1 v2 0 of
|     n | n <= 0    -> 0
|       | otherwise -> n / (size v1 * size v2)
|   where
|     dot [] _  n = n
|     dot _  [] n = n
|     dot ((x,xv):xs) ((y,yv):ys) n =
|       case x `compare` y of
|         EQ -> dot xs ys $! (xv * yv + n)
|         LT -> dot xs ((y,yv):ys) n
|         GT -> dot ((x,xv):xs) ys n
| --    size = sqrt . sum . map (square . snd)
|     size l = sqrt $! size' l 0
|     size' [] n = n
|     size' ((_,x):xs) n = size' xs $! n + x*x
| 
| where Vector = [(Int,Double)] is a sparse vector 
representation.  This
| was even higher (moderately) until I switched from the old 
to the new
| definition of size listed there.
| 
| You can't blame this on the fact that the two vectors are 
being passed
| lazily either: they're being read strictly from a file and 
even seq'd
| before being put into the list.  Specifically, we have (v0 
is passed in
| to the function from top-level):
| 
|   ... do
|     v <- readList_H h
|     return (cosine v0 v, w)
| 
| where readList_H is defined as:
| 
| readList_H h = do
|   b <- FastIO.isEOF h
|   c <- FastIO.fscanfChar h
|   if c /= ' '
|     then return []
|     else do
|       b <- FastIO.isEOF h
|       i <- FastIO.fscanfInt h
|       FastIO.fscanfChar h
|       v <- FastIO.fscanfFloat h
|       rest <- readList_H h
|       return ((force (force i,force $ floatToDouble v)) : rest)
|   where force x = x `seq` x
| 
| as far as i can tell, all the list allocation should be 
happening here.
| (the forces were not there in the beginning -- I added them 
later but it
| changed nothing.)
| 
|  - Hal
| 
| --
|  Hal Daume III                                   | hdaume@isi.edu
|  "Arrest this man, he talks in maths."           | 
www.isi.edu/~hdaume
| _______________________________________________
| Glasgow-haskell-users mailing list
| Glasgow-haskell-users@haskell.org
| http://www.haskell.org/mailman/listinfo/glasgow-haskell-users