Basics of parallel programming in Scala
Repo RodneyShag/Parallel_programming, read from GitHub 2 d ago. RodneyShag has not joined Take My Repo.
RodneyShag/Parallel_programming is a public repo on GitHub by RodneyShag. Basics of parallel programming in Scala. It declares no license on GitHub. Public does not mean open source: without a license, nobody is granted the right to reuse it. It has 10 stars and last changed on 2019-10-14. Nobody has reviewed it on Take My Repo yet, which says nothing about its quality. Read from GitHub on 2026-11-19.
In the maintainer's words. Shown from GitHub; Take My Repo does not keep a copy.
This repo is a concise summary and replacement of the Coursera: Parallel programming course. Using the hyperlinks below is optional.
Parallel computing is a type of computation in which many calculations are performed at the same time.
CPU speed-up is non-linear - The power required to speed up a CPU starts to grow non-linearly. For this reason, we add more CPUs instead of trying to speed up just 1 CPU.
Thread memory address space - Threads can be started from within the same program, and they share the same memory.
Example using threads:
class HelloThread extends Thread {
override def run() {
println("Hello world!")
}
}
val t = new HelloThread
t.start()
t.join()
Calling t.join() will block execution on the main thread until HelloThread completes
Atomicity - An operation is atomic if it appears as if it occurred instantaneously from the point of view of other threads.
the synchronized keyword is used to acheive atomicity.
Example of deadlock with 2 synchronized threads:
class Account(private var amount: Int = 0) {
def transfer(target: Account, n: Int) =
this.synchronized {
target.synchronized {
this.amount -= n
target.amount += n
}
}
}
}
def startThread(a: Account, b: Account, n: Int) = {
val t = new Thread {
override def run() {
for (i <- 0 until n) {
a.transfer(b, 1)
}
}
}
t.start()
t
}
val a1 = new Account(500000)
val a2 = new Account(700000)
val t = startThread(a1, a2, 150000)
val s = startThread(a2, a1, 150000)
t.join()
s.join()
Deadlock occurred since the Account a1 is waiting for Account a2 to release the lock, and Account a2 is waiting for Account a1 to release the lock.
This deadlock can be fixed by ensuring a lock is grabbed for the smaller account number before the larger account number.
class Account(private var amount: Int = 0) {
val uid = getUniqueUid()
private def lockAndTransfer(target: Account, n: Int) =
this.synchronized {
target.synchronized {
this.amount -= n
target.amount += n
}
}
def transfer(target: Account, n: Int) =
if (this.uid < target.uid) this.lockAndTransfer(target, n)
else target.lockAndTransfer(this, -n)
}
The parallel keyword will parallelize 2 calls. It is defined as:
def parallel[A, B](taskA: => A, taskB: => B): (A, B) = { ... }
Scala "by-name" parameters => are used to achieve lazy evaluation of A and B, so that they can be evaluated in parallel instead of when the function is initially called.
Here is a recursive algorithm for an unbounded number of threads. It calculates the p-norm for a 2-D vector:
def pNormRec(a: Array[Int], p: Double): Int =
power(segmentRec(a, p, 0, a.length), 1/p)
def segmentRec(a: Array[Int], p: Double, s: Int, t: Int) = {
if (t - s < threshold) {
sumSegment(a, p, s, t) // small segment: do it sequentially
} else {
val m = (s + t) / 2
val (sum1, sum2) = parallel(segmentRec(a, p, s, m), segmentRec(a, p, m, t))
sum1 + sum2
}
}
Here is an example of 4 threads in parallel:
val ((part1, part2), (part3, part4)) =
parallel(parallel(sumSegment(a, p, 0, mid1),
sumSegment(a, p, mid1, mid2)),
parallel(sumSegment(a, p, mid2, mid3),
sumSegment(a, p, mid3, a.length)))
power(part1 + part2 + part3 + part4, 1/p)
If we sum all integers in an array of length n, our runtime is O(n) if it's done sequentially.
Assuming enough CPUs are available for full parallelization, then the code takes "tree" form where the runtime is the same as the height of the tree: O(log(n))
sum(0 to 8)
sum(0 to 4) sum(5 to 8) // both done in parallel
sum(0 to 2) sum(3 to 4) sum(5 to 6) sum(7 to 8) // all 4 done in parallel
If we didn't have enough CPUs for full parallelization, the runtime would be O(n)
A naive approach for benchmarking is to do:
val xs = List(1, 2, 3)
val startTime = System.nanoTime
xs.reverse
println((System.nanoTime - startTime) / 1000000)
The above method can be improved by
def copy(src: Array[Int], target: Array[Int], from: Int, until: Int, depth: Int): Unit = {
if (depth == maxDepth) {
Array.copy(src, from, target, from, until - from)
} else {
val mid = (from + until) / 2
val right = parallel(
copy(src, target, mid, until, depth + 1),
copy(src, target, from, mid, depth + 1)
)
}
}
def mapASegSeq[A, B](inp: Array[A], left: Int, right: Int, f : A => B,
out: Array[B]) = {
var i = left
while (i < right) {
out(i) = f(inp(i))
i = i + 1
}
}
Testing it gives:
// Input
val in = Array(2, 3, 4, 5, 6)
val out = Array(0, 0, 0, 0, 0)
val f = (x: Int) => x * x
mapASegSeq(in, 1, 3, f, out)
out
// Output
res1: Array[Int] = Array(0, 9, 16, 0, 0)
def mapASegSeq[A, B](inp: Array[A], left: Int, right: Int, f : A => B,
out: Array[B]) = {
if (right - left < threshold) {
mapASegSeq(inp, left, right, f, out)
} else {
val mid = (left + right) / 2
parallel(mapASegPar(inp, left, mid, f, out),
mapASegPar(inp, mid, right, f, out))
}
}
def mapTreePar[A:Manifest, B:Manifest](t: Tree[A], f: A => B) : Tree[B] =
t match {
case Leaf(a) => {
val len = a.length;
val b = new Array[B](len)
var i = 0;
while (i < len) {
b(i) = f(a(i))
i = i + 1
}
Leaf(b)
}
case Node(l, r) => {
val (lb, rb) = parallel(mapTreePar(l, f), mapTreePar(r, f))
Node(lb, rb)
}
}
Subtraction is not associative, so the following results are different:
List(1, 3, 8).foldLeft(100)((s, x) => s - x) == ((100 - 1) - 3) - 8 == 88
List(1, 3, 8).foldRight(100)((s, x) => s - x) == 1 - (3 - (8 - 100)) == -94
List(1, 3, 8).reduceLeft(100)((s, x) => s - x) == (1 - 3) - 8 == -10
List(1, 3, 8).reduceRight(100)((s, x) => s - x) == 1 - (3 - 8) == 6
def reduce[A](t: Tree[A], f : (A, A) => A): A = t match {
case Leaf(v) => v
case Node(l, r) => f(reduce[A](l, f), reduce[A](r, f))
}
def reduce[A](t: Tree[A], f : (A, A) => A): A = t match {
case Leaf(v) => v
case Node(l, r) =>} {
val (lV, rV) = parallel(reduce[A](l, f), reduce[A](r, f))
f(lV, rV)
}
}
def reduceSeg[A](inp: Array[A], left: Int, right: Int, f: (A, A) => A): A = {
if (right - left < threshold) {
var res = inp(left)
var i = left + 1
while (i < right) {
res = f(res, inp(i))
i = i + 1
res
}
} else {
val mid = (left + right) / 2
val (a1, a2) = parallel(reduceSeg(inp, left, mid, f),
reduceSeg(inp, mid, right, f))
f(a1, a2)
}
}
def reduce[A](inp: Array[A], f: (A, A) => A): A =
reduceSeg(inp, 0, inp.length, f)
We use the .par function to convert a range to a parallel range. Iterations of the parallel loop will be executed on different processers. A parallel for loop does not return a value. It can only interact with the rest of the program by performing a side effect, such as writing to an array. This is only correct if iterations of the for loop write to separate memory locations, or use some form of synchronization.
The following code is correct:
def initializeArray(xs: Array[Int])(v: Int): Unit = {
for (i <- (o until xs.length).par) {
xs(i) = v
}
}
But if we had changed xs(i) = v to xs(0) = i, the code would be incorrect since we would be trying to access the same entry in an array in multiple iterations of the for loop.
Scala collections can be converted to parallel collections by invoking the .par method:
(1 until 1000).par
.filter(n => n % 3 == 0)
.count(n => n.toString == n.toString.reverse)
Implementation of sum in parallel:
def sum(xs: Array[int]) : Int = {
xs.par.fold(0)(_ + _)
}
Implementation of max in parallel:
def max(xs: Array[Int]): Int = {
xs.par.fold(Int.MinValue)(math.max) // or rewrite math.max as: (x, y) => if (x > y) x else y
}
For the previous 2 examples, fold worked out for us since the functions we provided (+ and math.max) were associative. The benefit of fold (as compared to foldLeft or foldRight) is that fold can run in parallel.
def foldLeft[B](z: B)(f: (B, A) => B): B or def fold(z: A)(f: (A, A) => A): A can be to count vowels. We can use aggregate instead, which is like a combination of the 2 functions.
def aggregate[B](z: B)(f: (B, A) => B, g: (B, B) => B): B
Array('E', 'P', 'F', 'L').par.aggregate(0)(
(count, c) => if (isVowel(c)) count + 1 else count,
_ + _
)

