Grayscale image algorithm is slower when multithreaded than sequential

Question

For a school project we need to multithread an image processing algorithm. I decided to divide the height of the image by the number of threads. Each thread loops though the height and width and changes the colors of the pixels. Weirdly though, the sequential version is always much faster. What am I doing wrong?

The method that is executed by the threads:

public synchronized void applyGrayScale(int numberOfThreads) {
    int heightPerThread = imageHeight / numberOfThreads;
    //Set the thread counter
    int threadCounter = this.getCount();
    this.setCount(count + 1);

    /*The height per thread is calculated by the number of threads. We first start at 0. For the next thread we start at heightPerThread * [current thread number]
    So for example; first thread runs from 0 to 80 pixels. The second thread runs from 81 to 160 pixels.
     */
    for (int j = ((heightPerThread - 2) * threadCounter); j < (heightPerThread * (threadCounter + 1) - 1); j++) {
        for (int i = 0; i < imageInput.getWidth() - 1; i++) {
            //Get the RGB value and set it to grayscale
            int rgb;
            int p = RGB.getRGBW(imageInput, i, j);
            rgb = (int) ((((p >> 16) & 0xFF) * 0.2125) + (((p >> 8) & 0xFF) * 0.7154) + ((p & 0xFF) * 0.0721));
            rgb = (rgb << 16) | (rgb << 8) | (rgb);
            //Set the new RGB value per pixel
            imageOutput.setRGB(i, j, rgb);
        }
    }
}

Code that runs the program:

   int threadsAmount = 5;
   final Thread[] threads = new Thread[threadsAmount];

   BufferedImage image = null;
    try {
        image = ImageIO.read(new File("C:/Cat03.jpg"));
    } catch (IOException e) {
        e.printStackTrace();
    }

    //Define the starting time
    long start = System.currentTimeMillis();

    //Create a new grayscale object and set the image
    final GrayscaleParallel grayscaleParallel = new GrayscaleParallel(image);

    //Thread to apply the grayscale with the number of threads
    class grayScaleThread extends Thread {
        @Override
        public void run() {
            grayscaleParallel.applyGrayScale(threadsAmount);
        }
    }

    //Start all threads
    for (int i = 0; i < threadsAmount; i++) {
        threads[i] = new grayScaleThread();
        threads[i].start();
    }

    //Wait for all threads to finish
    for (int i = 0; i < threadsAmount; i++) {
        try {
            threads[i].join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    //save result to file
    grayscaleParallel.createImage();

    //Define how long it took
    long end = System.currentTimeMillis();
    float sec = (end - start) / 1000F;
    System.out.println(sec + " seconds parallel");

The output is: 0.897 seconds parallel 0.798 seconds serial

The sequential algorithm:

 for (int j = 0; j < _image.getHeight(); j++) {
        for (int i = 0; i < _image.getWidth(); i++) {
            int rgb;
            int p = RGB.getRGBW(_image, i, j);

            rgb = (int) ((((p >> 16) & 0xFF) * 0.2125) + (((p >> 8) & 0xFF) * 0.7154) + ((p & 0xFF) * 0.0721));
            rgb = (rgb << 16) | (rgb << 8) | (rgb);

            imageOutput.setRGB(i, j, rgb);
        }
    }
    return imageOutput;

When I use a very large image the parallel time seems to improve by 0.5 seconds over the sequential one, but when I don't save the results the parallel algorithm is again slower.

Answer 1

The problem is that your applyGrayScale() method is synchronized - only one thread can execute it at the same time as all of them run it on the same object. There is no part in your code that could run parallel. So basicly the process is more or less the same as in the sequential variant but you add some extra overhead for context switching and tracking which thread enters the method.

Instead you have to split the image before hand - when creating thread "tell" them which part it should modify. Then change the method from synchronized to normal and let them do their job in parallel.

Answer 2

You do nothing wrong!

The bottle-neck in converting the image is not the calculation, it is the memory-access.

With one thread (=sequential) you access the memory in a sequential way. The computer is optimized for such sequential accesses. E.g. by pre loading the next memory addresses if you access an address (memory-bus is much wider than 32 or 64 bits) Also the caching of your CPU predicts sequential accesses because they are very common in programming.

Since the calculation you do is very simple, the slowest part of the algorithm is to read and write the data from/to RAM. If you use more than one thread and access the memory in different (not sequential) addresses, you get a lot of cache-misses and do not benefit from the caching and preloading done by you CPU / memory-bus. That is the reason the performance is worse than the sequential version of your code.

(There might also be some overhead for concurrent reading/writing of the different threads in the multi-threaded version, which might reduce the performance even more)

---

As mentioned in the comments:

As pointed out by Amongalen (see comment/answer) there might on top of the things I mentioned above be another quite simple reason why there could not be any parallel execution in your implementation.

applyGrayScale() is synchronized and therefore cannot be called in parallel on the same class instance. So if all your threads share the same instance they call applyGrayScale() on, all other threads are wailing while one executes the method.

But I'm sure even after fixing this, the multi-threaded version will still be slower than the sequential one because of the reasons I mentioned above in my answer.