Scala Parallel Collections
Aleksandar Prokopec

Modern multiprocessor architectures offer computing resources that are not always straightforward to use. To leverage this computing power one has to adapt existing algorithms and programming approaches. Support in the software stack is necessary to easily write parallel programs.
One such support comes in the form of parallel collections. Ordinary collections perform bulk operations sequentially and use only a single processor while parallel collections deploy their work on multiple processors to increase their performance. Scala parallel collections that will be introduced in 2.8 reimplement standard collection operations while keeping compatibility with existing Scala collection framework. They also introduce new operations characteristic for parallel algorithms, and a few contracts the programmer should be aware of.
Parallel programs often require specialised data structures to be efficient. Parallel collection framework contains several novel data structures that have been recently developed. These data structures are designed to fit particularly well in the divide and conquer approach to designing parallel algorithms, while keeping good cache locality and avoiding concurrent memory writes. Another important concern is the issue of immutability - generally the notion of immutable data structures found in functional languages fits well to parallel paradigm and can provide efficient operations on data.