在Haskell中并行构建树的策略

Question

我有一个项目，正在使用Haskell构建一个决策树（Decision Tree）。

生成的决策树将具有多个互不相关的分支，因此我认为它们可以并行构造。

DecisionTree数据类型定义如下：

data DecisionTree =
    Question Filter DecisionTree DecisionTree |    
    Answer DecisionTreeResult

instance NFData DecisionTree where
    rnf (Answer dtr)            = rnf dtr
    rnf (Question fil dt1 dt2)  = rnf fil `seq` rnf dt1 `seq` rnf dt2

这里是构建树的算法部分。

constructTree :: TrainingParameters -> [Map String Value] -> Filter -> Either String DecisionTree    
constructTree trainingParameters trainingData fil =    
    if informationGain trainingData (parseFilter fil) < entropyLimit trainingParameters    
    then constructAnswer (targetVariable trainingParameters) trainingData    
    else
        Question fil <$> affirmativeTree <*> negativeTree `using` evalTraversable parEvalTree    
        where   affirmativeTree   = trainModel trainingParameters passedTData    
                negativeTree      = trainModel trainingParameters failedTData    
                passedTData       = filter (parseFilter fil) trainingData    
                failedTData       = filter (not . parseFilter fil) trainingData

parEvalTree :: Strategy DecisionTree    
parEvalTree (Question f dt1 dt2) = do    
    dt1' <- rparWith rdeepseq dt1    
    dt2' <- rparWith rdeepseq dt2    
    return $ Question f dt1' dt2'
parEvalTree ans = return ans

trainModel 递归调用 constructTree。与并行相关的代码行为：

Question fil <$> affirmativeTree <*> negativeTree `using` evalTraversable parEvalTree 

我正在使用 GHC 标志 -threaded -O2 -rtsopts -eventlog 构建这个项目，并且使用以下命令运行它： stack exec -- performance-test +RTS -A200M -N -s -l （我在一台拥有两个核心的机器上）。

但是看起来它并没有并行运行任何东西。

SPARKS: 164 (60 converted, 0 overflowed, 0 dud, 0 GC'd, 104 fizzled)

INIT    time    0.000s  (  0.009s elapsed)
MUT     time   29.041s  ( 29.249s elapsed)
GC      time    0.048s  (  0.015s elapsed)
EXIT    time    0.001s  (  0.006s elapsed)
Total   time   29.091s  ( 29.279s elapsed)

我怀疑使用 rdeepseq 和并行策略时可能存在递归调用问题。如果有经验的 Haskeller 参与讨论，那真是太好了 :)

- The Hoff

---

你能提供完整的源代码吗？比如在GitHub上？我需要对其进行调试。 - luqui

是的，存储库在这里可用： https://github.com/AxelUlmestig/decision-tree-haskell 非常感谢您提供帮助。 - The Hoff

Answer 1

我不是Haskell性能/并行性方面的专家，但我认为这里发生了几件事情。

首先，确实有这样一行代码：

Question fil <$> affirmativeTree <*> negativeTree `using` evalTraversable parEvalTree 

可以想象，这行代码的第一部分构建了一个类似于数据结构的东西。

                      +-------+
                      | Right |
                      +-------+
                          |
                    +----------+
                    | Question |
                    +----------+
                     |   |    |
   +-----------------+   |    +-----------+
   |                +----+                |
   |                |                     |
+-----+   +-------------------+   +----------------+
| fil |   |       THUNK       |   |     THUNK      |
+-----+   | (affirmativeTree) |   | (negativeTree) |
          +-------------------+   +----------------+

evalTraversable接着会看到Right并在Question上运行parEvalTree，导致两个thunk被启动以进行深度并行评估。

不幸的是，事情并不完全是这样的，我认为问题是由于额外的Either String引起的。为了评估Question行（即使只是到WHNF），如evalTraversable所必须的，我们必须弄清楚结果是一个Right decisonTree还是一个Left _。这意味着在parEvalTree能够发挥作用之前，必须将affirmativeTree和negativeTree都评估到WHNF。不幸的是，由于您代码的结构，以这种方式将任何一个树评估到WHNF都会强制执行几乎所有内容---必须强制执行过滤器选择，以查看递归constructTree调用采取哪个分支，然后其自身的递归调用trainModel也必须以同样的方式评估到WHNF。

这可以通过先分别启动affirmativeTree和negativeTree，然后只在它们完全计算后以WHNF形式查看结果来避免。可以采取以下方式：

uncurry (Question fil) <$> bisequence ((affirmativeTree, negativeTree) `using` parTuple2 rdeepseq rdeepseq)

如果您用这行代码替换原始代码并将其加载到ThreadScope中运行，您将看到并行性明显增加：活动图在某些地方短暂地超过1，并且执行在多个HEC之间跳转。不幸的是，该程序的大部分时间仍然花费在顺序执行上。

我尝试了解这个问题，我认为你的树构造代码可能有一些右偏。我添加了一些“traceMarker”和“traceEvent”，看起来过滤器的正负两侧之间经常存在相当大的不平衡，这使得并行执行效果不佳：正子树往往非常快地完成，而负子树需要很长时间，从而创建出类似于顺序执行的情况。在几种情况下，正子树非常小，导致启动计算的核心完成它，然后开始负子树，而另一个核心还没来得及唤醒就被窃取任务了。这就是ThreadScope中单个核心长时间运行的原因。你可以在图表开头看到短暂的具有相当多并行性的时期，这是第一个过滤器的负子树正在执行的时间，因为那是主要的过滤器，其负子树足够大以真正促进并行化。跟踪后面也有一些类似（但要小得多）的事件，其中创建了相当大的负树。

如果你更改上述内容并尝试找到更均匀分割数据集的过滤器，我预计你应该会看到这段代码的并行性有相当大的提高。

- Lucy Maya Menon