Using threads to find max in array

Question

I really do not have access to anyone, outside of professors, that is highly knowledgeable about Java so I figured I would post my stuff here to further my knowledge and improve my coding. This is homework for my Operating Systems class and it works. Here are some of my main concerns.

1. Is this a good use of the static inner class?
2. Are my variable and class declarations properly declared?
3. Is there a better way than using Thread.sleep to make the sure that the main thread waits for certain child threads to complete before it performs some action?

The object of the program is to find the max in an array using 3 steps. Each step is to perform one part of the task with its own thread. For example, step one uses n threads to initialize an array of size n with 1's. Input done via command line: Prog1.java n x0 x1 ... xn, where n is the number of elements and x0 x1 ... xn are the elements. Input is limited to about 20 elements.

As I am a student, I will also glady accept any critiques on any part of the code. Sorry if this seems like too much for one question and thanks in advance to anyone who contributes.

/* User Input: 4 3 1 7 5
 Number of input values = 4
 Input values x = 3 1 7 5
 After initialization w = 1 1 1 1
 Thread T(0,1) compares x[0] = 3 and x[1] = 1, and writes 0 into w[1]
 Thread T(2,3) compares x[2] = 7 and x[3] = 5, and writes 0 into w[3]
 Thread T(1,3) compares x[1] = 1 and x[3] = 5, and writes 0 into w[1]
 Thread T(1,2) compares x[1] = 1 and x[2] = 7, and writes 0 into w[1]
 Thread T(0,3) compares x[0] = 3 and x[3] = 5, and writes 0 into w[0]
 Thread T(0,2) compares x[0] = 3 and x[2] = 7, and writes 0 into w[0]
 After Step 2 w = 0 0 1 0
 Maximum = 7
 Location = 2
 */
import java.util.Arrays;
public class Prog1 {
private static int[] w;
private static int[] x;
public static void main(String[] args) throws InterruptedException { 
 if (args.length == 0) { /* return if there are NO arguments */
 System.out.println("No arguments!");
 return;
 }
 int size = Integer.parseInt(args[0]); /* Get the number of args */
 x = new int[size]; /* Parse string array to integer */
 for (int i = 0; i < size; i++) {
 try {
 x[i] = Integer.parseInt(args[i + 1]);
 } catch (NumberFormatException nfe) {
 System.out.println("Conversion Error: " + nfe.getMessage());
 return;
 }}
 /* Initialize all w elements to 1 with a thread for each element */
 w = new int[size]; 
 for (int i = 0; i < size; i++) {
 Initialize t = new Initialize(i); 
 t.start();
 } 
 System.out.printf("%-25s%d\n","Number of input values = ", size);
 String input = Arrays.toString(x).replace("[", "").
 replace("]", "").replace(",", "");
 System.out.printf("%-21s%s\n","Input values ", "x = " + input);
 String init = Arrays.toString(w).replace("[", "").
 replace("]", "").replace(",", "");
 System.out.printf("%-21s%s\n","After initialization ", "w = " + init);
 /* Perform Comparisons with a thread for each comparison */
 int inc = 1; 
 for (int i = 0; i < size - 1; i++) {
 for (int j = inc; j < size; j++) {
 FindMax t = new FindMax(i,j);
 t.start();
 }
 inc++;
 }
 Thread.sleep(100); /* After Step 2 Output */
 String maxFound = Arrays.toString(w).replace("[", "").
 replace("]", "").replace(",", "");
 System.out.printf("%-21s%s\n","After Step 2 ","w = " + maxFound);
 /* Print the maximum number and its location with a thread for each element*/
 for (int i = 0; i < size; i++) { 
 PrintMax t = new PrintMax(i);
 t.start();
 } 
} // End main()
private static class Initialize extends Thread {
 private final int value = 1;
 private final int index;
 public Initialize(int i) {
 this.index = i;
 }
 @Override
 public void run() {
 w[index] = this.value;
 }}
private static class FindMax extends Thread {
 private final int indI;
 private final int indJ;
 public FindMax(int indI, int indJ) {
 this.indI = indI;
 this.indJ = indJ;
 }
 @Override
 public void run() {
 int num1 = x[indI];
 int num2 = x[indJ];
 int lesser;
 int compare = Integer.compare(num1, num2);
 if (compare < 0) {
 w[indI] = 0;
 lesser = indI;
 } else {
 w[indJ] = 0;
 lesser = indJ;
 }
 System.out.printf("Thread T(%d,%d) compares x[%1$d] = %d and x[%2$d] = %d, "
 + "and writes 0 into w[%d]\n", indI, indJ, num1, num2, lesser);
 }
}
static class PrintMax extends Thread {
 private final int index;
 public PrintMax(int index) {
 this.index = index;
 }
 @Override
 public void run() {
 if (w[index] == 1) {
 int max = x[index];
 System.out.printf("%-23s%s%d\n", "Maximum", "= ", max);
 System.out.printf("%-23s%s%d\n", "Location", "= ", index);
 }
 }
}}

