Haskell code optimisation

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Haskell code optimisation

Abhishek Kumar
I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation.

------haskell code
f m n  | m==0 =n+1
           | n==0 = f  (m-1) 1
           | otherwise = f (m-1) (f m (n-1))

Thanks
Abhishek Kumar

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Haskell code optimisation

Sumit Sahrawat, Maths & Computing,
 IIT (BHU)
Graham Hutton's paper "A tutorial on the expressiveness and universality of folds", provides a good introduction to folds, and implements the Ackerman function as an example.
Folds were the first stumbling point for me when learning Haskell, and this paper helped me a lot.

On 11 December 2015 at 20:17, Abhishek Kumar <[hidden email]> wrote:
I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation.

------haskell code
f m n  | m==0 =n+1
           | n==0 = f  (m-1) 1
           | otherwise = f (m-1) (f m (n-1))

Thanks
Abhishek Kumar

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners




--
Sumit Sahrawat,

Junior - Mathematics and Computing,
Indian Institute of Technology - BHU,
Varanasi, India

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Haskell code optimisation

Kim-Ee Yeoh
Administrator
In reply to this post by Abhishek Kumar
Have you tried BangPatterns? Compiled with optimization, I get 22 secs. Here's the full program:

{-# LANGUAGE BangPatterns #-}

f :: Int -> Int -> Int
f !m !n 
   | m==0      = n+1
   | n==0      = f (m-1) 1
   | otherwise = f (m-1) (f m (n-1))

main = putStrLn (show (f 4 1))


-- Kim-Ee

On Fri, Dec 11, 2015 at 9:47 PM, Abhishek Kumar <[hidden email]> wrote:
I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation.

------haskell code
f m n  | m==0 =n+1
           | n==0 = f  (m-1) 1
           | otherwise = f (m-1) (f m (n-1))

Thanks
Abhishek Kumar

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners



_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Haskell code optimisation

Abhishek Kumar
Thanks Kim for your answer but as far as I understand strict evaluation should save in space as expression is not expanded in terms of thunks,but I can't understand time savings.Can you pls explain strict evaluation?

On Friday, December 11, 2015, Kim-Ee <[hidden email]> wrote:
Have you tried BangPatterns? Compiled with optimization, I get 22 secs. Here's the full program:

{-# LANGUAGE BangPatterns #-}

f :: Int -> Int -> Int
f !m !n 
   | m==0      = n+1
   | n==0      = f (m-1) 1
   | otherwise = f (m-1) (f m (n-1))

main = putStrLn (show (f 4 1))


-- Kim-Ee

On Fri, Dec 11, 2015 at 9:47 PM, Abhishek Kumar <<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;abhishekkmr18@gmail.com&#39;);" target="_blank">abhishekkmr18@...> wrote:
I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation.

------haskell code
f m n  | m==0 =n+1
           | n==0 = f  (m-1) 1
           | otherwise = f (m-1) (f m (n-1))

Thanks
Abhishek Kumar

_______________________________________________
Beginners mailing list
<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;Beginners@haskell.org&#39;);" target="_blank">Beginners@...
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners



_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Haskell code optimisation

Kim-Ee Yeoh
Administrator

On Sat, Dec 12, 2015 at 4:19 PM, Abhishek Kumar <[hidden email]> wrote:
Thanks Kim for your answer but as far as I understand strict evaluation should save in space as expression is not expanded in terms of thunks,but I can't understand time savings.Can you pls explain strict evaluation?

For this particular problem, start here:

https://en.wikipedia.org/wiki/Memory_hierarchy

What happens to original program that has a sprawling mass of thunks all over RAM? The CPU spends most of its time waiting on the memory bus. And that's not even going into things like disk-backed virtual mem.

-- Kim-Ee

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Haskell code optimisation

Abhishek Kumar
In reply to this post by Kim-Ee Yeoh
Compiling below code (ghc --make) still doesn't gives result on my i3 Ubuntu 64bit machine.Can u please elaborate optimisations you did?
Thanks
Abhishek

On Friday, December 11, 2015, Kim-Ee Yeoh <[hidden email]> wrote:
Have you tried BangPatterns? Compiled with optimization, I get 22 secs. Here's the full program:

{-# LANGUAGE BangPatterns #-}

f :: Int -> Int -> Int
f !m !n 
   | m==0      = n+1
   | n==0      = f (m-1) 1
   | otherwise = f (m-1) (f m (n-1))

main = putStrLn (show (f 4 1))


-- Kim-Ee

On Fri, Dec 11, 2015 at 9:47 PM, Abhishek Kumar <<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;abhishekkmr18@gmail.com&#39;);" target="_blank">abhishekkmr18@...> wrote:
I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation.

------haskell code
f m n  | m==0 =n+1
           | n==0 = f  (m-1) 1
           | otherwise = f (m-1) (f m (n-1))

Thanks
Abhishek Kumar

_______________________________________________
Beginners mailing list
<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;Beginners@haskell.org&#39;);" target="_blank">Beginners@...
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners



_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Haskell code optimisation

Dimitri DeFigueiredo
with 'ghc -O2' this takes 14 seconds on my macbook pro.

Dimitri

On 12/12/15 10:35 AM, Abhishek Kumar wrote:
Compiling below code (ghc --make) still doesn't gives result on my i3 Ubuntu 64bit machine.Can u please elaborate optimisations you did?
Thanks
Abhishek

On Friday, December 11, 2015, Kim-Ee Yeoh <[hidden email]> wrote:
Have you tried BangPatterns? Compiled with optimization, I get 22 secs. Here's the full program:

{-# LANGUAGE BangPatterns #-}

f :: Int -> Int -> Int
f !m !n 
   | m==0      = n+1
   | n==0      = f (m-1) 1
   | otherwise = f (m-1) (f m (n-1))

main = putStrLn (show (f 4 1))


-- Kim-Ee

On Fri, Dec 11, 2015 at 9:47 PM, Abhishek Kumar <<a moz-do-not-send="true" href="javascript:_e(%7B%7D,'cvml','abhishekkmr18@gmail.com');" target="_blank">[hidden email]> wrote:
I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation.

------haskell code
f m n  | m==0 =n+1
           | n==0 = f  (m-1) 1
           | otherwise = f (m-1) (f m (n-1))

Thanks
Abhishek Kumar

_______________________________________________
Beginners mailing list
<a moz-do-not-send="true" href="javascript:_e(%7B%7D,'cvml','Beginners@haskell.org');" target="_blank">Beginners@...
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners




_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Haskell code optimisation

Magnus Therning
In reply to this post by Sumit Sahrawat, Maths & Computing, IIT (BHU)

Sumit Sahrawat, Maths & Computing, IIT (BHU) writes:

> Graham Hutton's paper "A tutorial on the expressiveness and universality of
> folds", provides a good introduction to folds, and implements the Ackerman
> function as an example.
> Folds were the first stumbling point for me when learning Haskell, and this
> paper helped me a lot.

To save others from a search: http://www.cs.nott.ac.uk/~pszgmh/fold.pdf

/M

--
Magnus Therning              OpenPGP: 0x927912051716CE39
email: [hidden email]   jabber: [hidden email]
twitter: magthe               http://therning.org/magnus

Failure is not an option. It comes bundled with the software.

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

signature.asc (815 bytes) Download Attachment