Joachim Breitner | 7 Jan 13:06 2013
Picon

Example programs with ample use of deepseq?

Dear Haskellers,

I’m wondering if the use of deepseq to avoid unwanted lazyness might be
a too large hammer in some use cases. Therefore, I’m looking for real
world programs with ample use of deepseq, and ideally easy ways to test
performance (so preferably no GUI applications).

I’ll try to find out, by runtime observerations, which of the calls ot
deepseq could be replaced by id, seq, or „shallow seqs“ that, for
example, calls seq on the elements of a tuple.

Thanks,
Joachim

--

-- 
Joachim "nomeata" Breitner
  mail <at> joachim-breitner.de  |  nomeata <at> debian.org  |  GPG: 0x4743206C
  xmpp: nomeata <at> joachim-breitner.de | http://www.joachim-breitner.de/

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Edward Z. Yang | 7 Jan 13:20 2013
Picon

Re: Example programs with ample use of deepseq?

There are two senses in which deepseq can be overkill:

1. The structure was already strict, and deepseq just forces another
no-op traversal of the entire structure.  This hypothetically affects
seq too, although seq is quite cheap so it's not a problem.

2. deepseq evaluates too much, when it was actually sufficient only to
force parts of the structure, e.g. the spine of a list.  This is less
common for the common use-cases of deepseq; e.g. if I want to force pending
exceptions I am usually interested in all exceptions in a (finite) data
structure; a space leak may be due to an errant closure---if I don't
know which it is, deepseq will force all of them, ditto with work in
parallel programs.  Certainly there will be cases where you will want snip
evaluation at some point, but that is somewhat difficult to encode
as a typeclass, since the criterion varies from structure to structure.
(Though, perhaps, this structure would be useful:

data Indirection a = Indirection a
class DeepSeq Indirection
    rnf _ = ()
)

Cheers,
Edward

Excerpts from Joachim Breitner's message of Mon Jan 07 04:06:35 -0800 2013:
> Dear Haskellers,
> 
> I’m wondering if the use of deepseq to avoid unwanted lazyness might be
> a too large hammer in some use cases. Therefore, I’m looking for real
(Continue reading)

Joachim Breitner | 7 Jan 16:59 2013
Picon

Re: Example programs with ample use of deepseq?

Hi,
Am Montag, den 07.01.2013, 13:06 +0100 schrieb Joachim Breitner:
> I’m wondering if the use of deepseq to avoid unwanted lazyness might be
> a too large hammer in some use cases. Therefore, I’m looking for real
> world programs with ample use of deepseq, and ideally easy ways to test
> performance (so preferably no GUI applications).

surprisingly, deepseq is not used as much as I thought.
http://packdeps.haskellers.com/reverse/deepseq lists a lot of packages,
but (after grepping through some of the code) most just define NFData
instances and/or use it in tests, but rarely in the „real“ code. For
some reason I expected it to be in more widespread use.

But therefore I am even more interested in non-hackaged applications
that I can be allowed to stud – in return I might be able to tell you
way to speed up your application.

Greetings,
Joachim

--

-- 
Joachim "nomeata" Breitner
  mail <at> joachim-breitner.de  |  nomeata <at> debian.org  |  GPG: 0x4743206C
  xmpp: nomeata <at> joachim-breitner.de | http://www.joachim-breitner.de/

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
(Continue reading)

Johannes Waldmann | 8 Jan 15:23 2013
Picon

Re: Example programs with ample use of deepseq?

http://article.gmane.org/gmane.comp.lang.haskell.parallel/340

(with follow-up message about rseq => rdeepseq)

- J.W.
Evan Laforge | 8 Jan 22:01 2013
Picon

Re: Example programs with ample use of deepseq?

> surprisingly, deepseq is not used as much as I thought.
> http://packdeps.haskellers.com/reverse/deepseq lists a lot of packages,
> but (after grepping through some of the code) most just define NFData
> instances and/or use it in tests, but rarely in the „real“ code. For
> some reason I expected it to be in more widespread use.

I've been using deepseq quite a bit lately, but for the purpose of
debugging space leaks.  If, when I deepseq a big structure, the space
leak goes away, I can then apply it to some subset.  After much
trial-and-error I can find something which is insufficiently strict.
Ideally I can then strictify that one thing and stop using the
deepseq.  I wish there was a more efficient way to do this.

I also use it to explicitly force certain parts of a data structure so
they evaluate in parallel, though that part is not actually done yet.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Joachim Breitner | 8 Jan 22:54 2013
Picon

Re: Example programs with ample use of deepseq?

Hi,