• Loki Astari: Sorting 20 elements using multiple threads seems overkill. Doing it in a single thread should occupy the processor for microseconds. Starting the threads probably takes longer then just running across 20 elements in a single thread. Is there a particular reason you are using threads (personally I would not even look at threads until I was sifting through billions of values).
• brinks: The assignment explicitly requires that we use threads. We need n threads to initialize each element in the array to a 1, n(n-1)/2 threads to do each of the comparisons, and n threads to check whether an index has a 0 or 1 in it. I am learning java thread programming in my O/S Concepts class. I agree that it does not seem like the best way to do this.

Answer 1

I agree with @Loki Astari that this is overkill but as a homework for a course is fine. Some notes about the current code:

1. Is this a good use of the static inner class?

   It's OK but I prefer putting them to separate files. I've found that switching between windows/tabs is more handy than scrolling in the same file. You can do it if you pass the w and/or x arrays to their constructor.

2. Is there a better way than using Thread.sleep to make the sure that the main thread waits for certain child threads to complete before it performs some action?

   Yes. On low level Thread.join but I suggest you using higher level structures, like Executors and Futures for that.

   I'd implements Runnable than extends Thread and change the following loop

   for (int i = 0; i < size; i++) {
    Initialize t = new Initialize(i);
    t.start();
   }
   

   to

   // creates an executor with size threads
   ExecutorService executorService = Executors.newFixedThreadPool(size);
   List<Future<?>> initalizerFutures = new ArrayList<>();
   w = new int[size];
   for (int i = 0; i < size; i++) {
    // runs the Initializer with the executor on separate threads
    final Future<?> initalizerFuture = executorService.submit(new Initialize(i));
    initalizerFutures.add(initalizerFuture);
   }
   // waits for each initializer to complete
   for (final Future<?> future: initalizerFutures) {
    future.get();
   }
   

   (At the end of the program you should shutdown the executor.)

3. Unfortunately, the code is still not thread safe. Although accessing array elements on separate threads could be safe but the code in the question accesses the same array index from separate threads which should be synchronized properly.

   [...] synchronization has no effect unless both read and write operations are synchronized.

   Source: Effective Java, 2nd Edition, Item 66: Synchronize access to shared mutable data

   Locking is not just about mutual exclusion; it is also about memory visibility. To ensure that all threads see the most up-to-date values of shared mutable variables, the reading and writing threads must synchronize on a common lock.

   Source: Java Concurrency in Practice, 3.1.3. Locking and Visibility.

4. Arrays.toString(a).replace("[", "").replace("]", "").replace(",", "");
   

   This is duplicated in the code. You should move this logic into a separate method and use that to keep it DRY. Additionally, I guess the format of Arrays.toString won't change but it would be cleaner iterating through the array and building the string with a loop or using an already existing join implementation.

5. In System.out.printf use %n instead of \n. The former outputs the correct platform-specific line separator.

6. System.out.printf("%-21s%s\n", "Input values ", "x = " + input);
   

   could be

   System.out.printf("%-21s%s%s%n", "Input values ", "x = ", input);
   

   (without the concatenation).

7. Short variable names are hard to read, like x and w. Longer names would make the code more readable since readers don't have to decode the abbreviations every time and when they write/maintain the code don't have to guess which abbreviation the author uses.

8. Comments like this are rather noise:

   if (args.length == 0) { /* return if there are NO arguments */
   

   It's rather obvious from the code itself, so I'd remove the comment. Your professors might require these comments but keep in mind that it's not clean. (Clean Code by Robert C. Martin: Chapter 4: Comments, Noise Comments)

9. System.out.println("No arguments!");
   

   Error messages shouldn't blame the user (don't say what he did is wrong), give a suggestion about what they should do. (See: Should we avoid negative words when writing error messages?, What will be the Best notifications and error messages?)

