I am currently writing a program which first generates prime numbers by the Sieve of Eratosthenes sequentially, then concurrently. The concurrent version of the algorithm is supposed to be quicker than the sequential one, but in my case the concurrent version is approx. 10 times slower. I am wondering where I am putting the extra work on my threads, compared to the main thread in the sequential solution. Here's my program (prepare to read a bit!):
Primes.java:
public abstract class Primes {
byte[] bitArr;
int maxNum;
final int[] BITMASK = { 1, 2, 4, 8, 16, 32, 64 };
final int[] BITMASK2 = { 255 - 1, 255 - 2, 255 - 4, 255 - 8,
255 - 16, 255 - 32, 255 - 64 };
void setAllPrime() {
for (int i = 0; i < bitArr.length; i++) {
bitArr[i] = (byte) 127;
}
}
void crossOut(int i) {
bitArr[i/14] = (byte) (bitArr[i/14] - BITMASK[((i/2)%7)]);
}
boolean isPrime(int i) {
if(i == 2){
return true;
}
if((i%2) == 0){
return false;
}
return (bitArr[i/14] & BITMASK[(i%14)>>1]) != 0;
}
int nextPrime(int i) {
int k;
if ((i%2) == 0){
k =i+1;
}
else {
k = i+2;
}
while (!isPrime(k) && k < maxNum){
k+=2;
}
return k;
}
void printAllPrimes() {
for (int i = 2; i <= maxNum; i++){
if (isPrime(i)){
System.out.println("Prime: " + i);
}
}
}
}
PrimesSeq.java:
import java.util.ArrayList;
public class PrimesSeq extends Primes{
PrimesSeq(int maxNum) {
this.maxNum = maxNum;
bitArr = new byte[(maxNum / 14) + 1];
setAllPrime();
generatePrimesByEratosthenes();
}
void generatePrimesByEratosthenes() {
crossOut(1); // 1 is not a prime
int curr = 3;
while(curr < Math.sqrt(maxNum)){
for(int i = curr*curr; i < maxNum; i+=2*curr){
if(isPrime(i)){ // 2*curr because odd*2 = even!
crossOut(i);
}
}
curr = nextPrime(curr);
}
}
}
PrimesPara.java:
import java.util.ArrayList;
public class PrimesPara extends Primes {
PrimeThread[] threads;
int processors;
int currentState = 0;
//0 = Init
//1 = Generate primes after thread #0 finish
//2 = Factorize
public PrimesPara(int maxNum){
this.maxNum = maxNum;
this.processors = Runtime.getRuntime().availableProcessors();
bitArr = new byte[(maxNum / 14) + 1];
setAllPrime();
this.threads = new PrimeThread[processors*2];
generateErastothenesConcurrently();
//printAllPrimes();
}
public void generateErastothenesConcurrently(){
int[] starts = generateThreadIndexes();
for(int i = 0; i < threads.length; i++){
if(i != threads.length-1){
threads[i] = new PrimeThread(starts[i], starts[i+1]-1, i);
} else {
threads[i] = new PrimeThread(starts[i], maxNum, i);
}
}
//Start generating the first primes
crossOut(1);
Thread th = new Thread(threads[0]);
th.start();
try {
th.join();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
currentState = 1;
//Start generating the rest of the primes
Thread[] thrs = new Thread[threads.length];
for(int i = 0; i < thrs.length; i++){
thrs[i] = new Thread(threads[i]);
thrs[i].start();
}
for(int i = 0; i < thrs.length; i++){
try {
thrs[i].join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
currentState = 2;
}
private int[] generateThreadIndexes(){
int[] indexes = new int[processors*2];
for(int i = 0; i < indexes.length; i++){
indexes[i] = (i*((maxNum/(processors*2))));
}
indexes[indexes.length-1]++;
return indexes;
}
public class PrimeThread implements Runnable {
int start;
int end;
int thridx;
public PrimeThread(int start, int end, int thridx){
this.start = start;
this.end = end;
this.thridx = thridx;
}
public void run() {
switch(currentState){
case 0:
generateSqrtPrimes();
break;
case 1:
generateMyPrimes();
break;
case 2:
break;
}
}
private void generateSqrtPrimes(){
int curr = 3;
while(curr < Math.sqrt(maxNum)+1){
for(int i = curr*curr; i < Math.sqrt(maxNum)+1; i+=2*curr){
if(isPrime(i)){ // 2*curr because odd*2 = even!
crossOut(i);
}
}
curr = nextPrime(curr);
}
}
private void generateMyPrimes(){
int curr = start>(int)Math.sqrt(maxNum)?start:(int)Math.sqrt(maxNum);
while(curr < end){
for(int i = 3; i < Math.sqrt(maxNum)+1; i = nextPrime(i)){
if((curr%i) == 0){
if(isPrime(curr)){
crossOut(curr);
}
}
}
curr = nextPrime(curr);
}
}
}
}
If someone could tell me where the bottleneck on the concurrent program is, I'd be very happy. Thanks in advance!
Primes
class is not thread safe -crossOut
for example is not thread safe - so it is very possible that your parallel threads have to do a lot more work because they don't see what the others have done (ii) even if that worked, you will do more work because you may check 17 * 19 before having crossed out 17 and 19 (whereas in the sequential algo, that can't happen) (iii) if your program completes fairly quickly (say a few 100s of ms), the time to start the thread will probably outweight any gains.2*processors
threads is probably too many. Start with just two threads and see if that gives you correct results and a performance boost. Then increase the number of threads.