title: Java Fork-Join not working with large ArrayList
body: <p>I'm pretty new to parallelism and concurrency and I'm trying to implement a median filter algorithm using Fork-Join in Java. Basically I read an input file into an ArrayList and use that list to generate a new ArrayList of the filtered medians(including the first and last element of the original ArrayList).</p>
  
  <p>Now I managed to make a Serial/Sequential version of the algorithm and it works fine. However when I tried to make a Fork-Join version, it does not seem to work for large ArrayLists(100000+). I tried it with a very small ArrayList of size 5 and it works fine. I cannot seem to be able to find my error(which I'm sure is a logic error and/or implementation error). Any help would be appreciated. </p>
  
  <p><strong>Here's the sequential algorithm snippet:</strong></p>
  
  <pre><code>    //Add first boundary element to output ArrayList
      outputElements.add(this.elements.get(0));
  
      //Start Filter Algorithm 
      while(elements.size()-counter &gt;= filterSize){
          for(int i = 0; i&lt;filterSize; i++){
              tempElements.add(this.elements.get(i+counter));
              if(i==filterSize){
                  break;
              }
          }
  
          Collections.sort(tempElements);
          outputElements.add(tempElements.get((filterSize-1)/2));
  
          counter++;
          tempElements.clear();
      }
  
      //Add last boundary element to output ArrayList.
      if (elements != null &amp;&amp; !elements.isEmpty()) {
          outputElements.add(elements.get(elements.size()-1));
      }//End Filter Algorithm
  </code></pre>
  
  <p><strong>Here's the Parallel Class I made. This is the part that's not working:</strong></p>
  
  <pre><code>public class Parallel extends RecursiveTask&lt;List&lt;Float&gt;&gt;{
      int lo;
      int hi;
      int filterSize;
      String outFile; //Output file name.
      int arraySize;
      List&lt;Float&gt; elements = new ArrayList&lt;Float&gt;();
      List&lt;Float&gt; tempElements = new ArrayList&lt;Float&gt;();
      List&lt;Float&gt; outputElements = new ArrayList&lt;Float&gt;();
      int counter = 0;
      static final int SEQUENTIAL_CUTOFF=1000;
  
      public Parallel(List&lt;Float&gt; elements, int filterSize, String outFile, int lo, int hi) {
          this.lo = lo;
          this.hi = hi;
          this.elements = elements;
          this.outFile = outFile;
          this.filterSize = filterSize;       
          if(lo == 0){
              outputElements.add(this.elements.get(0));
          }
      }
      @Override
      protected List&lt;Float&gt; compute() {
          long startTime = System.nanoTime(); //Algorithm starts here 
          if((hi-lo) &lt; SEQUENTIAL_CUTOFF) {
              while(hi-counter &gt;= filterSize){
                  for(int i = lo; i&lt;filterSize; i++){
                      tempElements.add(this.elements.get(i+counter));
                      if(i==filterSize){
                          break;
                      }
                  }               
                  Collections.sort(tempElements);
                  outputElements.add(tempElements.get((filterSize-1)/2));
                  counter++;
                  tempElements.clear();
                  return outputElements;
              }
            }else{              
                Parallel left = new Parallel(this.elements, this.filterSize, this.outFile, this.lo, ((this.lo + this.hi)/2));
                Parallel right = new Parallel(this.elements, this.filterSize, this.outFile, ((this.hi + this.lo)/2), this.hi);
                left.fork();
  
                List&lt;Float&gt; leftArr = new ArrayList&lt;Float&gt;();
                List&lt;Float&gt; rightArr = new ArrayList&lt;Float&gt;();
  
               rightArr =  right.compute();
               leftArr = left.join();
  
               List&lt;Float&gt; newList = new ArrayList&lt;Float&gt;();
               newList.addAll(leftArr);
               newList.addAll(rightArr);       
  
            }
          long endTime = System.nanoTime();//Algorithm ends here.
  
          //Write elements to output file 
          PrintWriter writeOutput = null;
          try {
              writeOutput = new PrintWriter(this.outFile, "UTF-8");
          } catch (FileNotFoundException | UnsupportedEncodingException e) {
              // TODO Auto-generated catch block
              e.printStackTrace();
          }
          writeOutput.println(outputElements.size());//Number of lines
          for(int i=0; i&lt;outputElements.size();i++){
              writeOutput.println(i+1 + " " + outputElements.get(i)); //Each line is written
          }
  
          writeOutput.close(); //Close when output finished writing.
          System.out.println("Parallel complete");
          return null;
      }
  }
  </code></pre>
  
  <p>Any help is really appreciated. I can't get this right after spending a few hours and researching a lot around S.O and Google.</p>
  
  <p>Edit: musical_coder suggested to post the errors I'm facing and here they are. It's a lot of errors:</p>
  
  <pre><code>Exception in thread "main" java.lang.IndexOutOfBoundsException
      at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
      at sun.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:57)
      at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45)
      at java.lang.reflect.Constructor.newInstance(Constructor.java:526)
      at java.util.concurrent.ForkJoinTask.getThrowableException(ForkJoinTask.java:536)
      at java.util.concurrent.ForkJoinTask.reportResult(ForkJoinTask.java:596)
      at java.util.concurrent.ForkJoinTask.join(ForkJoinTask.java:640)
      at java.util.concurrent.ForkJoinPool.invoke(ForkJoinPool.java:1521)
      at main.main(main.java:45)
  Caused by: java.lang.IndexOutOfBoundsException: Index: 1, Size: 0
      at java.util.ArrayList.rangeCheck(ArrayList.java:635)
      at java.util.ArrayList.get(ArrayList.java:411)
      at Parallel.compute(Parallel.java:44)
      at Parallel.compute(Parallel.java:57)
      at Parallel.compute(Parallel.java:57)
      at Parallel.compute(Parallel.java:57)
      at Parallel.compute(Parallel.java:57)
      at Parallel.compute(Parallel.java:57)
      at Parallel.compute(Parallel.java:57)
      at Parallel.compute(Parallel.java:57)
      at Parallel.compute(Parallel.java:57)
      at Parallel.compute(Parallel.java:57)
      at Parallel.compute(Parallel.java:57)
      at Parallel.compute(Parallel.java:57)
      at Parallel.compute(Parallel.java:1)
      at java.util.concurrent.RecursiveTask.exec(RecursiveTask.java:93)
      at java.util.concurrent.ForkJoinTask.doExec(ForkJoinTask.java:334)
      at java.util.concurrent.ForkJoinWorkerThread.execTask(ForkJoinWorkerThread.java:604)
      at java.util.concurrent.ForkJoinPool.scan(ForkJoinPool.java:784)
      at java.util.concurrent.ForkJoinPool.work(ForkJoinPool.java:646)
      at java.util.concurrent.ForkJoinWorkerThread.run(ForkJoinWorkerThread.java:398)
  </code></pre>