Scala 中并行集合的效率/可扩展性（图）

因此，我一直在 Scala 中使用并行集合来处理我正在开发的图形项目，我已经定义了图形类的基础知识，它目前正在使用scala.collection.mutable.HashMap关键在哪里Int其值为ListBuffer[Int]（邻接表）。 （编辑：此后已更改为ArrayBuffer[Int]

几个月前我用 C++ 做了类似的事情，std::vector<int, std::vector<int> >.

我现在想做的是在图中的所有顶点对之间运行一个度量，所以在 C++ 中我做了这样的事情：

// myVec = std::vector<int> of vertices
for (std::vector<int>::iterator iter = myVec.begin(); iter != myVec.end(); ++iter) {
    for (std::vector<int>::iterator iter2 = myVec.begin(); 
        iter2 != myVec.end(); ++iter2) {
        /* Run algorithm between *iter and *iter2 */
    }
}

我在 Scala 中做了同样的事情，并行化，（或尝试）这样做：

// vertexList is a List[Int] (NOW CHANGED TO Array[Int] - see below)
vertexList.par.foreach(u =>
  vertexList.foreach(v =>
    /* Run algorithm between u and v */
  )
)

C++版本显然是单线程的，Scala版本有.par所以它使用并行集合，并且在 8 核（同一台机器）上是多线程的。然而，C++ 版本在大约 3 天内处理了 305,570 对，而 Scala 版本迄今为止仅在 17 小时内处理了 23,573 对。

假设我做了我的math http://www.wolframalpha.com/input/?i=%28%2850%20%2a%206115%29%20/%20%283%2a24%29%29%20/%20%2823573/17%29正确的是，单线程 C++ 版本大约比 Scala 版本快 3 倍。 Scala 真的比 C++ 慢很多吗？还是我完全误用了 Scala（我最近才开始使用 Scala，我已经读了大约 300 页的《Scala 编程》了）？

谢谢！ -kstruct

EDIT要使用 while 循环，我需要做类似的事情吗？

// Where vertexList is an Array[Int]
vertexList.par.foreach(u =>
  while (i <- 0 until vertexList.length) {
    /* Run algorithm between u and vertexList(i) */
  }
}

如果你们的意思是对整个事情使用 while 循环，是否有等效的.par.foreach一会儿？

EDIT2等一下，该代码甚至都不正确 - 我的错。我如何使用 while 循环并行化它？如果我有一些var i跟踪迭代，那么所有线程都不会共享它i?

从您的评论中，我看到您更新了共享可变HashMap在每个算法运行结束时。如果你随机散步，共享Random也是一个争论点。

我建议进行两项更改：

1. Use .map and .flatMap返回不可变集合而不是修改共享集合。
2. Use a ThreadLocalRandom（从任一Akka http://doc.akka.io/api/akka/2.0/#akka.jsr166y.ThreadLocalRandom%24 or Java 7 http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ThreadLocalRandom.html) 减少随机数生成器上的争用
3. 检查算法的其余部分以了解更多可能的争用点。
4. 您也可以尝试并行运行内部循环。但如果不了解你的算法，就很难知道这是否有帮助或有害。幸运的是，运行并行和顺序收集的所有组合非常简单；只是关掉pVertexList and vertexList在下面的代码中。

像这样的东西：

val pVertexList = vertexList.par
val allResult = for {
  u <- pVertexList
  v <- pVertexList
} yield {
  /* Run algorithm between u and v */
  ((u -> v) -> result)
}

价值allResult将是一个ParVector[((Int, Int), Int)]。您可以致电.toMap将其转换为Map.