Each processor will use f: (B, A) => B to do its calculation. The resulting calculations from the processors are combined using g: (B, B) => B. aggregate is a very general operation.

Traversable[T] - collection of elements with type T, with operations implemented using foreachIterable[T] - collection of elements with type T, with operations implemented using iterator. Subtype of Traversable[T], containing more collection methods.Seq[T] - An ordered sequence of elements with type T, where every element is assigned to an index. Subtype of Iterable[T]Set[T] - A set of elements with type T (no duplicates)Map[K, V] - a map of keys with type K associated with values of type V (no duplicate keys)ParIterable[T], ParSeq[T], ParSet[T], ParMap[K, V],ParArray[T] - parallel array of objects, counterpart of Array and ArrayBufferParRange - parallel range of integers, counterpart of RangeParVector[T] - parallel vector, counterpart of immutable Vectorimmutable.ParHashSet[T] - counterpart of immutable.HashSetimmutable.ParHashMap[T] - counterpart of immutable.HashMapmutable.ParHashSet[T] - counterpart of mutable.HashSetmutable.ParHashMap[T] - counterpart of mutable.HashMapParTrieMap[K, V] - thread-safe parallel map with atomic snapshots, counterpart of TrieMapThese are collections that can have code that can be executed either in sequential or parallel: GenIteratble[T], GenSeq[T], GenSet[T], GenMap[K, V]
15251 is a sample palindrome. largestPalindrome searches for the largest palindrome in a sequence:
def largestPalindrome(xs: GenSeq[Int]): Int = {
xs.aggregate(Int.MinValue) (
(largest, n) =>
if (n > largest && n.toString == n.toString.reverse) n else largest,
math.max
)
}
val array = (0 until 1000000).toArray
largestPalindrome(array) // invoke sequentially
largestPalindrome(array.par) // invoke parallelly
Rule: Avoid mutations to the same memory locations without proper synchronization
The following code won't since using += on mutable.Set[Int] may modify the memory locations.
def intersection(a: GenSet[Int], b: GenSet[Int]): Set[Int] = {
val result = mutable.Set[Int]()
for (x <- a) if (b contains x) result += x
result
}
intersection((0 until 1000).toSet, (0 until 1000 by 4).toSet)
intersection((0 until 1000).par.toSet, (0 until 1000 by 4).par.toSet)
The program can be fixed by replacing mutable.Set[Int] with Java's new ConcurrentSkipListSet[Int]()
A smarter way to solve the problem is to recode the method to use filter instead of creating a new Set
def intersection(a: GenSet[Int], b: GenSet[Int]): GenSet[Int] = {
if (a.size < b.size) a.filter(b(_))
else b.filter(a(_))
}
Another Rule: Never modify a parallel collection on which a data-parallel operation is in progress
A splitter can be split into more splitters that traverse over disjoint subsets of elements.
trait Splitter[A] extends Iterator[A] {
def split: Seq[Splitter[A]]
def remaining: Int
}
Every parallel collection has its own Splitter implementation. Splitting is done multiple times during execution of a parallel operation, so it should be O(log n) or better runtime for us to benefit from parallelization.
trait Combiner[A, Repr] extends Builder[A, Repr] {
def combine(that: Combiner[A, Repr]): Combiner[A, Repr]
}
O(log n + log m) or better runtimeLet us discuss two-phase construction for arrays.
Achieving faster than O(n) runtime is not possible for combine if we use a standard array.
In Two-Phase construction, the combiner has an intermediate data structure as its internal representation
+=, the intermediate data structure should have an efficient runtimecombine, the intermediate data structure should have O(log n + log m) or better runtimeHere is my mediocre explanation of the process:
Let P be the number of processors. Use an array of P arrays. Think of it as an array of pointers to arrays.
+= is O(1) amortized time to add 1 element to the end of 1 of the nested arrays.combine is O(P) runtime to copy references to arrays, instead of copying arrays.n/P different parts of the array in parallel.Coursera: Parallel programming - Notes are based on this tutorial.
scan example was too advanced for this tutorial.RodneyShag/Parallel_programming is a public repo on GitHub by RodneyShag. Basics of parallel programming in Scala.
It declares no license on GitHub. Public does not mean open source: without a license, nobody is granted the right to reuse it.
Its maker has not tagged a system, so it is unknown here. Its README says what it needs.
Open "Take it" on its page: Take My Repo writes an install plan for your machine and hands it to your AI agent (Claude Code, Codex or Cursor), which asks you before each step. Take My Repo has not tested it on any machine.
Its last change on GitHub was on 2019-10-14. Take My Repo does not judge from that whether it is maintained.
Nobody has reviewed it on Take My Repo yet, which says nothing about its quality.
Efficient solutions to "Cracking the Coding Interview" (6th Edition) problems