Daniel Díaz Casanueva | 24 Jan 15:31 2013
Picon

Data.Sequence and replicateM

Hi Cafe,

I was coding this morning when I suddenly found something that surprised me. It's been a short time since I am really caring about the performance of my programs. Before, I was just caring about their correctness. So I am trying different things and profiling to see differences. One difference I have found surprising is that the function f is MUCH faster and less space consuming than the function g:

import Control.Monad
import qualified Data.Sequence as Seq

type Seq = Seq.Seq

f :: Monad m => Int -> m a -> m (Seq a)
f n = fmap Seq.fromList . replicateM n

g :: Monad m => Int -> m a -> m (Seq a)
g = Seq.replicateM

Maybe is just in my test case, where the Int argument is big and the monadic action short, but it looks to me that Data.Sequence.replicateM can be faster than it is right now.

Regards,
Daniel Díaz.

--
E-mail sent by Daniel Díaz Casanueva

let f x = x in x
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Gershom Bazerman | 24 Jan 17:41 2013
Picon

Re: Data.Sequence and replicateM

On 1/24/13 9:31 AM, Daniel Díaz Casanueva wrote:

import Control.Monad
import qualified Data.Sequence as Seq

type Seq = Seq.Seq

f :: Monad m => Int -> m a -> m (Seq a)
f n = fmap Seq.fromList . replicateM n

g :: Monad m => Int -> m a -> m (Seq a)
g = Seq.replicateM

Maybe is just in my test case, where the Int argument is big and the monadic action short, but it looks to me that Data.Sequence.replicateM can be faster than it is right now.

Are you forcing the full sequence in both cases? In the former case, you'll get all the actions, but have a thunk containing the result of Seq.fromList. In the latter, you're performing the actions as you build the sequence, so the resultant sequence will be fully evaluated.

I imagine that this is the reason that the former seems faster to you.

--g
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Daniel Díaz Casanueva | 24 Jan 18:41 2013
Picon

Re: Data.Sequence and replicateM

Good point. However, I forced the result to evaluate using `deepseq` and I still got similar results.


On Thu, Jan 24, 2013 at 11:41 AM, Gershom Bazerman <gershomb <at> gmail.com> wrote:
On 1/24/13 9:31 AM, Daniel Díaz Casanueva wrote:

import Control.Monad
import qualified Data.Sequence as Seq

type Seq = Seq.Seq

f :: Monad m => Int -> m a -> m (Seq a)
f n = fmap Seq.fromList . replicateM n

g :: Monad m => Int -> m a -> m (Seq a)
g = Seq.replicateM

Maybe is just in my test case, where the Int argument is big and the monadic action short, but it looks to me that Data.Sequence.replicateM can be faster than it is right now.

Are you forcing the full sequence in both cases? In the former case, you'll get all the actions, but have a thunk containing the result of Seq.fromList. In the latter, you're performing the actions as you build the sequence, so the resultant sequence will be fully evaluated.

I imagine that this is the reason that the former seems faster to you.

--g

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




--
E-mail sent by Daniel Díaz Casanueva

let f x = x in x
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Thomas Horstmeyer | 25 Jan 13:23 2013
Picon

Re: Data.Sequence and replicateM

Hi,

isn't the correct type context for f the following?

f :: (Functor m, Monad m) => Int -> m a -> m (Seq a)

So your f really is a kind of specialization of g.

Could the reason for f performing better be list fusion? Anything 
happening inside Control.Monad.replicateM should be subject to it.

Cheers,
Thomas

Am 24.01.2013 15:31, schrieb Daniel Díaz Casanueva:
> Hi Cafe,
>
> I was coding this morning when I suddenly found something that surprised
> me. It's been a short time since I am really caring about the
> performance of my programs. Before, I was just caring about their
> correctness. So I am trying different things and profiling to see
> differences. One difference I have found surprising is that the function
> f is MUCH faster and less space consuming than the function g:
>
> import Control.Monad
> import qualified Data.Sequence as Seq
>
> type Seq = Seq.Seq
>
> f :: Monad m => Int -> m a -> m (Seq a)
> f n = fmap Seq.fromList . replicateM n
>
> g :: Monad m => Int -> m a -> m (Seq a)
> g = Seq.replicateM
>
> Maybe is just in my test case, where the Int argument is big and the
> monadic action short, but it looks to me that Data.Sequence.replicateM
> can be faster than it is right now.
>
> Regards,
> Daniel Díaz.
>
> --
> E-mail sent by Daniel Díaz Casanueva
>
> let f x = x in x
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
Daniel Díaz Casanueva | 25 Jan 15:36 2013
Picon

Re: Data.Sequence and replicateM


Yes, you're right about the type context. I always forget that Functor is not a superclass of Monad. Anyway, the `fmap` can be done only with `Monad` in the context.

About the list fusion, I'm compiling with optimizations enabled (-O2), but I do not know how it works with fusions. Is it the optimization omitting the step of creating the list? How can I know it with certainty?


On Fri, Jan 25, 2013 at 7:23 AM, Thomas Horstmeyer <horstmey <at> mathematik.uni-marburg.de> wrote:
Hi,

isn't the correct type context for f the following?

f :: (Functor m, Monad m) => Int -> m a -> m (Seq a)

So your f really is a kind of specialization of g.

Could the reason for f performing better be list fusion? Anything happening inside Control.Monad.replicateM should be subject to it.

Cheers,
Thomas


Am 24.01.2013 15:31, schrieb Daniel Díaz Casanueva:
Hi Cafe,

I was coding this morning when I suddenly found something that surprised
me. It's been a short time since I am really caring about the
performance of my programs. Before, I was just caring about their
correctness. So I am trying different things and profiling to see
differences. One difference I have found surprising is that the function
f is MUCH faster and less space consuming than the function g:

import Control.Monad
import qualified Data.Sequence as Seq

type Seq = Seq.Seq

f :: Monad m => Int -> m a -> m (Seq a)
f n = fmap Seq.fromList . replicateM n

g :: Monad m => Int -> m a -> m (Seq a)
g = Seq.replicateM

Maybe is just in my test case, where the Int argument is big and the
monadic action short, but it looks to me that Data.Sequence.replicateM
can be faster than it is right now.

Regards,
Daniel Díaz.

--
E-mail sent by Daniel Díaz Casanueva

let f x = x in x


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


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



--
E-mail sent by Daniel Díaz Casanueva

let f x = x in x
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Petr P | 25 Jan 19:37 2013
Picon

Re: Data.Sequence and replicateM

2013/1/25 Daniel Díaz Casanueva <dhelta.diaz <at> gmail.com>

Yes, you're right about the type context. I always forget that Functor is not a superclass of Monad. Anyway, the `fmap` can be done only with `Monad` in the context.


Instead of adding `Functor m` constraint you could write just

    f n = liftM Seq.fromList . replicateM n
 
Best regards,
Petr Pudlak
 
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane