1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$
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.

\$\endgroup\$
4
  • \$\begingroup\$ The program does run correctly though. I have tested it on many computers with various numbers of cores. \$\endgroup\$
    – nimsson
    Dec 9 '15 at 20:27
  • \$\begingroup\$ 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 \$\endgroup\$
    – nimsson
    Dec 9 '15 at 20:29
  • \$\begingroup\$ 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. \$\endgroup\$
    – JimmyB
    Dec 10 '15 at 16:33
  • \$\begingroup\$ maybe that's why it sometimes fails on my computer... \$\endgroup\$
    – nimsson
    Dec 10 '15 at 22:41
0
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.