This is the program I was given, it searches a large array for a max value:
import java.util.Date;
import java.util.Random;
class FindMax {
private static final int N = 256 * 1024 * 1024;
public static void main(String args[]) {
assert(N > 0);
int array[] = new int [N];
assert(array != null);
Random random = new Random(new Date().getTime());
for (int i = 0; i < N; i++) {
array[i] = random.nextInt();
}
Date start = new Date();
int max = array[0];
for (int i = 1; i < N; i++) {
if (array[i] > max) {
max = array[i];
}
}
Date end = new Date();
System.out.println("max: " + max);
System.out.println("time in msec: " + (end.getTime() - start.getTime()));
}
}
I am to increase the speed by having multiple threads each search part of the array. This is what i did:
import java.util.Date;
import java.util.Random;
class FindMax extends Thread{
private static final int N = 256 * 1024 * 1024;
static int array[] = new int [N];
static int max = array[0];
int start, end;
public void run(){
for (int i = this.start; i < this.end; i++) {
if (array[i] > max) {
max = array[i];
}
}
}
public FindMax(int q, int u){
this.start=q;
this.end=u;
}
public static void main(String args[]) {
assert(N > 0);
int ts = Integer.parseInt(args[0]);
assert(array != null);
Random random = new Random(new Date().getTime());
for (int i = 0; i < N; i++) {
array[i] = random.nextInt();
}
Date start = new Date();
Thread t[] = new Thread[ts];
int eacht = (256 * 1024 * 1024)/ts;
for( int p=0; p<ts;p++){
t[p] = new FindMax(0+p*eacht, (eacht-1)+p*eacht);
t[p].start();
}
Date end = new Date();
System.out.println("max: " + max);
System.out.println("time in msec: " + (end.getTime() - start.getTime()));
}
}
The problem is that is has the opposite effect. The more threads (taken from command line argument) the LONGER the program takes to run. Why is this doing the exact opposite of increasing the programs speed with increased threads created?
max
field declared asstatic
. This can give wrong results (because, for example, a thread might see thatarray[i] > max
right before some other thread increases max, and then performmax = array[i]
right afterward), and also can cause significant slowdown (because many processors writing to the same memory location will keep invalidating each other's caches of what's in that location). Instead, you need each thread to write to its ownmax
, and then, once the threads finish, you can go through and find the greatestmax
. \$\endgroup\$