For his 2020 New Years resolution, Larry Candlepin wants to bowl a perfect 300. However, it's already April, and Larry can barely bowl a 90 on a good day. Thankfully, you tell him about a strategy that can make his training more efficient -- he can clone himself and bowl on every lane of the alley! This genious multithreading strategy can help Larry get in all the practice he needs to improve his bowling skills by the end of the year! But first, he needs you to teach him how to multithread so he can acheive his dream of becoming a bowling star!

In this lab you will learn the basics of threading in Java. Java has a lot of threading tools, and you should look at the java.util.concurrent and java.util.concurrent.atomic packages if you want to learn more.


This lab has two parts: Counting Primes and conceptual KD-Tree Search. For this lab, we will be working on a code base separate from the Autocorrect project. You can get access to the stencil code here.

Part 1: Counting Primes

For this part of the lab, you are going to count the number of primes less than some number n. In the stencil, you have access to the PrimeCalculator class, which has an isPrime(int num) method that tests if a number is prime. For example, PrimeCalculator.isPrime(5) will return true. You don't have to worry about how it's implemented. One important thing to note is that this implementation considers 1 to be prime.

A Working Solution

Take a look at the Main.java class. It is currently mostly empty. The MAX_NUMBER_TO_TEST field is set to 8,000,000. We want to find the number of primes less than this number. The prime-number theorem in mathematics states that the number of prime numbers less than n is approximately n/log n. For what it's worth, the correct answer for our case is 539,778 (including 1).

Read the TODO:[Part 1] statement and fill in the appropriate code. You do not need threads for this part. When you have finished, run the program and make note of the number of primes that is printed out as well as how long it took. Verify that the resulting number of primes is correct.

Improving the Solution

You've probably realized that if you really want to verify the approximation, you'll need a much large value for MAX_NUMBER_TO_TEST. But even with the current value, it still takes a long time to count the number of primes. How can we make this program run faster?
One way to improve the runtime is to distribute the work of counting primes to many separate processes, known as threads. Each thread runs independently and concurrently, which means that more operations can be done in the same amount of time.
There are two TODO:[Part 2] blocks for you to fill out, one in Main.java and one in PrimeCalcThread.java. You should probably do the latter first. Once you are done, run the program. You should notice that it takes a lot less time to count all the primes.

Note: When you start running a thread, you want to start it by running the start() method (e.g. thread.start();), not the run() method. If you run the method by calling run(), it will run that method in the main thread. However, if you run the thread with start(), it will run the run() method on a separate thread. To join the threads, you want to call the join() method from the main thread (e.g. thread.join();). This will ensure that the main thread will wait until all the threads that have been joined are done, before continuing the program. Once you start all the threads, you will then want to join them and output the value of the counter.

(Thread) Safety First

Though you have made your program a lot faster, there is a problem. If you run the program multiple times, you will notice that the final number you get will change every time and will not be equal to the number you got in non-threaded solution. The reason for this is because when multiple threads call the increment() method in IntWrapper, the value might not get actually incremented correctly. This is an example of a concurrency issue, where concurrently modifying a field causes indeterminate behaviour. In our case the only issue is that the output value is wrong, but if you were using threads to concurrently modify more complex objects, your program could crash.

In order to solve this, you can use Java's synchronized keyword, which you can read about here. There is a simple way to modify IntegerWrapper to make increment() synchronized and you should do this for TODO:[Part 3]. Once you make this small change, your part 1 and part 2 solutions should output te same values.

Another Solution

We will now try another threaded solution that instead of dividing the bounds of search for each thread, we will have each thread increment a single primality counter. This can be done using Java's AtomicInteger module. There are two TODO:[Part 4] blocks for you to fill out, one in Main.java and one in DistributionThread.java. The four different DistributionThreads should each be incrementing a single shared AtomicInteger (the current value being tested for primality) and IntWrapper (the counter for the number of primes so far).

If you get the same output consistently for all the TODOs, you've finished the coding portion of the lab! Please show a TA the changes you've made to get checked off.

Part 2: Conceptual KD-Tree Search

Think about the following conceptual question and prepare an answer to give to your TA for checkoff:

If you have a very large dataset of n-dimensional points, how could you multithread the construction of a KDTree to make it more efficient?