10. The Java Language Specification, Java SE 7 Edition, 6.1 Declarations:

    Class and Interface Type Names

    Names of class types should be descriptive nouns or noun phrases, not overly long, in mixed case with the first letter of each word capitalized.

    According to that I'd rename Initialize to Initializer, FindMax to MaximumFinder, PrintMax to MaximumPrinter.

11. Comments on the closing curly braces are unnecessary and disturbing. Modern IDEs could highlight blocks.

    } // End main()
    

    "// ..." comments at end of code block after } - good or bad?

• brinks: In a problem such as mine is it necessary to use the List<Future<?>> initalizerFutures = new ArrayList<>();? I am not sure if I fully understand the way it works, but is this not needed in my case because I do not really need to return any value? @TwoThe has a similar solution, but just used the ExecutorService. If it is not too much trouble and there is some reason for using Future in this context could you explain it? I have read through a few blogs and the Javadoc for the associated classes and it is all a bit murky to me.
• palacsint: @brinks: The other option is Thread.join (or maybe other classes from the java.util.concurrent package) but it's easier to work with Futures and Executors. You can parametrize the Future with Void (uppercase V) if you are not interested in the return value but Future.get is still needed to wait the completion of the submitted task.
• palacsint: @brinks: Usage is easy: submit a Runnable instance to an ExecutorService. The ExecutorService runs the submitted Runnable's run method on a separate thread. If run finishes the Future.get will return. If run is still working the Future.get will wait for its completion. Executors.newFixedThreadPool(10) creates an executor with 10 threads, so ten Runnable instances could run parallel but you can queue more.

Answer 2

Since you asked for it, I try to comment on your code in "extra-precise review mode". ;)

General

One does not use global variables

Unless they are static and final, in which case they are called "constants". There are just too many ways to fail when using those.

Code Structure

It is always a good idea to properly indent and structure your code using your IDE's build-in auto-formatting. It helps you on detecting basic coding mistakes and is in general a sign that the author has a certain level of quality.

Use functions to structure your code. Writing all what you want to do in a single function (aka spaghetti-code) will work till the moment you need to change something. And in reality you always eventually change your code. The decision of whether or not to put parts of your code in a sub-function should follow the rules of database normalization as it is about the same concept: avoid deletion, insertion and update anomalies.

protected vs private

When deciding private vs protected you should always use protected unless there is a specific reason not to. private will hide members and functions from sub-classes as well, so without a getter/setter pair they cannot be accessed. And even then: using getters/setters for internal variables is often an unnecessary burden, code bloat and degrades performance.

User communication

When communicating with the user of your program, always assume that he/she has no clue what this program is doing and be polite. Statements like No arguments! while being technically correct will not help the user to figure out what to do at that point. A better version would be:

Not enough arguments. Cannot continue.
Compares a given set of integers and prints the maximum value and its location.
Usage:
Prog1 <int>, <int>, ...
Where <int> is any valid integer.

Variable/method names

Be expressive with the names of your variables and methods. Something like x is short to type, but won't help you or anyone else to understand what the purpose of this variable might be. This is for once helpful to actually understand the code, and on the other hand a good way to prevent some mistakes while coding. If you write x + 1 this looks reasonable, unless you know that x is actually an array. This wouldn't happen if you name it integers or inputArray.

Threads vs. Runnables

In general you should always use Runnables and process them using an ExecutorService. This simplifies management of code a lot and also makes it more flexible by separating the actual tasks from the system to process them. Imagine that it might be necessary to optimize performance later on, then suddenly you need to rewrite half of your code, while with Runnables you can focus completely on the actual execution part of the code, as the task definitions stay the same.

Code

int size = Integer.parseInt(args[0])

You assume at this point that args[0] is an integer, otherwise the code will crash at this point. Furthermore the size is not required at all, as it is equal to the amount of parameters.

In general parsing the arguments is a good candidate for a sub-method for several reasons:

• It removes clutter from the code
• It is easy to find
• It transforms the untrusted user input into a trusted work-set (or terminates) so the rest of the program can assume that the input data is valid.

An example parsing function:

public static int[] parseInputParameters(final String[] args) {
 if ((args == null) || (args.length < 2)) {
 System.out.println("Not enough arguments. Cannot continue.");
 return null;
 }
 final int[] result = new int[args.length];
 for (int i = 0; i < args.length; ++i) {
 try {
 result[i] = Integer.parseInt(args[i]);
 } catch (NumberFormatException nfe) {
 System.out.println("'" + String.valueOf(args[i]) + "' is not a valid integer. Cannot continue.");
 return null;
 }
 }
 return result;
}

