package be.ac.vub.ir.multithreading;

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

import flanagan.math.Fmath;
import be.ac.vub.ir.util.Chrono;

public class Counting3s {

	int[] array;
	Counting3s(int length, int oneEveryX){
		array = new int[length];
		for(int i=0;i<length; i++)
			array[i] = (int)(Math.random()*oneEveryX);
	}
	//======================== PROGRAM ===========================//
	public static void main(String[] args) {
		final int N=60000000, T=20, A_3_ONE_EVERY_X=10;
		Counting3s c = new Counting3s(N, A_3_ONE_EVERY_X);
		
		System.out.println("Counting 3s in an array of "+N+" elements and "+T+ " threads:");

		Chrono chrono = new Chrono();
		int nbr = c.seqCounting();
		long seqtime = chrono.stop();
		System.out.println(" * Seq  : counted "+nbr+" 3s in "+chrono.toString());
		
		chrono.restart();
		nbr = c.parCounting1(T);
		long partime = chrono.stop();
		System.out.println(" * Par 1 (no sync)       : counted "+nbr+" 3s in "+chrono.toString()+" => Speedup = "+Fmath.truncate((float) seqtime/partime, 2));

		chrono.restart();
		nbr = c.parCounting2(T);
		partime = chrono.stop();
		System.out.println(" * Par 2 (boolean)       : counted "+nbr+" 3s in "+chrono.toString()+" => Speedup = "+Fmath.truncate((float)seqtime/partime, 2));

		chrono.restart();
		nbr = c.parCounting3(T);
		partime = chrono.stop();
		System.out.println(" * Par 3 (volatile)      : counted "+nbr+" 3s in "+chrono.toString()+" => Speedup = "+Fmath.truncate((float)seqtime/partime, 2));

		chrono.restart();
		nbr = c.parCounting4(T);
		partime = chrono.stop();
		System.out.println(" * Par 4 (sync method)   : counted "+nbr+" 3s in "+chrono.toString()+" => Speedup = "+Fmath.truncate((float)seqtime/partime, 2));

		chrono.restart();
		nbr = c.parCounting5(T);
		partime = chrono.stop();
		System.out.println(" * Par 5 (local ctr)     : counted "+nbr+" 3s in "+chrono.toString()+" => Speedup = "+Fmath.truncate((float)seqtime/partime, 2));
		
		chrono.restart();
		nbr = c.parCounting5b(T);
		partime = chrono.stop();
		System.out.println(" * Par 5b (padding)      : counted "+nbr+" 3s in "+chrono.toString()+" => Speedup = "+Fmath.truncate((float)seqtime/partime, 2));
		
		chrono.restart();
		nbr = c.parCounting6(T);
		partime = chrono.stop();
		System.out.println(" * Par 6 (atomic ctr)    : counted "+nbr+" 3s in "+chrono.toString()+" => Speedup = "+Fmath.truncate((float)seqtime/partime, 2));
		
		chrono.restart();
		nbr = c.parCounting7(T);
		partime = chrono.stop();
		System.out.println(" * Par 7 (atomic boolean): counted "+nbr+" 3s in "+chrono.toString()+" => Speedup = "+Fmath.truncate((float)seqtime/partime, 2));

		chrono.restart();
		nbr = c.parCounting8(T);
		partime = chrono.stop();
		System.out.println(" * Par 8 (sync by main)  : counted "+nbr+" 3s in "+chrono.toString()+" => Speedup = "+Fmath.truncate((float)seqtime/partime, 2));

	}

