Print

Print


Hi Sean,

I have spent some time to improve the performance of the SPEA2 algo
implemented in ECJ. I had a closer look at 

-> SPEA2Breeder.loadElites
-> SPEA2Evaluator.computeAuxiliaryData

mainly to parallelise the loops and sorts. The code is within my custom
framework hence can't not just simply post the classes. But the key areas of
improvement were

(1) Parallelise the main loop into smaller chunks to calc the distances,
(2) Parallelise the main loop to calc the fitness and
(3) Use parallel qsort to obtain sortedIndex

The last step add significantly performance by using the parallel Colt
framework and its provided parallel Quick Sort algorithm. I replace your
insert sort by

		for (int i = 0; i < nIndex; i++) {
			sortedIndex[i] = MathUtil.sequenceInt(0, nIndex-1);
			IntComparator c= new DistanceComparator(distances[i]);
			Sorting.parallelQuickSort( sortedIndex[i], 0, nIndex, c);
		}

Where DistanceComparator extends the IntComparator within the ParallelColt
framework. MathUtil is also a class within the same framework.

class DistanceComparator implements IntComparator {
	
	protected double distances[];
	
	public DistanceComparator( double distances[] ) {
		this.distances = distances;
	}

	@Override
	public int compare(int o1, int o2) {
		
		if( distances[o1] > distances[o2] )
			return 1;
		else if( distances[o1] < distances[o2] )
			return -1;
		else
			return 0;
	}
	
}

Maybe worth adding this to the head of branch?

PS: Let me know if you are interested so I can post you the individual classes.