I have a function, that performs one step of computation by updating a map (underlying is a mutable HashMap). I want to do several of these computations in parallel (each "chain" working on its own mutable HashMap).

I did this by putting the HashMaps into a parallel collection and applying the function to each HashMap, by using map.

Now I have experienced missing entries inside the maps. When debugging, the map contains the entry once the exception breakpoint stops the program (and restarting the computation a bit earlier by discarding some layers of stack frames works then).

This behavior is gone when I am using sequential collections. So is it possible, that there is some misbehaviour (or bug), that is caused by the 开发者_开发技巧same HashMap gets worked on in different Threads?

I didn't post a code example, since I don't think the behaviour is reproducible. To the best of my knowledge, the only mutable data is contained inside those HashMaps, that hold the state of the computation.

On request a the sample of my code where the parallel map is created (reset) and modified (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
  }
}

Explanation of the code

The ParallelInferer class is intended (also) for immutable inference. So, the mutability is not directly visible inside the posted code, but I think it's the important part that is shown.

Each inference algorithm has a notion of state, this state is of type InferenceAlgorithm#Repr - as apparent in the usage of inferer.Repr as part of the states variable. The inferers work by mapping a Repr (and a Random object) to a new Repr with their computeStep function. This can be seen in def step(). Now some inferers use a mutable HashMap as part of their state. Their computeStep method returns the same map that it got as argument, after mutating it.

Question

1. Can I somehow fix this behaviour?
2. Am I misusing parallel collections and should parallelize my task differenty?

Edit

I've just run the parallelized version again, and I think it also causes the algorithm to not terminate, although it does when running sequentially. Well, not that surprising, isn't it?

Can someone speculate on why this is happening?

Yes, absolutely. Mutable HashMaps are by default not thread-safe, and using them in this manner can result in undefined behaviour. Missing entries is actually a fairly benign manifestation. Depending on the underlying implementation, it also possible to corrupt the HashMap data structure to the point where your program goes into an infinite loop.

There are a lot of ways to fix this, which will have different coding complexities and performance tradeoffs. The easiest is to just use a synchronized hash map rather than an unsynchronized one.

import scala.collection.mutable._

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

I wouldn't say the root problem is that you are using parallel collections incorrectly, but rather that any parallel program using mutable data structures is going to have issues like this. A much more Scala-ish way to do this would be to use immutable maps, and have your parallel processing steps return new immutable maps. This sounds computationally expensive, but isn't necessarily, due to the underlying implementation of immutable hash maps.