	//======================== SEQUENTIAL COUNTING  ===========================//
	int seqCounting(){
		int count=0;
		for(int i=0;i<array.length; i++)
			if (array[i] == 3)
				count++;
		return count;
	}
	//======================== (1) PARALLEL COUNTING WITHOUT SYNCHRONIZATION ===========================//
	int count;
	int parCounting1(int nbrThreads){
		count=0;
		final int NBR_THREADS = nbrThreads;
		Thread[] threads = new Thread[nbrThreads];
		for(int t=0;t<nbrThreads;t++){
			final int T = t;
			threads[t] = new Thread(){
				public void run(){
					int length_per_thread=array.length/NBR_THREADS;
					int start=T*length_per_thread;
					for(int i=start;i<start+length_per_thread; i++)
						if (array[i] == 3)
							count++;
				}
			};
			threads[t].start();
		}
		// wait until all threads have finished
		for(int t=0;t<nbrThreads;t++)
			try {
				threads[t].join();
			} catch (InterruptedException e) {}
		return count;
	}
	//======================== (2) PARALLEL COUNTING WITH BOOLEAN PROTECTION  ===========================//
	boolean access=true;
	int parCounting2(int nbrThreads){
		count=0;
		final int NBR_THREADS = nbrThreads;
		Thread[] threads = new Thread[nbrThreads];
		for(int t=0;t<nbrThreads;t++){
			final int T = t;
			threads[t] = new Thread(){
				public void run(){
					int length_per_thread=array.length/NBR_THREADS;
					int start=T*length_per_thread;
					for(int i=start;i<start+length_per_thread; i++)
						if (array[i] == 3){
							while(!access)
								yield();
							access=false;
							countv++;
							access=true;
						}
				}
			};
			threads[t].start();
		}
		// wait until all threads have finished
		for(int t=0;t<nbrThreads;t++)
			try {
				threads[t].join();
			} catch (InterruptedException e) {}
		return countv;
	}
	//======================== (3) PARALLEL COUNTING WITH VOLATILE  ===========================//
	volatile int countv;
	int parCounting3(int nbrThreads){
		countv=0;
		final int NBR_THREADS = nbrThreads;
		Thread[] threads = new Thread[nbrThreads];
		for(int t=0;t<nbrThreads;t++){
			final int T = t;
			threads[t] = new Thread(){
				public void run(){
					int length_per_thread=array.length/NBR_THREADS;
					int start=T*length_per_thread;
					for(int i=start;i<start+length_per_thread; i++)
						if (array[i] == 3)
							countv++;
				}
			};
			threads[t].start();
		}
		// wait until all threads have finished
		for(int t=0;t<nbrThreads;t++)
			try {
				threads[t].join();
			} catch (InterruptedException e) {}
		return countv;
	}
	//======================== (4) PARALLEL COUNTING WITH SYNCHRONIZED METHOD ===========================//
	synchronized void addOne(){ count++; }
	int parCounting4(int nbrThreads){
		count=0;
		final int NBR_THREADS = nbrThreads;
		Thread[] threads = new Thread[nbrThreads];
		for(int t=0;t<nbrThreads;t++){
			final int T = t;
			threads[t] = new Thread(){
				public void run(){
					int length_per_thread=array.length/NBR_THREADS;
					int start=T*length_per_thread;
					for(int i=start;i<start+length_per_thread; i++)
						if (array[i] == 3)
							addOne();
				}
			};
			threads[t].start();
		}
		// wait until all threads have finished
		for(int t=0;t<nbrThreads;t++)
			try {
				threads[t].join();
			} catch (InterruptedException e) {
			}
		return count;
	}
	//======================== (4b) PARALLEL COUNTING WITH SYNCHRONIZED BLOCK ===========================//
	int parCounting4b(int nbrThreads){
		count=0;
		final int NBR_THREADS = nbrThreads;
		Thread[] threads = new Thread[nbrThreads];
		for(int t=0;t<nbrThreads;t++){
			final int T = t;
			threads[t] = new Thread(){
				public void run(){
					int length_per_thread=array.length/NBR_THREADS;
					int start=T*length_per_thread;
					for(int i=start;i<start+length_per_thread; i++)
						if (array[i] == 3)
							synchronized(Counting3s.this){
								count++;
							}
				}
			};
			threads[t].start();
		}
		// wait until all threads have finished
		for(int t=0;t<nbrThreads;t++)
			try {
				threads[t].join();
			} catch (InterruptedException e) {}
		return count;
	}
	//======================== (5) PARALLEL COUNTING WITHOUT LOCAL COUNTER ===========================//
	synchronized void addCount(int n){ count+=n; }
	int parCounting5(int nbrThreads){
		count=0;
		final int NBR_THREADS = nbrThreads;
		Thread[] threads = new Thread[nbrThreads];
		for(int t=0;t<nbrThreads;t++){
			final int T = t;
			threads[t] = new Thread(){
				int private_count=0;
				public void run(){
					int length_per_thread=array.length/NBR_THREADS;
					int start=T*length_per_thread;
					for(int i=start;i<start+length_per_thread; i++)
						if (array[i] == 3)
							private_count++;
					addCount(private_count);
				}
			};
			threads[t].start();
		}
		// wait until all threads have finished
		for(int t=0;t<nbrThreads;t++)
			try {
				threads[t].join();
			} catch (InterruptedException e) {
			}
		return count;
	}
	//======================== (5b) PARALLEL COUNTING WITHOUT PADDING ===========================//
	
