Scala 并行集合和可变状态

Question

我有一个函数，它通过更新映射来执行一个计算步骤(底层是一个可变的 HashMap)。我想并行执行其中的几个计算(每个“链”都在自己的可变 HashMap 上工作)。

我通过将 HashMaps 放入并行集合并将函数应用于每个 HashMap 来做到这一点，使用 map。

现在我遇到了 map 中缺少条目的情况。调试时，一旦异常断点停止程序，映射就会包含条目(然后通过丢弃一些堆栈帧层来提前重新启动计算)。

当我使用顺序集合时，这种行为消失了。那么是否有可能存在一些不当行为(或错误)，这是由在不同线程中处理相同的 HashMap 引起的？

我没有发布代码示例，因为我认为这种行为是不可重现的。据我所知，唯一的可变数据包含在那些 HashMap 中，它们保存了计算的状态。

应要求提供我的代码示例，其中创建了并行映射 ( reset ) 和修改了 ( step )。

class ParallelInferer[V <: DiscreteVariable, TInf <: InferenceAlgorithm[V]](val numChains: Int,
                                              val inferer: InferenceAlgorithm[V],
                                              val random: Random) {
  //tuples of inferer state and the according random number generator
  protected var states: ParSeq[(inferer.Repr,Random)] = _
  protected var steps = 0

  reset()

  def reset() {
    steps = 0

    val seed = random.nextInt()

    //todo why does parallelizing fail here (key not found on a map)
    states = (1 to numChains).par
      .map(n => new Random(seed + n))    //create the rngs
      .map(rng => (inferer.createInitialState(rng),rng))
  }

  def step() {
    //advance every chain by one
    states = states.map{case (repr, rng) => (inferer.computeStep(repr, rng),rng)}
    steps = steps + 1
  }
}

代码说明
ParallelInferer class 旨在(也)用于不可变推理。因此，可变性在发布的代码中不是直接可见的，但我认为这是显示的重要部分。

每个推理算法都有一个状态的概念，这个状态的类型是 InferenceAlgorithm#Repr - 在 inferer.Repr 的用法中很明显作为 states 的一部分多变的。推断器通过映射 Repr 来工作(和一个 Random 对象)到一个新的 Repr与他们的 computeStep功能。这可以在 def step() 中看到.现在一些推断器使用可变 HashMap作为他们国家的一部分。他们的 computeStep方法在改变它之后返回它作为参数获得的相同映射。

题

我可以以某种方式修复这种行为吗？

我是否滥用并行集合，应该并行化我的任务差异？

编辑

我刚刚再次运行了并行化版本，我认为它也会导致算法不会终止，尽管它在顺序运行时会终止。嗯，这并不令人惊讶，不是吗？

有人可以推测为什么会发生这种情况吗？

Answer 1

是的，一点没错。默认情况下，可变 HashMap 不是线程安全的，以这种方式使用它们会导致未定义的行为。缺少条目实际上是一种相当良性的表现。根据底层实现，也有可能破坏 HashMap 数据结构，使您的程序进入无限循环。

有很多方法可以解决这个问题，这将具有不同的编码复杂性和性能权衡。最简单的方法是使用同步哈希映射而不是非同步哈希映射。

import scala.collection.mutable._

val map = new HashMap[Key, Value] with SynchronizedMap[Key, Value] 

我不会说根本问题是您错误地使用了并行集合，而是任何使用可变数据结构的并行程序都会遇到这样的问题。一种更加 Scala 风格的方法是使用不可变映射，并让您的并行处理步骤返回新的不可变映射。这听起来在计算上很昂贵，但不一定，因为不可变哈希映射的底层实现。