2

Edit: Just to point out, I know what index out of bounds usually means - I would not make this post if it wasn't something I've never encountered before, which in this case is an array list that refuses to add a plain old int of 6000 or so, and a byte array that is of size 2mil...

Solution: For anyone else looking for answers to this, it was due to multiple threads concurrently adding to the list, which caused it to not update the new size of the list properly. To avoid it, you either need to synchronize the part that adds to the list, or use something like a Vector instead.

I have a program for finding prime numbers lower than a given number n (Eratosthenes Sieve) that I have parallelised. In it, I have marked off all numbers that are not primes up to n in a byte array, and I have an ArrayList that contains the primes I have found.

Initially, I just add the numbers up until the sqrt(n), and mark off all products of the prime I find (so if I find 5, I mark off: 5*5, and 5*5 + 2*5, and 5*5 + 3*5 etc), so that when I have found all primes up to the square root of n, I have crossed out all numbers that are not primes between sqrt(n) up until n.

At this point, all I have to do, is go through the rest of the byte array, and check if it's marked as a prime or not, and add it if it is. However, I'm getting an index out of bounds exception on the part that adds the marked-as-prime numbers to my ArrayList of primes?

  public void addRemainingPrimes(int start, int end){

    for(int i = start; i < end; i+= 2){
      if(isPrime(i)){
        primes.add(i);
      }
    }
  }

  public boolean isPrime(int i) {
      int byteCell    = i / 16;
      int bit         = (i/2) % 8;
      return (numbers[byteCell] & (1 << bit)) == 0;

  }

In the thread class: 

public void run(){
  //does stuff to find primes up to sqrt(n)

  updateRange();
  addRemainingPrimes(start, end);

}

public void updateRange(){
  if(id == 0){
    start = sqrt;
  }else{
    start = (((n - sqrt)/k) * id) + sqrt;
  }
  if(id == k-1){
    end = n;
  }else{
    end = start + ((n - sqrt) / k) - 1;
  }

}

numbers is the byte array of size n, primes is my ArrayList of primes, n = 2.000.000, k is the number of threads I'm using, and id is from 0 to k-1.

The error I'm getting: 

Exception in thread "Thread-5" java.lang.ArrayIndexOutOfBoundsException: 6246
    at java.util.ArrayList.add(ArrayList.java:463)
    at ParallellSieve.addRemainingPrimes(ParallellSieve.java:162)
    at ParallellSieve$PrimeWorker.run(ParallellSieve.java:194)
    at java.lang.Thread.run(Thread.java:748)
Telanore
  • 75
  • 1
  • 9
  • can you debug to point where the exception and then capture the value of `i` ?. It may be either less than `0` or bigger than `Integer.MAX_VALUE `. check your with you debugger. – arthur Mar 22 '18 at 12:38
  • (Sorry, I'm an idiot today) I did that and it gave me that i = 27918, so it should be plenty within range. It seems to change every time I run it though, so maybe I have to synchronize the adding to the list? – Telanore Mar 22 '18 at 13:08
  • It was indeed a concurrency issue. Multiple threads adding to the same ArrayList can cause it to not update the new size of the list appropriately, thus throwing an out of bounds exception. – Telanore Mar 22 '18 at 13:13

0 Answers0