On Wed, Jun 18, 2008 at 9:16 AM, Anatoly Yakovenko wrote:

C doesn't work like that :)

Yes it can. You would have to check the disassembly to be sure, but C compilers can, and do, perform dead code elimination. AGL -- Adam Langley agl@imperialviolet.org http://www.imperialviolet.org

On Wed, Jun 18, 2008 at 06:03:42PM +0100, Jules Bean wrote:

Anatoly Yakovenko wrote:

...

...

...

#include #include

int main() { int size = 1024; int ii = 0; double* v1 = malloc(sizeof(double) * (size)); double* v2 = malloc(sizeof(double) * (size)); for(ii = 0; ii < size*size; ++ii) { double _dd = cblas_ddot(0, v1, size, v2, size); } free(v1); free(v2); } Your C compiler sees that you're not using the result of cblas_ddot, so it doesn't even bother to call it. That loop never gets run. All your program does at runtime is call malloc and free twice, which is very fast :-)

C doesn't work like that :).

C compilers can do what they like ;)

GCC in particular is pretty good at removing dead code, including entire loops. However it shouldn't eliminate the call to cblas_ddot unless it thinks cblas_ddot has no side effects at all, which would be surprising unless it's inlined somehow.

Or unless it's been annotated as pure, which it should be. David

I suspect that it is your initialization that is the difference. For one thing, you've initialized the arrays to different values, and in your C code you've fused what are two separate loops in your Haskell code. So you've not only given the C compiler an easier loop to run (since you're initializing the array to a constant rather than to a sequence of numbers), but you've also manually optimized that initialization. In fact, this fusion could be precisely the factor of two. Why not see what happens in Haskell if you create just one vector and dot it with itself? (of course, that'll also make the blas call faster, so you'll need to be careful in your interpretation of your results.)

The difference cant be in the initialization. I am calling the dot product a million times, the malloc and init in both cases are insignificant. Also, "fusing" the two loops in C probably wont help, if anything having each loop run separate is likely to be faster and result in less cache misses. In this case, i am using vectors of size 10 only, and calling the loop 10 million times, haskell is far far slower, or 35 times. That's pretty crappy. $ cat htestdot.hs {-# OPTIONS_GHC -O2 -fexcess-precision -funbox-strict-fields -fglasgow-exts -fbang-patterns -lcblas#-} module Main where import Data.Vector.Dense.IO import Control.Monad main = do let size = 10 let times = 10*1000*1000 v1::IOVector Int Double <- newListVector size $ replicate size 0.1 v2::IOVector Int Double <- newListVector size $ replicate size 0.1 sum <- foldM (\ ii zz -> do rv <- v1 `getDot` v2 return $ zz + rv ) 0.0 [0..times] print $ sum $ ghc --make htestdot.hs $ time ./htestdot 1.00000001e7 real 0m17.328s user 0m17.320s sys 0m0.010 $ cat testdot.c #include #include #include #include int main() { int size = 10; int times = 10*1000*1000; int ii = 0; double dd = 0.0; double* v1 = malloc(sizeof(double) * (size)); double* v2 = malloc(sizeof(double) * (size)); for(ii = 0; ii < size; ++ii) { v1[ii] = 0.1; } for(ii = 0; ii < size; ++ii) { v2[ii] = 0.1; } for(ii = 0; ii < times; ++ii) { dd += cblas_ddot(size, v1, 1, v2, 1); } free(v1); free(v2); printf("%f\n", dd); return 0; } $ gcc -O2 testdot.c -lcblas -o testdot $ time ./testdot 999999.999839 real 0m0.491s user 0m0.480s sys 0m0.020s Just to make sure that fold isnt causing the slowdown, i reverted the haskell program to use the mapM_, i still got almost the same performance: $ cat htestdot.hs {-# OPTIONS_GHC -O2 -fexcess-precision -funbox-strict-fields -fglasgow-exts -fbang-patterns -lcblas#-} module Main where import Data.Vector.Dense.IO import Control.Monad main = do let size = 10 let times = 10*1000*1000 v1::IOVector Int Double <- newListVector size $ replicate size 0.1 v2::IOVector Int Double <- newListVector size $ replicate size 0.1 mapM_ (\ ii -> do v1 `getDot` v2) [0..times] $ ghc --make htestdot $ time ./htestdot real 0m15.660s user 0m15.630s sys 0m0.030s This is what the profiler has to say: $ cat htestdot.prof Fri Jun 27 18:06 2008 Time and Allocation Profiling Report (Final) htestdot +RTS -p -RTS total time = 22.00 secs (1100 ticks @ 20 ms) total alloc = 3,320,010,716 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc main Main 100.0 100.0 individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 1 0 0.0 0.0 100.0 100.0 main Main 222 1 93.6 88.0 93.6 88.0 CAF Main 216 5 0.0 0.0 6.4 12.0 main Main 223 0 6.4 12.0 6.4 12.0 CAF GHC.Handle 168 3 0.0 0.0 0.0 0.0