Note that I compare length < 2 as comparing a single integer is not possible.

w = new int[size];
for (int i = 0; i < size; i++)

You should always do array initialization using the length operator like for (int i = 0; i < w.length; i++) While technically they contain the same value, this is a potential update issue if size changes in between, while length will always be correct.

Initialize t = new Initialize(i);
t.start();

While this is thread-safe because you happen to use an array, the cost to create, initialize and run a Thread massively out-weights the cost for setting the variable in a simple loop. One might as well ask how much faster 100 threads initialize an array on a 1-core system than 1 thread can do?

A few lines later you already use the array w, even though there is no guarantee that threads are already done initializing. There is a good chance that our output will print some of the variables as 0, because the thread was not yet done initializing.

In addition Java uses a memory model that allows threads to use local copies of variables, as long as the code stays the same from a single-threaded perspective of the thread (and the thread alone). So even if some threads are already done initializing, the array you use in your main might not yet contain these updates just because they simply have not yet been written to the array hold by the main thread. For further reading see volatile.

System.out.printf("%-25s%d\n", "Number of input values = ", size);

Why use variables for static text? Why not:
System.out.printf("Number of input values = %d\n", size);

Your version forces the JVM to do more construction than actually necessary. Unless you plan to distribute your program in different languages, you should not do that.

String input = Arrays.toString(x).replace("[", "").replace("]", "").replace(",", "");

This would be a good candidate for a sub-method, as you use this transformation in various places. Beside using a StringBuilder, this can also be done using Regex in the form of Arrays.toString(x).replaceAll("[\\[\\],]", "").

int inc = 1;
for (int i = 0; i < size - 1; i++) {
 for (int j = inc; j < size; j++) {
 FindMax t = new FindMax(i, j);
 t.start();
 }
 inc++;
}

Again performance is questionable here. In addition you transmit indexes to your threads instead of transmitting the actual values, which violates the information hiding principle and chains those threads to the existence and correctness of those global variables. You should use a data class for your case that is considered thread-local, which means that the thread can do everything it wants with it, as all thread issues are prevented since only this single thread is able to access that encapsulated data.

Thread.sleep(100);

Who guarantees that your threads are done after 100 millis?

if (compare < 0) {
 w[indI] = 0;
 lesser = indI;
} else {
 w[indJ] = 0;
 lesser = indJ;
}

This would in general violate threading rules as many threads write simultaneously to the same data locations. However as you use arrays and only write 0, this is thread-safe. But still this is code that can easily break with the slightest change to your code.

Cleaner version

I uploaded a modified version of your code here including most of my suggestions. This is not what I would call clean code, but given the task trying to clean everything up would be futile.

I am using Executors with inline Runnables to emphasize how much of an overkill that is. It would be cleaner to create extra classes for those Runnables.

However removing the Runnables and executors alltogether and turning it into a simple loop would be a much better idea. Using Arrays.sort(inputValues) would be infinitively faster.

Your Questions

Is this a good use of the static inner class?

Debatable. While on the one hand it is cleaner than not using any class, it is still overkill.

Are my variable and class declarations properly declared?

Technically yes, but the scope (protected vs private) is not optimal and the names are not very expressive.

Is there a better way than using Thread.sleep to make the sure that the main thread waits for certain child threads to complete before it performs some action?

In my example I use an ExecutorService in combination with shutDown() and awaitTermination(...). An alternative would be a CountDownLatch.

• Yuushi: I disagree with your protected vs private comments. Inheritance couples classes together very tightly, and is an important design decision, not to taken lightly by just making everything protected. Further, it's arguably better to leave variables as private, and have protected methods that subclasses can access if and when they need to. It is very, very unlikely that there will be any kind of detectable performance degradation from this approach.
• TwoThe: It depends on your view on inheritance. I've often came across classes that went the "all private" approach, and extending them was a pain or impossible, because the original author wasn't creative enough to think of all possible scenarios. My approach is: create a good API, but allow everything outside of that which isn't critical, because you never know what others want to do with it. And the performance reduction was about having tons of set()/get() in your code, just because you made something private for no reason.
• Yuushi: Something as simple as set()/get() is almost guaranteed to be inlined by the JVM.