title: Efficiency/scalability of parallel collections in Scala (graphs)
body: <p>So I've been working with parallel collections in Scala for a graph project I'm working on, I've got the basics of the graph class defined, it is currently using a <code>scala.collection.mutable.HashMap</code> where the key is <code>Int</code> and the value is <code>ListBuffer[Int]</code> (adjacency list). (EDIT: This has since been change to <code>ArrayBuffer[Int]</code></p>
  
  <p>I had done a similar thing a few months ago in C++, with a <code>std::vector&lt;int, std::vector&lt;int&gt; &gt;</code>.</p>
  
  <p>What I'm trying to do now is run a metric between all pairs of vertices in the graph, so in C++ I did something like this:</p>
  
  <pre><code>// myVec = std::vector&lt;int&gt; of vertices
  for (std::vector&lt;int&gt;::iterator iter = myVec.begin(); iter != myVec.end(); ++iter) {
      for (std::vector&lt;int&gt;::iterator iter2 = myVec.begin(); 
          iter2 != myVec.end(); ++iter2) {
          /* Run algorithm between *iter and *iter2 */
      }
  }
  </code></pre>
  
  <p>I did the same thing in Scala, parallelized, (or tried to) by doing this:</p>
  
  <pre><code>// vertexList is a List[Int] (NOW CHANGED TO Array[Int] - see below)
  vertexList.par.foreach(u =&gt;
    vertexList.foreach(v =&gt;
      /* Run algorithm between u and v */
    )
  )
  </code></pre>
  
  <p>The C++ version is clearly single-threaded, the Scala version has <code>.par</code> so it's using parallel collections and is multi-threaded on 8 cores (same machine). However, the C++ version processed 305,570 pairs in a span of roughly 3 days, whereas the Scala version so far has only processed 23,573 in 17 hours.</p>
  
  <p>Assuming I did my <a href="http://www.wolframalpha.com/input/?i=%28%2850%20%2a%206115%29%20/%20%283%2a24%29%29%20/%20%2823573/17%29" rel="nofollow">math</a> correctly, the single-threaded C++ version is roughly 3x faster than the Scala version. Is Scala really that much slower than C++, or am I completely mis-using Scala (I only recently started - I'm about 300 pages into Programming in Scala)?</p>
  
  <p>Thanks!
  -kstruct</p>
  
  <p><em>EDIT</em> To use a while loop, do I do something like..</p>
  
  <pre><code>// Where vertexList is an Array[Int]
  vertexList.par.foreach(u =&gt;
    while (i &lt;- 0 until vertexList.length) {
      /* Run algorithm between u and vertexList(i) */
    }
  }
  </code></pre>
  
  <p>If you guys mean use a while loop for the entire thing, is there an equivalent of <code>.par.foreach</code> for whiles?</p>
  
  <p><em>EDIT2</em> Wait a second, that code isn't even right - my bad. How would I parallelize this using while loops? If I have some <code>var i</code> that keeps track of the iteration, then wouldn't all threads be sharing that <code>i</code>?</p>