Multithreaded Pascal's Triangle Calculator

Question

I once wrote a program to calculate Pascal's triangle limited only by memory. I recently looked back and was disturbed by how ugly it is. I can tell that there are some bad practices for lack of better options known to me.

import java.math.BigInteger;
public class Pascal {
 private final int numRows; //The number of rows that the program should calculate
 private final int numThreads = Runtime.getRuntime().availableProcessors(); //The number of cores that we can spawn threads for
 private final Thread[] workerThread = new Thread[numThreads]; //The threads that will do the calculations
 private final boolean[] threadRunning = new boolean[numThreads]; //A reference for the threads to synchronize
 private final boolean[] stopThread = new boolean[numThreads]; //A reference for the threads to stop
 private final BigInteger[][] pascal; //The actual triangle
 private int i; //This is just a terrible workaround for the 'threadRun' to be able to access index loops
 private static final BigInteger one = new BigInteger("1"); //BigInteger representing 1
 private BigInteger maxNumber = null; //The maximum number in the triangle
 private final Runnable threadRun = () -> { //The thread code to speed up the process up by as many cpus as there are
 final int threadId = Pascal.this.i; //Index loop is the thread id when the thread is started
 //System.out.println(i);
 for(;;) {
 if(Pascal.this.stopThread[threadId]) return; //Stop if requested
 while(!Pascal.this.threadRunning[threadId]) { //If the thread is paused
 if(Pascal.this.stopThread[threadId]) return; //Stop if requested
 try {
 Thread.sleep(1); //Or sleep until it's running again
 }
 catch(InterruptedException ex) {
 if(Pascal.this.stopThread[threadId]) return; //Don't stop this thread! We still need it! Unless it is told to stop.
 }
 }
 for(int a = threadId + 1; a < Pascal.this.i; a += numThreads) { //Calculate this thread's share of the row
 Pascal.this.pascal[Pascal.this.i][a] = Pascal.this.pascal[Pascal.this.i-1][a-1].add(Pascal.this.pascal[Pascal.this.i-1][a]);
 }
 Pascal.this.threadRunning[threadId] = false; //This thread is done, so notify the main thread and wait for furuther instructions
 }
 };
 public Pascal(int rows) {
 pascal = new BigInteger[rows][]; //Each row has variable length
 numRows = rows;
 }
 public void calculate(boolean print) {
 //Start alll the threads in idle mode
 for(i = 0; i < numThreads; i++) {
 threadRunning[i] = false;
 stopThread[i] = false;
 workerThread[i] = new Thread(threadRun);
 workerThread[i].start();
 //Wait for the thread to spawn
 try {
 Thread.sleep(50);
 }
 catch(InterruptedException ex) {}
 }
 //Print the first two lines
 if(print) {
 System.out.println("1");
 System.out.println("1 1");
 }
 //Initialize the first two rows
 pascal[0] = new BigInteger[] { one };
 pascal[1] = new BigInteger[] { one, one };
 //Iterate through the rows
 for(i = 2; i < numRows; i++) {
 //Can't have the worker threads accessing the pascal at the same time as the main thread
 synchronized(pascal) {
 //This is a triangle array, so the row length is the row number
 pascal[i] = new BigInteger[i + 1];
 synchronized(pascal[i]) {
 //Both ends of the triangle are one by definition
 pascal[i][0] = one;
 pascal[i][i] = one;
 }
 }
 //Let the theads compute!
 for(int j = 0; j < numThreads; j++) {
 threadRunning[j] = true;
 }
 //Wait for the threads to finish computing
 while(!allFalse(threadRunning)) {}
 //Print the row if desired
 if(print) {
 for(int j = 0; j <= i; j++) {
 System.out.print(pascal[i][j] + " ");
 }
 System.out.println();
 }
 //Free memory that is no longer needed
 pascal[i - 1] = null;
 //The biggest number in the row is that in the middle
 maxNumber = pascal[i][i/2];
 }
 //Stop all of the threads when the computation is done
 for(int i = 0; i < numThreads; i++) {
 stopThread[i] = true;
 }
 }
 public BigInteger getMaxNumber() {
 return maxNumber;
 }
 public static void main(String[] args) {
 int numRows = 10;
 if(args.length > 0) { //Check if the user wants to specify a row count other than 10
 try {
 numRows = Integer.parseInt(args[0]);
 }
 catch(NumberFormatException ex) {
 System.out.println("Please enter a valid number.");
 System.exit(1);
 }
 }
 numRows++; //To account for one less row being calculated than should be
 Pascal pascal = new Pascal(numRows);
 pascal.calculate(true); //actually print the triangle
 System.out.println(pascal.getMaxNumber());
 }
 //Checks the array to see if all the elements are false
 public static boolean allFalse(boolean[] array) {
 for(boolean b : array) if(b) return false;
 return true;
 }
}

For example, there has got to be a better way for interthread communication. I am looking for best Java practices here that makes the code easy to read but also if there are performance or memory usage improvements, that is also welcome.

I have tried to comment the code as best as I can.

Answer 1

private final Runnable threadRun = () -> { //The thread code to speed up the process up by as many cpus as there are
 final int threadId = Pascal.this.i;

Does not work reliably. threadId is assigned when the corresponding thread executes that line; if it does or not before the next iteration changing i is undefined and hence not guaranteed.

for(int a = threadId + 1; a < Pascal.this.i;

Race condition on Pascal.this.i: Threads are already started while i is still being modified from the main thread.

//Can't have the worker threads accessing the pascal at the same time as the main thread
synchronized(pascal) {

Doesn't work because you do not synchronize in the worker threads, i.e. the worker threads don't care and still access pascal whenever they want.

Plus some more issues which affect the functional correctness. I suggest you try and fix those first. You may want to have some read on Java's threading, especially about how Thread and Runnable relate, what thread-management routines there are in Thread (mainly thinking about start(), interrupt(), and join()) and when and how to use synchronized. It's actually not very complex, and pretty straight forward to use/implement in a simple case like your's. To improve your solution you could then familiarize yourself with Object.wait() and Object.notify() for inter-thread event signalling and/or ready-made data structures like Queues for data exchange between threads.

• nimsson: The program does run correctly though. I have tested it on many computers with various numbers of cores.
• nimsson: And the final int threadId = Pascal.this.i was intentionally like that. The thread id is assigned to i as it is in the loop at the time that the thread starts
• JimmyB: Sorry, I overlooked that you were using a lambda, not an anonymous class. In that case, it may indeed work, promoted by the Thread.sleep(50); which causes the new thread to execute before i is modified with a certain probability, but that is by no means guaranteed and so should not be relied upon.
• nimsson: maybe that's why it sometimes fails on my computer...

Answer 2

Comments

The first thing that is hard to read in your code is the space taken by all those comments. They take so much space and does not provide really much at first sight that they are more ruining the code than anything else. Reserve comments when you want to convey the why of the code, not to explain what your variable name is already saying. Comment should be use in special case, not on every lines.

Organization

The other thing I would critic is the organisation of the code. I would have suggested that instead of defining a private final Runnable threadRun, you should have implemented Runnable and define that code in the method of the class. Having such an important part of the code in the definition of the members of the class is a bit weird. This would make the method more readable since you would not have to resort to all those Pascal.this in your method.

By reading a bit more your code, I now understand you can't really do what I first suggested since the calculate is an instance method. I still suggest you do this differently, maybe by declaring a sub static class inside the pascal case and use that class to define your Runnable would make it clearer.

---

Small correction

• Your code is not well formated everywhere, please format it correctly next time (ex: catch should be on the same line that }
• I suggest that you always use {} even for one-liner.