Code review: efficiency question

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

Code review: efficiency question

Brian Hulley
Hi -
I started off writing the following piece of monadic code:

    let
          drawModal :: Control -> ManagerM ()
          drawModal c = do -- details omitted

          -- Prolog style coding...
          drawModals :: [Control] -> ManagerM ()
          drawModals [] = return ()
          drawModals (c:cs) = do
                                               drawModals cs
                                               drawModal c
    drawModals cs

then it struck me that I should have not bothered with drawModals and
instead should just have used:

    mapM_ drawModal (reverse cs)

However, while this looks more elegant, it is less efficient?
In other words, how much optimization can one assume when writing Haskell
code?
I'm trying to get a rough idea so I can decide whether to write helper
functions such as drawModals in future or whether I should always just use
the most elegant code instead.

Any ideas?

Thanks, Brian.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Code review: efficiency question

ajb@spamcop.net
G'day all.

Quoting Brian Hulley <[hidden email]>:

> Hi -
> I started off writing the following piece of monadic code:
>
>     let
>           drawModal :: Control -> ManagerM ()
>           drawModal c = do -- details omitted
>
>           -- Prolog style coding...
>           drawModals :: [Control] -> ManagerM ()
>           drawModals [] = return ()
>           drawModals (c:cs) = do
>                                                drawModals cs
>                                                drawModal c
>     drawModals cs
>
> then it struck me that I should have not bothered with drawModals and
> instead should just have used:
>
>     mapM_ drawModal (reverse cs)
>
> However, while this looks more elegant, it is less efficient?

I suspect it depends how long the list is.  The original drawModals
would probably be more efficient for small lists, because it doesn't
require creating an intermediate list.  OTOH, it may well be less
efficient for longer lists because it can't take advantage of tail
recursion.

> I'm trying to get a rough idea so I can decide whether to write helper
> functions such as drawModals in future or whether I should always just use
> the most elegant code instead.

This is a question that is independent of Haskell.  You should ALWAYS
write the most elegant code first, and only make it uglier if it's not
fast enough.

(Note: Some programs are non-Knuthian in that they do require attention
to efficiency before writing any code.  But even then, it's usually
worth putting effort into designing a good API first.  That way, you
can write the elegant code first, and if/when you have to replace it
later, the good API insulates the rest of the code from the change.)

Cheers,
Andrew Bromage
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Code review: efficiency question

Brian Hulley
[hidden email] wrote:
> I suspect it depends how long the list is.  The original drawModals
> would probably be more efficient for small lists, because it doesn't
> require creating an intermediate list.  OTOH, it may well be less
> efficient for longer lists because it can't take advantage of tail
> recursion.

Thanks for pointing this out - I'd forgotten all about the impact of having
non-tail recursion, so my original Prolog-style code was not necessarily
more efficient anyway, since it may be cheaper to allocate list elements
than to allocate activation records for recursion.

>> I'm trying to get a rough idea so I can decide whether to write
>> helper functions such as drawModals in future or whether I should
>> always just use the most elegant code instead.
>
> This is a question that is independent of Haskell. You should ALWAYS
> write the most elegant code first, and only make it uglier if it's not
> fast enough.
> [snip]

The scales have tipped in balance of the elegant mapM_ version! :-)

Thanks, Brian.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Code review: efficiency question

Evan Martin
In reply to this post by Brian Hulley
I remember reading a tutorial that pointed out that you can often
avoid explicit recusion in Haskell and instead use higher-level
operators.

For your code, I think
  drawModals = foldr (flip (>>)) (return ()) . map drawModal
works(?).

On 5/2/06, Brian Hulley <[hidden email]> wrote:

> Hi -
> I started off writing the following piece of monadic code:
>
>     let
>           drawModal :: Control -> ManagerM ()
>           drawModal c = do -- details omitted
>
>           -- Prolog style coding...
>           drawModals :: [Control] -> ManagerM ()
>           drawModals [] = return ()
>           drawModals (c:cs) = do
>                                                drawModals cs
>                                                drawModal c
>     drawModals cs
>
> then it struck me that I should have not bothered with drawModals and
> instead should just have used:
>
>     mapM_ drawModal (reverse cs)
>
> However, while this looks more elegant, it is less efficient?
> In other words, how much optimization can one assume when writing Haskell
> code?
> I'm trying to get a rough idea so I can decide whether to write helper
> functions such as drawModals in future or whether I should always just use
> the most elegant code instead.
>
> Any ideas?
>
> Thanks, Brian.
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Code review: efficiency question

