[Haskell-cafe] parallel package, rts ROOT vs WEAK policy and reachable sparks

[Li-yao Xia]

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.