[Haskell-cafe] parallel package, rts ROOT vs WEAK policy and reachable sparks
ruben.astud at gmail.com
Wed May 17 05:40:16 UTC 2017
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
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
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?
More information about the Haskell-Cafe