suboptimal ghc code generation in IO vs equivalent pure code case

[Simon Peyton Jones]

As Harendra has found, the biggest difference is probably that the IO version is necessarily strict, constructing the entire list (via the stack) before it returns, whereas the pure one is lazy, constructing the list only on demand. So the memory footprint of the lazy one will be asymptotically smaller (constant instead of linear in the list size).

Simon

From: Glasgow-haskell-users [mailto:glasgow-haskell-users-bounces at haskell.org] On Behalf Of Harendra Kumar
Sent: 14 May 2016 22:18
To: David Feuer <david.feuer at gmail.com>
Cc: GHC users <glasgow-haskell-users at haskell.org>
Subject: Re: suboptimal ghc code generation in IO vs equivalent pure code case

I have stared at the cmm and assembly quite a bit. Indeed there is no trace of a token in cmm and assembly as expected. Here is what is happening.

In the IO case the entire original list is evaluated and unfolded on the stack first. During the recursion, the stack will have as many closure pointers as the size of the list, last element of the list being on top of the stack. When we finish recursing the original list, the stack unwinds and we start creating the closures for the new list in the reverse order. This is all pretty evident from the cmm dump output.

This process retains a lot of heap and stack memory (proportional to the size of the list) which will require the GC to do a lot of walking, fixing and copying. I guess that's where the additional cost is coming from. When the list size increases this cost increases nonlinearly. That explains why at lower list sizes the IO version performs not just equal to but a tad better than the pure version because if GC overhead is not considered this code is in fact more efficient.

-harendra

On 15 May 2016 at 01:56, David Feuer <david.feuer at gmail.com<mailto:david.feuer at gmail.com>> wrote:

The state token is zero-width and should therefore be erased altogether in code generation.
On May 14, 2016 4:21 PM, "Tyson Whitehead" <twhitehead at gmail.com<mailto:twhitehead at gmail.com>> wrote:
On 14/05/16 02:31 PM, Harendra Kumar wrote:
The difference seems to be entirely due to memory pressure. At list size 1000 both pure version and IO version perform equally. But as the size of the list increases the pure version scales linearly while the IO version degrades exponentially. Here are the execution times per list element in ns as the list size increases:

Size of list  Pure       IO
1000           8.7          8.3
10000         8.7          18
100000       8.8          63
1000000     9.3          786

This seems to be due to increased GC activity in the IO case. The GC stats for list size 1 million are:

IO case:       %GC     time      66.1%  (61.1% elapsed)
Pure case:   %GC     time       2.6%  (3.3% elapsed)

Not sure if there is a way to write this code in IO monad which can reduce this overhead.

Something to be aware of is that GHC currently can't pass multiple return values in registers (that may not be a 100% accurate statement, but a reasonable high level summary, see ticket for details)

https://ghc.haskell.org/trac/ghc/ticket/2289

This can bite you with with the IO monad as having to pass around the world state token turns single return values into multiple return values (i.e., the new state token plus the returned value).

I haven't actually dug into your code to see if this is part of the problem, but figured I would mention it.

Cheers!  -Tyson
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users at haskell.org<mailto:Glasgow-haskell-users at haskell.org>
http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users<https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fmail.haskell.org%2fcgi-bin%2fmailman%2flistinfo%2fglasgow-haskell-users&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7cd6315a7cc7034672b7a008d37c3d4709%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=Zy2n6Lkhaqb4ZIty4bf20UhMYcOxqa61yeaolDebuZI%3d>

_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users at haskell.org<mailto:Glasgow-haskell-users at haskell.org>
http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users<https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fmail.haskell.org%2fcgi-bin%2fmailman%2flistinfo%2fglasgow-haskell-users&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7cd6315a7cc7034672b7a008d37c3d4709%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=Zy2n6Lkhaqb4ZIty4bf20UhMYcOxqa61yeaolDebuZI%3d>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/glasgow-haskell-users/attachments/20160516/238e9670/attachment-0001.html>