28

Scala 2.9 introduced parallel collections. They are a really great tool for certain tasks. However, how do they work internally and am I able to influence the behavior/configuration?

What method do they use to figure out the optimal number of threads? If I am not satisfied with the result are there any configuration parameters to adjust?

I'm not only interested how many threads are actually created, I am also interested in the way how the actual work is distributed amongst them. How the results are collected and how much magic is going on behind the scenes. Does Scala somehow test if a collection is large enough to benefit from parallel processing?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Steffen
  • 8,033
  • 1
  • 28
  • 34

1 Answers1

29

Briefly, there are two orthogonal aspects to how your operations are parallelized:

  1. The extent to which your collection is split into chunks (i.e. the size of the chunks) for a parallelizable operation (such as map or filter)
  2. The number of threads to use for the underlying fork-join pool (on which the parallel tasks are executed)

For #2, this is managed by the pool itself, which discovers the "ideal" level of parallelism at runtime (see java.lang.Runtime.getRuntime.availableProcessors)

For #1, this is a separate problem and the scala parallel collections API does this via the concept of work-stealing (adaptive scheduling). That is, when a particular piece of work is done, a worker will attempt to steal work from other work-queues. If none is available, this is an indication that all of the processors are very busy and hence a bigger chunk of work should be taken.

Aleksandar Prokopec, who implemented the library gave a talk at this year's ScalaDays which will be online shortly. He also gave a great talk at ScalaDays2010 where he describes in detail how the operations are split and re-joined (there are a number of issues that are not immediately obvious and some lovely bits of cleverness in there too!).

A more comprehensive answer is available in the PDF describing the parallel collections API.

opyate
  • 5,388
  • 1
  • 37
  • 64
oxbow_lakes
  • 133,303
  • 56
  • 317
  • 449
  • Thanks for your answer! I didn't know that paper about the implementation details. I'll put it on my reading list for the next days. If I understand correctly parallel collections are implemented to be always parallel. So, if I create collections which radically differ in size, I have to judge on my own when it pays off to use a parallel over a sequential list or did I get that wrong? – Steffen Jun 13 '11 at 12:23
  • 1
    I'm pretty sure that's right. There was discussion recently over the parallelizability of usages of `List` in the compiler and measurements were taken which showed that most Lists were 1-5 elements in size. This meant that it made no sense to replace `List` in the code with `ParSeq`. – oxbow_lakes Jun 13 '11 at 14:18
  • 1
    Hmm, in that case, it would be great to have a `parIfLargerThan(N:Int)` function. It would parallelize only if the size of the collection is larger than N (at runtime) – HRJ Jun 13 '11 at 16:53
  • @oxbow_lakes It depends how long it takes one thread to process 1 element. If it's a long time, you might get a 2x speedup on a ParSeq of size 2. – arya Oct 19 '14 at 17:30