Brian Hulley
Evan Martin wrote:
> I remember reading a tutorial that pointed out that you can often
> avoid explicit recusion in Haskell and instead use higher-level
> operators.
>
> For your code, I think
>   drawModals = foldr (flip (>>)) (return ()) . map drawModal
> works(?).

I think it would be foldl so that the (return()) would be nested as the
leftmost element.
Thanks for pointing out this point-free version of drawModals, although for
readability at the moment I think I still prefer just to use mapM_ drawModal
(reverse cs)

Best regards, Brian.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Code review: efficiency question

Bulat Ziganshin-2
In reply to this post by Brian Hulley
Hello Brian,

Tuesday, May 2, 2006, 3:12:48 AM, you wrote:

>           -- Prolog style coding...
>           drawModals :: [Control] -> ManagerM ()
>           drawModals [] = return ()
>           drawModals (c:cs) = do
>                                                drawModals cs
>                                                drawModal c

imho, it's typical functional style, but without using higher-level
functions

>     mapM_ drawModal (reverse cs)

> However, while this looks more elegant, it is less efficient?
> In other words, how much optimization can one assume when writing Haskell
> code?

ghc will don't translate your later code into the former one. although
in general ghc (but not other haskell compilers, afaik) is very good
in replacing one code with another faster one and in particular in
translating "list producer + list consumer" into straightforward loop

how about this solution:

reverseMapM_ f (x:xs) = do reverseMapM_ f xs; f x
reverseMapM_ f []     = return ()

or you can define `reverseMapM_` via fold, if you have better FP
skills than me :)

> I'm trying to get a rough idea so I can decide whether to write helper
> functions such as drawModals in future or whether I should always just use
> the most elegant code instead.

> Any ideas?

you will laugh, but speed of your two solutions depends on so many
factors (including size of CPU cache) that noone can say that is
better in general. although for small lists reverseMapM_ should be
faster than reverse+mapM. what will be faster - using of higher-order
function or direct recursion, i can't say, it's a really
counter-intuitive area of ghc optimizer :)

of course, i don't think that all that really matters for your program
(drawing should anyway need much more time than looping). just use
higher-level approach (that makes code simpler to write, understand
and maintain) and don't bother your mind :)


--
Best regards,
 Bulat                            mailto:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Code review: efficiency question

Brian Hulley
Bulat Ziganshin wrote:

> [ideas including reverseMapM_]
> you will laugh, but speed of your two solutions depends on so many
> factors (including size of CPU cache) that noone can say that is
> better in general. although for small lists reverseMapM_ should be
> faster than reverse+mapM. what will be faster - using of higher-order
> function or direct recursion, i can't say, it's a really
> counter-intuitive area of ghc optimizer :)
>
> of course, i don't think that all that really matters for your program
> (drawing should anyway need much more time than looping). just use
> higher-level approach (that makes code simpler to write, understand
> and maintain) and don't bother your mind :)

Hi Bulat!
Thanks for the suggestions about reverseMapM_ etc.
It seems that since the speeds of the two solutions can be relatively
faster/slower on different platforms/CPUs I might as well just use the
combination of existing functions mapM_ and reverse at the moment to get
readable code with the least amount of effort :-)

Best regards, Brian.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Code review: efficiency question

Josef Svenningsson
Brian,

You might also want to take a look at the list fusion functionality in
GHC which often can help optimize your programs when programming with
lists.
http://www.haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html#id3153234
It doesn't help in your particular program but it might be usable for
you in the future.

Cheers,

/Josef

On 5/3/06, Brian Hulley <[hidden email]> wrote:

> Bulat Ziganshin wrote:
> > [ideas including reverseMapM_]
> > you will laugh, but speed of your two solutions depends on so many
> > factors (including size of CPU cache) that noone can say that is
> > better in general. although for small lists reverseMapM_ should be
> > faster than reverse+mapM. what will be faster - using of higher-order
> > function or direct recursion, i can't say, it's a really
> > counter-intuitive area of ghc optimizer :)
> >
> > of course, i don't think that all that really matters for your program
> > (drawing should anyway need much more time than looping). just use
> > higher-level approach (that makes code simpler to write, understand
> > and maintain) and don't bother your mind :)
>
> Hi Bulat!
> Thanks for the suggestions about reverseMapM_ etc.
> It seems that since the speeds of the two solutions can be relatively
> faster/slower on different platforms/CPUs I might as well just use the
> combination of existing functions mapM_ and reverse at the moment to get
> readable code with the least amount of effort :-)
>
> Best regards, Brian.
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe