Java speedup processes / threads

Question

I have a rather big ArrayList.

I have to go through every index, and do a expensive calculation

My first idea to speed it up was by putting it into a thread. It works, but it is still extremely slow. I tinkered around the calculation, to make it less expensive, but its still to slow. The best solution i came up with is basically this one.

public void calculate(){
    calculatePart(0);
    calculatePart(1);
}

public void calculatePart(int offset) {
      new Thread() {
            @Override
            public void run() { 
                int i = offset;
                 while(arrayList.size() > i) {
                    //Do the calulation
                     i +=2;
              }
          }              
     }.start();
}

Yet this feels like a lazy, unprofessional solution. That is why I'm asking if there is a cleaner and even faster solution

Answer 1

Assuming that doing task on each element doesn't lead to data races, you could leverage the power of parallelism. To maximize the number of computations occurring at the same time, you would have to give tasks to each of the processors available in your system.

In Java, you can get the number of processors (cores) available using this:

int parallelism = Runtime.getRuntime().availableProcessors();

The idea is to create number of threads equal to the available processors.

So, if you have 4 processors available, you can create 4 threads and ask them to process items at a gap of 4.Suppose you have a list of size 10, which needs to be processed in parallel.

Then,

Thread 1 processes items at index 0,4,8
Thread 2 processes items at index 1,5,9
Thread 3 processes items at index 2,6
Thread 4 processes items at index 3,7

I tried to simulate your scenario with the following code:

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class SpeedUpTest {

    public static void main(String[] args) throws InterruptedException, ExecutionException {
        long seqTime, twoThreadTime, multiThreadTime;
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

        long time = System.currentTimeMillis();
        sequentialProcessing(list);
        seqTime = System.currentTimeMillis() - time;

        int parallelism = 2;
        ExecutorService executorService = Executors.newFixedThreadPool(parallelism);
        time = System.currentTimeMillis();
        List<Future> tasks = new ArrayList<>();
        for (int offset = 0; offset < parallelism; offset++) {

            int finalParallelism = parallelism;
            int finalOffset = offset;
            Future task = executorService.submit(() -> {
                int i = finalOffset;
                while (list.size() > i) {
                    try {
                        processItem(list.get(i));
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    i += finalParallelism;
                }
            });
            tasks.add(task);
        }
        for (Future task : tasks) {
            task.get();
        }
        twoThreadTime = System.currentTimeMillis() - time;

        parallelism = Runtime.getRuntime().availableProcessors();
        executorService = Executors.newFixedThreadPool(parallelism);
        tasks = new ArrayList<>();
        time = System.currentTimeMillis();
        for (int offset = 0; offset < parallelism; offset++) {

            int finalParallelism = parallelism;
            int finalOffset = offset;
            Future task = executorService.submit(() -> {
                int i = finalOffset;
                while (list.size() > i) {
                    try {
                        processItem(list.get(i));
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    i += finalParallelism;
                }
            });
            tasks.add(task);
        }
        for (Future task : tasks) {
            task.get();
        }
        multiThreadTime = System.currentTimeMillis() - time;
        log("RESULTS:");
        log("Total time for sequential execution : " + seqTime / 1000.0 + " seconds");
        log("Total time for execution with 2 threads: " + twoThreadTime / 1000.0 + " seconds");
        log("Total time for execution with " + parallelism + " threads: " + multiThreadTime / 1000.0 + " seconds");


    }

    private static void log(String msg) {
        System.out.println(msg);
    }

    private static void processItem(int index) throws InterruptedException {
        Thread.sleep(5000);
    }

    private static void sequentialProcessing(List<Integer> list) throws InterruptedException {

        for (int i = 0; i < list.size(); i++) {
            processItem(list.get(i));
        }
    }

}

OUTPUT:

RESULTS:

Total time for sequential execution : 50.001 seconds

Total time for execution with 2 threads: 25.102 seconds

Total time for execution with 4 threads: 15.002 seconds

Answer 2

High theoretically speaking: if you have X elements and your calculation must perform N operations on each one then your computer(processor) must perform X*N operations total, then...

Parallel threads can make it faster only if in the calculation operations there are some of them when thread is waiting (e.g. File or Network operations). That time can be used by other threads. But if all operations are pure CPU (e.g. mathematics) and thread is not waiting - required time to perform X*N operations stays the same.

Also each tread must give other threads ability to take control over CPU at some point. It happens automatically between methods calls or if you have Thread.yield() call in your code.

as example method like:

public void run()
{
  long a=0;
  for (long i=1; i < Long.MAX_VALUE; i++)
  {
   a+=i;
  }
 }

will not give other thread a chance to take control over CPU until it fully completed and exited.