ArrayIndexOutOfBoundsException at method of concurrency approaches comprise

Question

I want to run some comparison of different approaches for concurrency technique.

But it throws next exceptions:

Warmup
BaseLine     :      21246915
============================
Cycles       :         50000
Exception in thread "pool-1-thread-3" Exception in thread "pool-1-thread-5" java.lang.ArrayIndexOutOfBoundsException: 100000
    at concurrency.BaseLine.accumulate(SynchronizationComparisons.java:89)
    at concurrency.Accumulator$Modifier.run(SynchronizationComparisons.java:39)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:744)
java.lang.ArrayIndexOutOfBoundsException: 100000
    at concurrency.BaseLine.accumulate(SynchronizationComparisons.java:89)
    at concurrency.Accumulator$Modifier.run(SynchronizationComparisons.java:39)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:744)

Here is code:

import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;
import java.util.*;

import static net.mindview.util.Print.*;

abstract class Accumulator {
    public static long cycles = 50000L;
    // Number of Modifiers and Readers during each test:
    private static final int N = 4;
    public static ExecutorService exec = Executors.newFixedThreadPool(N * 2);
    private static CyclicBarrier barrier = new CyclicBarrier(N * 2 + 1);
    protected volatile int index = 0;
    protected volatile long value = 0;
    protected long duration = 0;
    protected String id = "error";
    protected final static int SIZE = 100000;
    protected static int[] preLoaded = new int[SIZE];
    static {
        // Load the array of random numbers:
        Random rand = new Random(47);
        for (int i = 0; i < SIZE; i++)
            preLoaded[i] = rand.nextInt();
    }

    public abstract void accumulate();

    public abstract long read();

    private class Modifier implements Runnable {
        public void run() {
            for (long i = 0; i < cycles; i++)
                accumulate();
            try {
                barrier.await();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
    }

    private class Reader implements Runnable {
        @SuppressWarnings("unused")
        private volatile long value;

        public void run() {
            for (long i = 0; i < cycles; i++)
                value = read();
            try {
                barrier.await();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
    }

    public void timedTest() {
        long start = System.nanoTime();
        for (int i = 0; i < N; i++) {
            exec.execute(new Modifier());
            exec.execute(new Reader());
        }
        try {
            barrier.await();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
        duration = System.nanoTime() - start;
        printf("%-13s: %13d\n", id, duration);
    }

    public static void report(Accumulator acc1, Accumulator acc2) {
        printf("%-22s: %.2f\n", acc1.id + "/" + acc2.id, (double) acc1.duration / (double) acc2.duration);
    }
}

class BaseLine extends Accumulator {
    {
        id = "BaseLine";
    }

    public void accumulate() {
        value += preLoaded[index++];
        if (index >= SIZE)
            index = 0;
    }

    public long read() {
        return value;
    }
}

class SynchronizedTest extends Accumulator {
    {
        id = "synchronized";
    }

    public synchronized void accumulate() {
        value += preLoaded[index++];
        if (index >= SIZE)
            index = 0;
    }

    public synchronized long read() {
        return value;
    }
}

class LockTest extends Accumulator {
    {
        id = "Lock";
    }
    private Lock lock = new ReentrantLock();

    public void accumulate() {
        lock.lock();
        try {
            value += preLoaded[index++];
            if (index >= SIZE)
                index = 0;
        } finally {
            lock.unlock();
        }
    }

    public long read() {
        lock.lock();
        try {
            return value;
        } finally {
            lock.unlock();
        }
    }
}

class AtomicTest extends Accumulator {
    {
        id = "Atomic";
    }
    private AtomicInteger index = new AtomicInteger(0);
    private AtomicLong value = new AtomicLong(0);

    public void accumulate() {
        // Oops! Relying on more than one Atomic at
        // a time doesn't work. But it still gives us
        // a performance indicator:
        int i = index.getAndIncrement();
        value.getAndAdd(preLoaded[i]);
        if (++i >= SIZE)
            index.set(0);
    }

    public long read() {
        return value.get();
    }
}

public class SynchronizationComparisons {
    static BaseLine baseLine = new BaseLine();
    static SynchronizedTest synch = new SynchronizedTest();
    static LockTest lock = new LockTest();
    static AtomicTest atomic = new AtomicTest();

    static void test() {
        print("============================");
        printf("%-12s : %13d\n", "Cycles", Accumulator.cycles);
        baseLine.timedTest();
        synch.timedTest();
        lock.timedTest();
        atomic.timedTest();
        Accumulator.report(synch, baseLine);
        Accumulator.report(lock, baseLine);
        Accumulator.report(atomic, baseLine);
        Accumulator.report(synch, lock);
        Accumulator.report(synch, atomic);
        Accumulator.report(lock, atomic);
    }

    public static void main(String[] args) {
        int iterations = 5; // Default
        if (args.length > 0) // Optionally change iterations
            iterations = new Integer(args[0]);
        // The first time fills the thread pool:
        print("Warmup");
        baseLine.timedTest();
        // Now the initial test doesn't include the cost
        // of starting the threads for the first time.
        // Produce multiple data points:
        for (int i = 0; i < iterations; i++) {
            test();
            Accumulator.cycles *= 2;
        }
        Accumulator.exec.shutdown();
    }
}

How to solve this trouble?

Answer 1

The array preLoaded is of size 100000. So, the valid index starts from 0 to 99999 since array index starts from 0. You need to swap the statements in method accumulate()

Change this

        value += preLoaded[index++]; //index validity is not done
        if (index >= SIZE)
            index = 0;

to

        if (index >= SIZE)
            index = 0;
        value += preLoaded[index++]; // index validity is done and controlled

This will not make the index go to 100000. It will make it to 0 when it turns 100000 before the index value is accessed.

Note : The above code is vulnerable only in multi-threaded environment. The above code will work fine with single thread.

Answer 2

Change BaseLine class and AtomicTest class:

 class BaseLine extends Accumulator {
  {
    id = "BaseLine";
  }
  public void accumulate() {
    int early = index++;  // early add and assign to a temp.
    if(early >= SIZE) {
      index = 0;
      early = 0;
    }  
    value += preLoaded[early];
  }
  public long read() {
    return value;
  }
}

class AtomicTest extends Accumulator {
  {
    id = "Atomic";
  }
  private AtomicInteger index = new AtomicInteger(0);
  private AtomicLong value = new AtomicLong(0);
  public void accumulate() {
    int early = index.getAndIncrement();
    if(early >= SIZE) {
      index.set(0);
      early = 0;
    }
    value.getAndAdd(preLoaded[early]);
  }
  public long read() {
    return value.get();
  }
}

Answer 3

I suspect that you're running into concurrent executions of BaseLine.accumulate() near the boundary of the preLoaded array.

You've got 4 threads hammering away at an unsynchronized method, which is potentially leading to index being incremented to 100000 by say, Thread 1, and before Thread 1 can set it back to 0, one of Thread 2, 3 or 4 is coming in and attempting to access preLoaded[index++], which fails as index is still 100000.