Am Dienstag, den 08.01.2013, 13:01 -0800 schrieb Evan Laforge:
> > surprisingly, deepseq is not used as much as I thought.
> > http://packdeps.haskellers.com/reverse/deepseq lists a lot of packages,
> > but (after grepping through some of the code) most just define NFData
> > instances and/or use it in tests, but rarely in the „real“ code. For
> > some reason I expected it to be in more widespread use.
> 
> I've been using deepseq quite a bit lately, but for the purpose of
> debugging space leaks.  If, when I deepseq a big structure, the space
> leak goes away, I can then apply it to some subset.  After much
> trial-and-error I can find something which is insufficiently strict.
> Ideally I can then strictify that one thing and stop using the
> deepseq.  I wish there was a more efficient way to do this.

this is also a possible application of my approach, by providing a „I
want this data structure to be fully evaluated now, please tell me how
it currently looks, i.e. where in the data structure still thunks lie
hidden.“

Do you have a nice, striking example where using your approach (using
deepseq and comparing efficiency) you could make a difference, and where
a tool as described above would make the analysis much easier?

Thanks,
Joachim

--

-- 
Joachim Breitner
(Continue reading)

Erik Hesselink | 9 Jan 14:23 2013
Picon

Re: Example programs with ample use of deepseq?

On Tue, Jan 8, 2013 at 10:54 PM, Joachim Breitner
<mail <at> joachim-breitner.de> wrote:
> Am Dienstag, den 08.01.2013, 13:01 -0800 schrieb Evan Laforge:
>> > surprisingly, deepseq is not used as much as I thought.
>> > http://packdeps.haskellers.com/reverse/deepseq lists a lot of packages,
>> > but (after grepping through some of the code) most just define NFData
>> > instances and/or use it in tests, but rarely in the „real“ code. For
>> > some reason I expected it to be in more widespread use.
>>
>> I've been using deepseq quite a bit lately, but for the purpose of
>> debugging space leaks.  If, when I deepseq a big structure, the space
>> leak goes away, I can then apply it to some subset.  After much
>> trial-and-error I can find something which is insufficiently strict.
>> Ideally I can then strictify that one thing and stop using the
>> deepseq.  I wish there was a more efficient way to do this.
>
> this is also a possible application of my approach, by providing a „I
> want this data structure to be fully evaluated now, please tell me how
> it currently looks, i.e. where in the data structure still thunks lie
> hidden.“
>
> Do you have a nice, striking example where using your approach (using
> deepseq and comparing efficiency) you could make a difference, and where
> a tool as described above would make the analysis much easier?

We've also used this approach to debug space-leaks, and would have
loved such a tool. We used deepseq, and compared the heap profiles. We
finally found the leaks this way, and fixed them using strictness
annotations. Finally, we verified by running deepseq again at top
level and observing that it didn't change anything anymore.
(Continue reading)

Joachim Breitner | 9 Jan 14:40 2013
Picon

Re: Example programs with ample use of deepseq?

Hi Erik,

Am Mittwoch, den 09.01.2013, 14:23 +0100 schrieb Erik Hesselink:
> We've also used this approach to debug space-leaks, and would have
> loved such a tool. We used deepseq, and compared the heap profiles. We
> finally found the leaks this way, and fixed them using strictness
> annotations. Finally, we verified by running deepseq again at top
> level and observing that it didn't change anything anymore.

same question to you: Would you have a suitable test case that can be
used to test and demonstrate the usefulness of such tools?

Greetings,
Joachim

--

-- 
Joachim "nomeata" Breitner
  mail <at> joachim-breitner.de  |  nomeata <at> debian.org  |  GPG: 0x4743206C
  xmpp: nomeata <at> joachim-breitner.de | http://www.joachim-breitner.de/

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Erik Hesselink | 9 Jan 15:11 2013
Picon

Re: Example programs with ample use of deepseq?

On Wed, Jan 9, 2013 at 2:40 PM, Joachim Breitner
<mail <at> joachim-breitner.de> wrote:
> Hi Erik,
>
> Am Mittwoch, den 09.01.2013, 14:23 +0100 schrieb Erik Hesselink:
>> We've also used this approach to debug space-leaks, and would have
>> loved such a tool. We used deepseq, and compared the heap profiles. We
>> finally found the leaks this way, and fixed them using strictness
>> annotations. Finally, we verified by running deepseq again at top
>> level and observing that it didn't change anything anymore.
>
> same question to you: Would you have a suitable test case that can be
> used to test and demonstrate the usefulness of such tools?

Sadly, no. This is a private, core part of our application that I
cannot share. I can describe what we did, and also the structure of
the data in broad terms: we have several Maps, where the keys are
usually Text, and the values are custom data types. These contain keys
into these maps again. The whole thing defines a graph with several
indexes into it. We finally solved the problems by completely moving
to strict map operations, strict MVar/TVar operations, and strict data
types.

If you have more questions, or tools you want to test, I'd be happy to
help, though.

Regards,

Erik
(Continue reading)

Joachim Breitner | 9 Jan 23:38 2013
Picon

Re: Example programs with ample use of deepseq?

Hi,

Am Mittwoch, den 09.01.2013, 15:11 +0100 schrieb Erik Hesselink:
> We finally solved the problems by completely moving
> to strict map operations, strict MVar/TVar operations, and strict data
> types.

do you mean strict by policy (i.e. before storing something in a
[MT]Var, you ensure it is evaluated) or by construction (by `seq` or
`deepseq`’ing everything before it is stored)? In the latter case: Seq
or deeqseq? Again in the latter case: Do you worry about the performance
of repeatedly deepseq’ing an already deepseq’ed and possibly large
value?

You are not the first user of Haskell who ends up with that approach to
lazy evaluation. I’m not sure what that means for Haskell, though.

Greetings,
Joachim

--

-- 
Joachim "nomeata" Breitner
  mail <at> joachim-breitner.de  |  nomeata <at> debian.org  |  GPG: 0x4743206C
  xmpp: nomeata <at> joachim-breitner.de | http://www.joachim-breitner.de/

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
(Continue reading)

Erik Hesselink | 11 Jan 10:34 2013
Picon

Re: Example programs with ample use of deepseq?

On Wed, Jan 9, 2013 at 11:38 PM, Joachim Breitner
<mail <at> joachim-breitner.de> wrote:
> Am Mittwoch, den 09.01.2013, 15:11 +0100 schrieb Erik Hesselink:
>> We finally solved the problems by completely moving
>> to strict map operations, strict MVar/TVar operations, and strict data
>> types.
>
> do you mean strict by policy (i.e. before storing something in a
> [MT]Var, you ensure it is evaluated) or by construction (by `seq` or
> `deepseq`’ing everything before it is stored)? In the latter case: Seq
> or deeqseq? Again in the latter case: Do you worry about the performance
> of repeatedly deepseq’ing an already deepseq’ed and possibly large
> value?

Strict by construction: we `seq` when storing in a var. This is
similar to the primed functions in some places, and the new
Data.Map.Strict. So repeatedly deepseq'ing isn't a problem: deepseq in
our case is only used for debugging.

> You are not the first user of Haskell who ends up with that approach to
> lazy evaluation. I’m not sure what that means for Haskell, though.

Well, we still use the 'normal' lazy approach in most places. Only
where we have persistent shared state do we use the above approach of
making everything strict. This means updaters pay the computational
price, not readers, which seems like a sane idea.

Regards,

Erik
(Continue reading)

Johan Tibell | 7 Jan 17:12 2013
Picon

Re: Example programs with ample use of deepseq?

On Mon, Jan 7, 2013 at 4:06 AM, Joachim Breitner
<mail <at> joachim-breitner.de> wrote:
> I’m wondering if the use of deepseq to avoid unwanted lazyness might be
> a too large hammer in some use cases. Therefore, I’m looking for real
> world programs with ample use of deepseq, and ideally easy ways to test
> performance (so preferably no GUI applications).

I never use deepseq, except when setting up benchmark data where it's
a convenient way to make sure that the data is evaluated before the
benchmark is run.

When removing space leaks you want to avoid creating the thunks in the
first place, not remove them after the fact. Consider a leak caused by
a list of N thunks. Even if you deepseq that list to eventually remove
those thunks, you won't lower your peak memory usage if the list was
materialized at some point.

In addition, by not creating the thunks in the first place you avoid
some allocation costs.

-- Johan
Ertugrul Söylemez | 8 Jan 15:39 2013
Picon

Re: Example programs with ample use of deepseq?

Joachim Breitner <mail <at> joachim-breitner.de> wrote:

> I’m wondering if the use of deepseq to avoid unwanted lazyness might
> be a too large hammer in some use cases. Therefore, I’m looking for
> real world programs with ample use of deepseq, and ideally easy ways
> to test performance (so preferably no GUI applications).
>
> I’ll try to find out, by runtime observerations, which of the calls ot
> deepseq could be replaced by id, seq, or „shallow seqs“ that, for
> example, calls seq on the elements of a tuple.

Now that you know when /not/ to use deepseq, let me tell you when it's
appropriate: parallelization via parallel strategies.  It's not exactly
necessary to use deepseq (or rdeepseq in this case), but it's often very
easy to express your algorithms in the usual way and then just change
some of the 'map' applications to 'parMap rdeepseq'.

When your algorithm is written with parallelization in mind this often
gives you an amazingly parallel program by changing only a few words in
your source code.

Greets,
Ertugrul

--

-- 
Not to be or to be and (not to be or to be and (not to be or to be and
(not to be or to be and ... that is the list monad.
_______________________________________________
(Continue reading)


Gmane