I can't identify the issue with my parallel run timer

Question

I have a program that applies a median filter to an array of over 2 million values.

I'm trying to compare run times for sequential vs parallel on the same dataset. So when I execute the program, it does 20 runs, every run is timed, and an average of the 20 times is outputted to the console.

ArrayList<Double> times = new ArrayList<>(20);//to calculate average run time

for (int run = 1; run < 21; run++) //algorithm will run 20 times
{
    long startTime = System.nanoTime();

    switch (method)
    {
        case 1: //Sequential
            filt.seqFilter();
            break;
        case 2: //ForkJoin Framework
            pool.invoke(filt); //pool is ForkJoin
            break;
    }
    Double timeElapsed = (System.nanoTime() - startTime) / 1000000.0;
    times.add(run - 1, timeElapsed);
    System.out.println("Run " + run + ": " + timeElapsed + " milliseconds.");
}

times.remove(Collections.max(times)); //there's always a slow outlier
double timesSum = 0;
for (Double e : times)
{
    timesSum += e;
}
double average = timesSum / 19;
System.out.println("Runtime: " + average);

filt is of type FilterObject which extends RecursiveAction. My overridden compute() method in FilterObject looks like this:

public void compute()
{
    if (hi - lo <= SEQUENTIAL_THRESHOLD)
    {
        seqFilter();
    }
    else
    {
        FilterObject left = new FilterObject(lo, (hi + lo) / 2);
        FilterObject right = new FilterObject((hi + lo) / 2, hi);
        left.fork();
        right.compute();
        left.join(); 
    }
}

seqFilter() processes the values between the lo and hi indices in the starting array and adds the processed values to a final array in the same positions. That's why there is no merging of arrays after left.join().

My run times for this are insanely fast for parallel - so fast that I think there must be something wrong with my timer OR with my left.join() statement. I'm getting average times of around 170 milliseconds for sequential with a filtering window of size 3 and 0.004 milliseconds for parallel. Why am I getting these values? I'm especially concerned that my join() is in the wrong place.

If you'd like to see my entire code, with all the classes and some input files, follow this link.

score 0 · Answer 1 · edited May 23 '17 at 10:26

After some testing of your code I found the reason. It turned out that the ForkJoinPool runs one task instance only once. Subsequent invoke() calls with the same task instance will return immediately. So you have to reinstantiate the task for every run.

Another problem is with the parallel (standard threads) run. You are starting the threads but never waiting for them to finish before measuring the time. I think You could use the CyclicBarrier here.

With the mentioned fixes I get roughly the same time for ForkJoin and standard threads. And it's three times faster than sequential. Seems reasonable.

P.S. You are doing a micro-benchmark. It may be useful to read answers to that question to improve your benchmark accuracy: How do I write a correct micro-benchmark in Java?

I can't identify the issue with my parallel run timer

1 Answers1