	int parCounting5b(int nbrThreads){
		count=0;
		final int NBR_THREADS = nbrThreads;
		Thread[] threads = new Thread[nbrThreads];
		for(int t=0;t<nbrThreads;t++){
			final int T = t;
			threads[t] = new Thread(){
				int private_count=0;
				int p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15; // padding
				public void run(){
					int length_per_thread=array.length/NBR_THREADS;
					int start=T*length_per_thread;
					for(int i=start;i<start+length_per_thread; i++)
						if (array[i] == 3)
							private_count++;
					addCount(private_count);
				}
			};
			threads[t].start();
		}
		// wait until all threads have finished
		for(int t=0;t<nbrThreads;t++)
			try {
				threads[t].join();
			} catch (InterruptedException e) {
			}
		return count;
	}
	//======================== (6) PARALLEL COUNTING WITH ATOMIC COUNTER ===========================//
	AtomicInteger counter = new AtomicInteger();
	int parCounting6(int nbrThreads){
		count=0;
		final int NBR_THREADS = nbrThreads;
		Thread[] threads = new Thread[nbrThreads];
		for(int t=0;t<nbrThreads;t++){
			final int T = t;
			threads[t] = new Thread(){
				int private_count=0;
				public void run(){
					int length_per_thread=array.length/NBR_THREADS;
					int start=T*length_per_thread;
					for(int i=start;i<start+length_per_thread; i++)
						if (array[i] == 3)
							private_count++;
					counter.addAndGet(private_count);
				}
			};
			threads[t].start();
		}
		// wait until all threads have finished
		for(int t=0;t<nbrThreads;t++)
			try {
				threads[t].join();
			} catch (InterruptedException e) {
			}
		return counter.get();
	}
	//======================== (7) PARALLEL COUNTING WITH PROTECTION BY ATOMIC BOOLEAN ===========================//
	// solution provided by Sven Claeys (2009)
	int countme;
	AtomicBoolean block = new AtomicBoolean(false);

	int parCounting7(int nbrThreads){
		countme=0;
		block.set(false);
		final int NBR_THREADS = nbrThreads;
		Thread[] threads = new Thread[nbrThreads];
		for(int t=0;t<nbrThreads;t++){
			final int T = t;
			threads[t] = new Thread(){
				public void run(){
					int length_per_thread=array.length/NBR_THREADS;
					int start=T*length_per_thread;
					for(int i=start;i<start+length_per_thread; i++)
						if (array[i] == 3){
							while (!block.compareAndSet(false, true)) {
								yield();
							}
							countme++;
							block.set(false);
						}
				}
			};
			threads[t].start();
		}
		// wait until all threads have finished
		for(int t=0;t<nbrThreads;t++)
			try {
				threads[t].join();
			} catch (InterruptedException e) {}
		return countme;
	}
	 
	 
	 //======================== PARALLEL COUNTING WITHOUT SYNCHRONIZATION BY MAIN THREAD ===========================//
	// solution provided by Robrecht Dewaele (2010)
	 private class ThreeCounter extends Thread {
         int threes = 0;
         final int T, NBR_THREADS;

         public ThreeCounter(int T, int nbrThreads) {
                 this.T = T;
                 this.NBR_THREADS = nbrThreads;
         }
         public void run(){
                 int length_per_thread=array.length/NBR_THREADS;
                 int start=T*length_per_thread;
                 for(int i=start;i<start+length_per_thread; i++)
                         if (array[i] == 3)
                                 threes++;
         }
	 }
	 int parCounting8(int nbrThreads){

	         ThreeCounter[] threads = new ThreeCounter[nbrThreads];
	         for(int t=0;t<nbrThreads;t++){
	                 threads[t] = new ThreeCounter(t, nbrThreads);
	                 threads[t].start();
	         }
	         int count8=0;
	         // wait until all threads have finished
	         for(int t=0;t<nbrThreads;t++)
	                 try {
	                         threads[t].join();
	                         count8 += threads[t].threes; // 
	                 } catch (InterruptedException e) {}
	        return count8;
	 }

}