Multithreading

Modern day processors have more than just one single CPU core. In fact, many consumer grade processors have anywhere between 2 to 24 cores on a single chip! Comparing these chips to hardware that was available at the start of Java's lifecycle would be like comparing a flintlock pistol to a Stinger missile. As a result, programmers, alongside Java's ecosystem itself, have had to adapt to these changes in hardware by developing new techniques that can properly leverage the additional computational firepower. The primary innovation comes in the form of multithreading which aims to take advantage of these multiple cores by running tasks simultaneously.

An execution model describes the behavior of how a program runs. If we focus less on the semantics/syntax of the language, but rather on the order in which instructions are processed we can define three distinct, but somwhat dependent, categories: sequential, concurrent, and parallel execution models.

I highly suggest running these examples on your own machine. It is not enough to see static renders of multithreading, you need to see it running to get a feel for it.

Below is an example of parallel execution using Java's Thread API:

 1:  import java.lang.Thread;
 2: public class HelloWorlds extends Thread{
 3:     int id;
 4: 
 5:     public void run(){
 6:         System.out.println(String.format("Thread %d: Hello Worlds!", this.id));
 7:     }
 8: 
 9:     public HelloWorlds(int id){
10:         this.id = id;
11:     }
12: 
13:     public static void main(String[] args) throws Exception{
14:         int worlds = Integer.parseInt(args[0]);
15:         Thread[] ts = new Thread[worlds];
16:         for(int i = 0; i < worlds; i++){
17:             ts[i] = new HelloWorlds(i);
18:             ts[i].start();
19:         }
20:         for(Thread t : ts){
21:             try{
22:                 t.join();
23:             }catch(Exception e){
24:                 System.out.println(e);
25:                 System.exit(-1);
26:             }
27:         }
28:     }
29: }

There's a lot going on here which probably makes this look insane at first glance. Let's break it down into chunks.

First, I define a class HelloWorlds. HelloWorlds is a subclass of the Thread class. Thread is how Java abstracts a thread of execution in a program. In sequential execution (Listing 1) there is only ever a single thread. In parallel execution there is at least two threads. Because Thread implements the Runnable interface it provides an implementation for the run() method—all user-defined worker threads override run() to replace it with useful work associated with its class. In HelloWorlds, the "useful work" is printing out a "Hello World" message.

Second, in the main method I instantiate an array of worlds number of Thread objects. Each object is instantiated with a unique id and stored in the array. Each Thread is then started up using the start() method. The start() method informs the JVM that it is time to create a new thread of execution. This new execution thread is then queued up and will begin at the run() method.

Third, I call join() on all of the Thread objects. join() halts the calling thread's exeuction until the target thread has finished executing. The default, main thread of execution is just like any other potentially schedulable thread, so we want to make sure it doesn't stop executing before any of the child threads.

Try seeing what happens when you comment out the call to join()!

We can see what happens below when I set worlds equal to 2, 5, and 10, respectively:

josephraskind@stargazer:/tmp/multithreading$ java HelloWorlds.java 2
Thread 0: Hello Worlds!
Thread 1: Hello Worlds!
josephraskind@stargazer:/tmp/multithreading$ java HelloWorlds.java 5
Thread 3: Hello Worlds!
Thread 0: Hello Worlds!
Thread 1: Hello Worlds!
Thread 2: Hello Worlds!
Thread 4: Hello Worlds!
josephraskind@stargazer:/tmp/multithreading$ java HelloWorlds.java 10
Thread 0: Hello Worlds!
Thread 3: Hello Worlds!
Thread 5: Hello Worlds!
Thread 7: Hello Worlds!
Thread 8: Hello Worlds!
Thread 9: Hello Worlds!
Thread 1: Hello Worlds!
Thread 2: Hello Worlds!
Thread 4: Hello Worlds!
Thread 6: Hello Worlds!

One thing you'll notice is that the higher thread counts are all out of order. This is proof that our tasks ran in a parallel/concurrent fashion. Multithreaded scheduling is deeply non-deterministic—from the perspective of the programmer there's no telling which thread will process before another!

Multithreading is an incredibly powerful tool that can greatly speed up the execution of complex programs, but it often comes at a significant cost to developers. The cost is that it is very difficult to write consistent, thread-safe multithreaded processes. The principle reason for this is due to the phenomena of race conditions.