i get the same crappy performance with: $ cat htestdot.hs {-# OPTIONS_GHC -O2 -fexcess-precision -funbox-strict-fields -fglasgow-exts -fbang-patterns -lcblas#-} module Main where import Data.Vector.Dense.IO import Control.Monad main = do let size = 10 let times = 10*1000*1000 v1::IOVector Int Double <- newListVector size $ replicate size 0.1 v2::IOVector Int Double <- newListVector size $ replicate size 0.1 replicateM_ times $ v1 `getDot` v2 On Fri, Jun 27, 2008 at 7:41 PM, Dan Doel wrote:

On Friday 27 June 2008, Anatoly Yakovenko wrote:

...

$ cat htestdot.hs {-# OPTIONS_GHC -O2 -fexcess-precision -funbox-strict-fields -fglasgow-exts -fbang-patterns -lcblas#-} module Main where

import Data.Vector.Dense.IO import Control.Monad

main = do let size = 10 let times = 10*1000*1000 v1::IOVector Int Double <- newListVector size $ replicate size 0.1 v2::IOVector Int Double <- newListVector size $ replicate size 0.1 sum <- foldM (\ ii zz -> do rv <- v1 `getDot` v2 return $ zz + rv ) 0.0 [0..times] print $ sum

Hackage is down for the time being, so I can't install blas and look at the core for your program. However, there are still some reasons why this code would be slow.

For instance, a brief experiment seems to indicate that foldM is not a good consumer in the foldr/build sense, so no deforestation occurs. Your program is iterating over a 10-million element lazy list. That's going to add overhead. I wrote a simple test program which just adds 0.1 in each iteration:

---- snip ----

{-# LANGUAGE BangPatterns #-}

module Main (main) where

import Control.Monad

main = do let times = 10*1000*1000 sum <- foldM (\_ zz -> return $ zz + 0.1) 0.0 [0..times] -- sum <- foo 0 times 0.0 print $ sum

foo :: Int -> Int -> Double -> IO Double foo k m !zz | k <= m = foo (k+1) m (zz + 0.1) | otherwise = return zz

---- snip ----

With foldM, it takes 2.5 seconds on my machine. If you comment that line, and use foo instead, it takes around .1 seconds. So that's a factor of what, 250? That loop allows for a lot more unboxing, which allows much better code to be generated.

When Hackage comes back online, I'll take a look at your code, and see if I can make it run faster, but you might want to try it yourself in the time being. Strictifying the addition of the accumulator is probably a good idea, for instance.

Cheers, -- Dan

so I had a look at the code. The loops are all fine. replicateM_ isn't a problem, but getDot is decidedly non trivial. Lots of pattern matching on different vector forms, and to top it off ffi calls. With some inlining in the blas library I was able to cut a few seconds off the running time, but getDot looks to be fundamentally a bit complicated in the current implementation. I wonder if you'll get different results with hmatrix? Anyway, this is a library issue. Better take it up with Patrick. Pass on to the library author the C code, the Haskell you think should be compiled identically. -- Don aeyakovenko:

i get the same crappy performance with:

$ cat htestdot.hs {-# OPTIONS_GHC -O2 -fexcess-precision -funbox-strict-fields -fglasgow-exts -fbang-patterns -lcblas#-} module Main where

import Data.Vector.Dense.IO import Control.Monad

main = do let size = 10 let times = 10*1000*1000 v1::IOVector Int Double <- newListVector size $ replicate size 0.1 v2::IOVector Int Double <- newListVector size $ replicate size 0.1 replicateM_ times $ v1 `getDot` v2

On Fri, Jun 27, 2008 at 7:41 PM, Dan Doel wrote:

...

On Friday 27 June 2008, Anatoly Yakovenko wrote:

...

$ cat htestdot.hs {-# OPTIONS_GHC -O2 -fexcess-precision -funbox-strict-fields -fglasgow-exts -fbang-patterns -lcblas#-} module Main where

import Data.Vector.Dense.IO import Control.Monad

main = do let size = 10 let times = 10*1000*1000 v1::IOVector Int Double <- newListVector size $ replicate size 0.1 v2::IOVector Int Double <- newListVector size $ replicate size 0.1 sum <- foldM (\ ii zz -> do rv <- v1 `getDot` v2 return $ zz + rv ) 0.0 [0..times] print $ sum

Hackage is down for the time being, so I can't install blas and look at the core for your program. However, there are still some reasons why this code would be slow.

For instance, a brief experiment seems to indicate that foldM is not a good consumer in the foldr/build sense, so no deforestation occurs. Your program is iterating over a 10-million element lazy list. That's going to add overhead. I wrote a simple test program which just adds 0.1 in each iteration:

---- snip ----

{-# LANGUAGE BangPatterns #-}

module Main (main) where

import Control.Monad

main = do let times = 10*1000*1000 sum <- foldM (\_ zz -> return $ zz + 0.1) 0.0 [0..times] -- sum <- foo 0 times 0.0 print $ sum

foo :: Int -> Int -> Double -> IO Double foo k m !zz | k <= m = foo (k+1) m (zz + 0.1) | otherwise = return zz

---- snip ----

With foldM, it takes 2.5 seconds on my machine. If you comment that line, and use foo instead, it takes around .1 seconds. So that's a factor of what, 250? That loop allows for a lot more unboxing, which allows much better code to be generated.

When Hackage comes back online, I'll take a look at your code, and see if I can make it run faster, but you might want to try it yourself in the time being. Strictifying the addition of the accumulator is probably a good idea, for instance.

Cheers, -- Dan

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe