Branimir Maksimovic | 3 Dec 00:12 2012
Picon

Help optimize fannkuch program

Well, playing with Haskell I have literally trasnlated my c++ program 
http://shootout.alioth.debian.org/u64q/program.php?test=fannkuchredux&lang=gpp&id=3
and got decent performance but not that good in comparison
with c++ 
On my machine Haskell runs 52 secs while c++ 30 secs.
(There is Haskell entry that is fastest but unfortunately does not runs on 
test machine is on par with c++
)
There is something which I have missing since programs
are identical.
Aa with previous entries you gurus here helped a lot in both help
and learning experience.
I simply love Haskell ;)
I plan to contribute this program as it is much faster than current running
even if it is multithreaded and my is not.

This is program:

{-# LANGUAGE CPP, BangPatterns #-}
{-  The Computer Language Benchmarks Game

    http://shootout.alioth.debian.org/

    contributed by Branimir Maksimovic

-}

import System.Environment
import Text.Printf
import Data.Bits

import qualified Data.Vector.Unboxed.Mutable as VM
import qualified Data.Vector.Generic.Mutable as VG
import qualified Data.Vector.Unboxed as V

main = do
n <- getArgs >>= readIO.head
(checksum,maxflips) <- fannkuch n
printf "%d\nPfannkuchen(%d) = %d\n" checksum n maxflips

fannkuch n = do
!perm <-  V.unsafeThaw $ V.fromList [1..n]
!tperm <-  VG.new n
!cnt <-  VG.replicate n 0
let
loop :: Int -> Int -> Int -> IO(Int,Int)
loop !c !m !pc = do
!b <- next_permutation perm n cnt
if b == False then return (c,m) 
else do
VM.unsafeCopy tperm perm
!flips <-  count_flips tperm 0
loop (c + (if pc .&. 1 == 0 then flips else -flips))
(max m flips)
(pc+1)
r <- loop 0 0 1
return r


next_permutation :: VM.IOVector Int -> Int -> VM.IOVector Int-> IO(Bool)
next_permutation !perm !n !cnt = 
do 
!i <- loop 1
if(i >= n) 
then return False
else do
!v <- VM.unsafeRead cnt i
VM.unsafeWrite cnt i (v+1)
return True
where 
loop :: Int -> IO(Int)
loop !i 
| i < n = do
 !tmp <- VM.unsafeRead perm 0
 let 
rotate :: Int -> IO()
rotate !j = 
if j >= i
then do
VM.unsafeWrite perm i tmp
return ()
else do
!v <- VM.unsafeRead perm (j+1)
VM.unsafeWrite perm j v
rotate (j+1)
 rotate 0
 !v <- VM.unsafeRead cnt i
 if v >= i
then do
VM.unsafeWrite cnt i 0
loop (i+1)
else return i
| otherwise = return i
count_flips :: VM.IOVector Int -> Int -> IO(Int)
count_flips !tperm !flips = do
!f <- VM.unsafeRead tperm 0
if f == 1 
then
return flips
else do 
VG.reverse $ VM.unsafeSlice 0 f tperm
count_flips tperm (flips+1)



_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Bryan O'Sullivan | 3 Dec 09:01 2012

Re: Help optimize fannkuch program

On Sun, Dec 2, 2012 at 3:12 PM, Branimir Maksimovic <bmaxa <at> hotmail.com> wrote:

Well, playing with Haskell I have literally trasnlated my c++ program 
http://shootout.alioth.debian.org/u64q/program.php?test=fannkuchredux&lang=gpp&id=3
and got decent performance but not that good in comparison
with c++ 
On my machine Haskell runs 52 secs while c++ 30 secs.

Did you compile with -O2 -fllvm?

On my machine:

C++ 28 sec
Mine -O2 -fllvm 37 sec
Yours -O2 -fllvm 41 sec
Mine -O2 48 sec
Yours -O2 54 sec

My version of your Haskell code is here: http://hpaste.org/78705
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Branimir Maksimovic | 3 Dec 20:18 2012
Picon

Re: Help optimize fannkuch program

Thanks. Your version is much faster.
Yes, I have compiled with 
ghc --make -O2 -fllvm -optlo-O3 -optlo-constprop fannkuchredux4.hs
(there is bug in ghc 7.4.2 regarding llvm 3.1 > which is circumvented with constrprop)

results: 
yours:
bmaxa <at> maxa:~/shootout/fannkuchredux$ time ./fannkuchredux4 12
3968050
Pfannkuchen(12) = 65

real    0m39.200s
user    0m39.132s
sys     0m0.044s

mine:
bmaxa <at> maxa:~/shootout/fannkuchredux$ time ./fannkuchredux 12
3968050
Pfannkuchen(12) = 65

real    0m50.784s
user    0m50.660s
sys     0m0.092s

Seems that you machine is faster than mine and somewhat better for executing mine version.
Thanks ! Should I contribute your version on shootout site?


Date: Mon, 3 Dec 2012 00:01:32 -0800
Subject: Re: [Haskell-cafe] Help optimize fannkuch program
From: bos <at> serpentine.com
To: bmaxa <at> hotmail.com
CC: haskell-cafe <at> haskell.org

On Sun, Dec 2, 2012 at 3:12 PM, Branimir Maksimovic <bmaxa <at> hotmail.com> wrote:
Well, playing with Haskell I have literally trasnlated my c++ program 
http://shootout.alioth.debian.org/u64q/program.php?test=fannkuchredux&lang=gpp&id=3
and got decent performance but not that good in comparison
with c++ 
On my machine Haskell runs 52 secs while c++ 30 secs.

Did you compile with -O2 -fllvm?

On my machine:

C++ 28 sec
Mine -O2 -fllvm 37 sec
Yours -O2 -fllvm 41 sec
Mine -O2 48 sec
Yours -O2 54 sec

My version of your Haskell code is here: http://hpaste.org/78705
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Bryan O'Sullivan | 4 Dec 00:32 2012

Re: Help optimize fannkuch program

On Mon, Dec 3, 2012 at 11:18 AM, Branimir Maksimovic <bmaxa <at> hotmail.com> wrote:

Thanks ! Should I contribute your version on shootout site?

Do whatever you like with it.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Branimir Maksimovic | 9 Dec 08:00 2012
Picon

Re: Help optimize fannkuch program

Here it is :


Date: Mon, 3 Dec 2012 15:32:20 -0800
Subject: Re: [Haskell-cafe] Help optimize fannkuch program
From: bos <at> serpentine.com
To: bmaxa <at> hotmail.com
CC: haskell-cafe <at> haskell.org

On Mon, Dec 3, 2012 at 11:18 AM, Branimir Maksimovic <bmaxa <at> hotmail.com> wrote:
Thanks ! Should I contribute your version on shootout site?

Do whatever you like with it.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane