parallel package, rts ROOT vs WEAK policy and reachable sparks

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

parallel package, rts ROOT vs WEAK policy and reachable sparks

Ruben Astudillo
Dear list

This mail is long, but only the 3 last paragraphs are questions, the
rest is context. Recently started reading the history of the parallel
package. On the changelog of version 2.2 says (I quote)

    "This module has been rewritten in version 2. The main change is to
    the 'Strategy a' type synonym, which was previously a -> Done and is
    now a -> Eval a. This change helps to fix the space leak described
    in "Runtime Support for Multicore Haskell". The problem is that the
    runtime will currently retain the memory referenced by all sparks,
    until they are evaluated. Hence, we must arrange to evaluate all the
    sparks eventually, just in case they aren't evaluated in parallel,
    so that they don't cause a space leak. This is why we must return a
    "new" value after applying a Strategy, so that the application can
    evaluate each spark created by the Strategy."

I know where are currently on version 3.3. Yet I decided to research a
little more on the paper cited. On it is discussed the issue of policy
for when to GC sparks. Around page 7 of the paper (I quote)

    ROOT: Treat (non-fizzled) sparks as roots for the garbage col-
    lector. That is, retain all such sparks and the graph they point to.

    WEAK: Only retain (non-fizzled) sparks that are reachable from the
    roots of the program.

    The problem is, neither of these policies is satisfactory. WEAK
    seems attractive, because it lets us discard sparks that are no
    longer required by the program. However, the WEAK policy is
    completely incompatible with strategies. Consider the parList
    strategy:

        parList :: Strategy a -> Strategy [a]
        parList strat []     = done
        parList strat (x:xs) = strat x ‘par‘ parList strat xs

    Each spark generated by parList is a thunk for the expression “
    strat x ”; this thunk is not shared, since it is created uniquely
    for the purposes of creating the spark, and hence can never fizzle.
    Hence, the WEAK policy will discard all sparks created by parList
    , which is obviously undesirable(*).

Question 1: Under WEAK policy, On (*) I understand the sparks cannot be
fizzle'd, but how are the parList spark not reachable from the roots of
the program? surely this function doesn't exist on its own. Somewhere in
the program I must be a function that is executed that has an

    let val = ... `using` parList ...
    in ... val ...

which would make the sparks reachable. Making it a *good* policy to
have IMHO. This probably has to do with my understanding of reachable
sparks.

Question 2: The ROOT policy is discuted to be better, because it
supports parList (and old parallel library versions). Yet, the old docs
of parallel recomend to that "if you are gonna spark, make sure you use
the result to avoid space leaks" ie filter you data before and only
spark on that. Is this intuition correct?

Question 3: What is the current situation of this? have weak pointers
helped in this regard?

-- Ruben
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: parallel package, rts ROOT vs WEAK policy and reachable sparks

Li-yao Xia-2
Hi Ruben,

Question 1: In your example, the sparks produced by parList are in fact
not reachable. Note that as long as you don't evaluate val, there are no
sparks at all: the expression (myList `using` parList strat) remains a
thunk. Once you evaluate it, (strat x) is sparked for each element x,
but no other reference to them is kept, since a strategy returns a unit.

Question 2: If you can "filter" the values that you will actually need
without evaluating them, that would be the right idea.

Question 3: Take a look at the other paper linked in the docs

Seq no More: Better Strategies for Parallel Haskell
http://community.haskell.org/~simonmar/papers/strategies.pdf

It describes the approach taken since version 2 which solves this issue
of garbage collecting sparks. It also goes in a bit more detail about
the problems with the original approach at the start of section 3.

Regards,
Li-yao


On 05/17/2017 01:40 AM, Ruben Astudillo wrote:

> Dear list
>
> This mail is long, but only the 3 last paragraphs are questions, the
> rest is context. Recently started reading the history of the parallel
> package. On the changelog of version 2.2 says (I quote)
>
>      "This module has been rewritten in version 2. The main change is to
>      the 'Strategy a' type synonym, which was previously a -> Done and is
>      now a -> Eval a. This change helps to fix the space leak described
>      in "Runtime Support for Multicore Haskell". The problem is that the
>      runtime will currently retain the memory referenced by all sparks,
>      until they are evaluated. Hence, we must arrange to evaluate all the
>      sparks eventually, just in case they aren't evaluated in parallel,
>      so that they don't cause a space leak. This is why we must return a
>      "new" value after applying a Strategy, so that the application can
>      evaluate each spark created by the Strategy."
>
> I know where are currently on version 3.3. Yet I decided to research a
> little more on the paper cited. On it is discussed the issue of policy
> for when to GC sparks. Around page 7 of the paper (I quote)
>
>      ROOT: Treat (non-fizzled) sparks as roots for the garbage col-
>      lector. That is, retain all such sparks and the graph they point to.
>
>      WEAK: Only retain (non-fizzled) sparks that are reachable from the
>      roots of the program.
>
>      The problem is, neither of these policies is satisfactory. WEAK
>      seems attractive, because it lets us discard sparks that are no
>      longer required by the program. However, the WEAK policy is
>      completely incompatible with strategies. Consider the parList
>      strategy:
>
>          parList :: Strategy a -> Strategy [a]
>          parList strat []     = done
>          parList strat (x:xs) = strat x ‘par‘ parList strat xs
>
>      Each spark generated by parList is a thunk for the expression “
>      strat x ”; this thunk is not shared, since it is created uniquely
>      for the purposes of creating the spark, and hence can never fizzle.
>      Hence, the WEAK policy will discard all sparks created by parList
>      , which is obviously undesirable(*).
>
> Question 1: Under WEAK policy, On (*) I understand the sparks cannot be
> fizzle'd, but how are the parList spark not reachable from the roots of
> the program? surely this function doesn't exist on its own. Somewhere in
> the program I must be a function that is executed that has an
>
>      let val = ... `using` parList ...
>      in ... val ...
>
> which would make the sparks reachable. Making it a *good* policy to
> have IMHO. This probably has to do with my understanding of reachable
> sparks.
>
> Question 2: The ROOT policy is discuted to be better, because it
> supports parList (and old parallel library versions). Yet, the old docs
> of parallel recomend to that "if you are gonna spark, make sure you use
> the result to avoid space leaks" ie filter you data before and only
> spark on that. Is this intuition correct?
>
> Question 3: What is the current situation of this? have weak pointers
> helped in this regard?
>
> -- Ruben
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.