Some tasks are inherently suited to multithreading, such as web browsers and database management systems, and others can be broken down into smaller tasks which could benefit from multithreaded execution. Let's take an example of summing up the values in a very large array. Below we have both a sequential and a parallel solution:

 1: import java.util.Arrays;
 2: public class ArraySummation extends Thread{
 3:     static int SIZE = 500_000_000;
 4: 
 5:     public static int parallelSum(int[] arr) {
 6:         int numThreads = Runtime.getRuntime().availableProcessors();
 7:         int chunkSize  = arr.length / numThreads;
 8:         int[] partial  = new int[numThreads];
 9: 
10:         Thread[] threads = new Thread[numThreads];
11: 
12:         for(int t = 0; t < numThreads; t++){
13:             final int threadIndex = t;
14:             final int start = t * chunkSize;
15:             final int end   = (t == numThreads - 1) ? arr.length : start + chunkSize;
16: 
17:             threads[t] = new Thread(() -> {
18:                     int localSum = 0;
19:                     for(int i = start; i < end; i++)
20:                         localSum += arr[i];
21:                     partial[threadIndex] = localSum;
22:             });
23:             threads[t].start();
24:         }
25: 
26:         try{
27:             for(Thread thread : threads)
28:                 thread.join();
29:         }catch(Exception e){
30:             System.out.println(e);
31:             System.exit(-1);
32:         }
33:         int total = 0;
34:         for(int p : partial)
35:             total += p;
36:         return total;
37:     }
38: 
39:     public static int sequentialSum(int arr[]){
40:         int sum = 0;
41:         for(int v : arr)
42:             sum += v;
43:         return sum;
44:     }
45: 
46:     public static void main(String[] args){
47:         int arr[] = new int[SIZE];
48:         Arrays.fill(arr, 1);
49: 
50:         long start = System.currentTimeMillis();
51:         int sum = sequentialSum(arr);
52:         double duration = (System.currentTimeMillis() - start) / 1000.0; 
53:         System.out.printf("Sequential Sum: %d (%.2f s)%n", sum, duration);
54: 
55:         start = System.currentTimeMillis();
56:         sum = parallelSum(arr);
57:         duration = (System.currentTimeMillis() - start) / 1000.0; 
58:         System.out.printf("Parallel Sum: %d (%.2f s)%n", sum, duration);        
59:     }
60: }

If we run both in interpretation mode:

josephraskind@stargazer:/tmp/multithreading$ java -Xint ArraySummation.java 
Sequential Sum: 500000000 (6.45 s)
Parallel Sum: 500000000 (2.70 s)

We can see a ~2.4X speedup with the parallel execution method.

1. Compile and run Listing 16 on your machine. Record both the sequential and parallel times. How many logical processors does your machine have? Run Runtime.getRuntime().availableProcessors() to find out. Is the speedup you observe close to that number? Based on what the chapter says about memory bandwidth and Amdahl's Law, explain why the speedup is lower than the number of cores.
2. The chapter shows that counter++ compiles to four bytecode instructions. Before running Listing 7, predict what value counter will hold after two threads each count to 1000000. Will it be exactly 2000000, less, or more? Run it several times and record the results. Are they consistent? Explain why the output varies between runs in terms of thread scheduling.
3. The chapter introduces synchronized as a fix for the race condition. Add synchronized to the run method in Listing 7 and rerun it with upperBound set to 1000000. Does the result now equal 2000000 consistently? Then measure the time taken with and without synchronized. What cost does synchronization impose and why?

4. Predict the output of the following program before running it:

   public class Predict {
       static int x = 0;
       public static void main(String[] args) throws InterruptedException {
           Thread t1 = new Thread(() -> { for(int i = 0; i < 1000; i++) x++; });
           Thread t2 = new Thread(() -> { for(int i = 0; i < 1000; i++) x++; });
           t1.start();
           t2.start();
           t1.join();
           t2.join();
           System.out.println(x);
       }
   }
   

   Run it ten times and record each result. Is the output always 2000? Always less? Could it ever be more than 2000? Explain each answer.

5. The chapter states that join causes the calling thread to wait until the joined thread finishes. Remove both join calls from Listing 16 and rerun it. What happens to the result? Explain in terms of what the main thread does after calling start without join.
6. The chapter motivates multithreading through hardware: modern CPUs have multiple cores that can execute instructions simultaneously. In your own words explain the difference between concurrency and parallelism. Is the sequential version of ArraySummation concurrent? Is the parallel version? Can a program be concurrent without being parallel?
7. The chapter shows that each thread in parallelSum writes to its own slot in the partial array. Why is this safe from race conditions when a shared counter field is not? What property of the partial array makes it thread-safe without needing synchronized?
8. The chapter introduces Runnable as the interface used to define thread tasks. Write a program with three threads, each printing its own name and a count from 1 to 5. Run it several times. Is the output always in the same order? What does the variability in output tell you about how the OS schedules threads?
9. Thread creation carries overhead. Design an experiment that measures this overhead by creating a thread that does nothing (() -> {}) and measuring how long it takes to start and join it. Run the experiment 1000 times and compute the average. How does this overhead compare to the time saved by parallelizing ArraySummation? Under what circumstances would the overhead make parallelism not worth it?
10. The chapter presents multithreading as a way to leverage multiple CPU cores for performance. Consider a program that reads a large file from disk and processes each line. Would multithreading help this program? What would the bottleneck be? Compare this to ArraySummation and explain why some workloads benefit more from multithreading than others.